链表
链表和数组的比较
数组：连续的内存空间 链表：通过指针将一组零散的内存块串联起来
常见的链表结构
单链表
单链表的删除和插入：O(1)
循环链表
双向链表
相对于单链表
优点：有前继指针，再插入删除时不需要单独存储一个前继指针。
缺点：消耗更多空间。
对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而内存紧张的程序，可以通过消耗更多时间（时间换空间）来降低内存的消耗。
缓存的例子实际就是用空间换时间的设计思想。如果把数据存储在硬盘中，会比较节省内存，但每次查找数据都要询问一次硬盘，效率低；但如果通过缓存技术，实现将缓存数据加载到内存中，虽然耗费内存空间，但每次查询的速度大大提高了。
双向循环链表
链表和数组性能比较
但具体情况还要具体分析：
数组简单易用，在实现上使用的是整块连续的内存空间，可以借助CPU缓存机制，预读数组中的数据，所以访问效率高。但如果声明的数组不够用还可能需要再申请一个更大的内存空间，把原数组拷贝过去，费时；
而链表在内存中不是连续存储，所以对CPU缓存不友好，没办法有效预读且消耗更多内存。但是链表本身没有大小限制，天然支持动态扩容。但是对链表频繁的插入、删除，还会导致频繁的内存申请和释放，容易造成内存碎片。
CPU缓存机制： CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(字节对其)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。
例
用链表实现LRU缓存淘汰策略：
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些应该被保留？常见的策略有三种：1. FIFO 2. 最少使用策略LFU（Least Frequently Used）3. 最近最少使用策略LRU（Least Recently Used）。
实现思路：维护一个有序（按访问时间）单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从头开始遍历链表。
当要访问缓存中一个数据时，先遍历链表查找对应数据结点，找到则返回，并将其从原来的位置删除，插入表头维护顺序。如果没找到，说明此数据没有在缓存中，需要加入缓存链表中，此时分两种情况：1. 缓存未满，则将最新数据插入表头； 2. 缓存已满，则将最少被人访问的尾节点删除，新数据插入表头。
习题：判断字符串是否是回文（对称）用单链表实现。
- 找到链表中点：快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到头，慢指针就到中点了。（快指针步数=总结点数/2取上，就是中点）
- 慢指针走到中点的过程中同时进行逆序，从中心向两边依次前进比较，不同false，指针相遇全部比较完true。
链表逆序
function reverseLink(nodeLink) { var preNode = null; var currentNode = nodeLink; var nextNode = currentNode.next; while(currentNode) { currentNode.next = preNode; preNode = currentNode; currentNode = nextNode; nextNode = nextNode?nextNode.next:null; } return preNode;}复制代码 用链表的技巧
- 链表中节点由数据和指针构成（C中可以用结构体表示，JavaScript中可以用对象表示）
- 警惕链表断链（指针丢失）和内存泄漏：插入删除时等情况容易断链。一般用链表解决问题使用较多的是创建多个指针指向节点。
- 利用哨兵简化实现难度：哨兵，一般就是用来解决“边界问题”的，不直接参与业务逻辑。解决问题时考虑边界情况很重要。
- 中点留意边界条件处理
- 编写代码过程中一定要注意检查边界条件是否考虑全面，以及代码在边界条件下是否能正常运行。对于链表来说，边界条件大致有以下几点:
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾节点的时候，代码是否能正常工作？
- 除此之外还有一些异常情况，如传入的参数是否为空啦等等。
- 举例画图，辅助思考
- 多练：常见的5个链表操作：
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第n个节点
- 求链表的中间节点
代码
- 删除单链表中倒数第n个节点。
困难处：单链表要遍历才能知道链表长度，而且求倒数第n个，逆向链表也不好做。 思路：在链表中如果涉及到位置，可以试试用两个指针来解决问题，两个指针相距固定位置一同向前移动/两个步伐不同的快慢指针。如：查找中间节点使用2倍速度的快慢指针。
function deleteNtoLast(nodeLink, n) { if (!(nodeLink instanceof Node) ||n<0)return-1; var guardNode = new Node(-1, nodeLink); // 删除头结点用 var deletNode = guardNode; var slowNode = nodeLink; var quickNode = nodeLink; for(let i = 1; i < n; i++) { quickNode = quickNode.next; if(quickNode==null)return-1; // n > nodeLink.length } while(quickNode.next!=null) { // 查找倒数第n个结点 quickNode = quickNode.next; slowNode = slowNode.next; deletNode = deletNode.next; } deletNode.next = slowNode.next; slowNode.next = null; slowNode = null; nodeLink = guardNode.next; guardNode.next = null; guardNode = null; return nodeLink; }复制代码 - 环的检测 首先，关于单链表中的环，一般涉及到以下问题：
-
给一个单链表，判断其中是否有环的存在；
-
如果存在环，找出环的入口点；
-
如果存在环，求出环上节点的个数；
-
如果存在环，求出链表的长度；
-
如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
-
（扩展）如何判断两个无环链表是否相交；
-
（扩展）如果相交，求出第一个相交的节点；
问题1
思路：设置两个快慢指针（1倍速度、2倍速度），如果有环一定会相遇（两个不同速度的人跑步一定会相遇一样）
代码：
function hasCircle(nodeLink) { var slowNode = nodeLink; var quickNode = nodeLink; while(quickNode.next) { slowNode = slowNode.next; quickNode = quickNode.next.next; if(quickNode==null) { return false; } if(slowNode === quickNode) { return true; } } return false;}复制代码 问题2
思路：
代码：
function circleEntry(nodeLink) { var slowNode = nodeLink; var quickNode = nodeLink; while(quickNode.next) { slowNode = slowNode.next; quickNode = quickNode.next.next; if(slowNode === quickNode) { break; } } // n=Tx+m var p1 = nodeLink; var p2 = slowNode; while(p1!==p2) { p1 = p1.next; p2 = p2.next; } return p1; }复制代码 问题3：
思路：1. 进入环后，就会绕着环循环走，可以记录慢指针相遇时的位置，继续走知道再次走到此位置就是一圈了。2. 从第一次相遇开始计算步伐知道第二次相遇，慢指针刚好走了一圈。
问题4：
思路:总长度=起点到入口点距离+环的长度
问题5：
思路：1. 根据上面知道环的长度，每个节点走环长度的一半步就是对面了。2. 不用上面的结果，同样设置两个快慢指针速度仍是2倍关系，则从给定点开始走当快指针回到原点时，慢指针的位置就是对面了。
问题6和7可以转换成1和2：
如图：
从listB看就是求它是否有环，和入口点。
问题：有序链表合并 思路：1. 像串糖葫芦一样从头到尾把两个链表节点从小到大串起来。2. 利用递归的方式：每比较完一个节点，剩余链表和另个链表继续执行合并。
function mergeLinks(link1, link2) { var h1 = link1; var h2 = link2; var newLink = new Node(-1,null); var h3 = newLink; while(h1!=null && h2!=null) { if(h1.data <= h2.data) { h3.next = h1; h3 = h1; h1 = h1.next; } else { h3.next = h2; h3 = h2;; h2 = h2.next; } } h3.next = h1==null?h2:h1; return newLink.next; }复制代码