引言
链表是一种线性表结构，其特点是非顺序存储，可充分利用碎片化的空闲内存。链表中的元素称为结点，结点通过逻辑指针维护相邻结点间的位置关系。 链表作为基础数据结构之一有多种形式：单链表、循环链表、双向链表及双向循环链表、跳表等。
带头单链表
从上图可见，链表中每个结点包含数据域和指向下一个结点的指针域。比较特别的是开头和结尾两个结点。我们习惯上把开头结点叫头结点，结尾结点叫尾结点。其中头结点中有个头指针，头指针中存有链表结构遍历的基地址，是链表能够遍历的前提。而尾结点指向下一个结点的指针域是空地址NULL。
单链表常规操作：
链表反转：就是将原结点的next指针都统一指向其前驱结点。
a、双指针迭代法：指针法就是利用两个指针不断的将结点的next指针设置为其前驱结点和不断重置前驱结点的过程。
第一次迭代，currentNode结点指向第一个结点，其prev指针此时指向null。
首次迭代
第二次迭代，currentNode指针后移一位，指向结点2；prev指针也后移一位指向结点3。
第二次迭代
第三次迭代，currentNode指针再次后移一位，指向结点1；prev指针后移一位指向结点2，终止迭代。
最后一次迭代
b、头插法：新建头结点（next指向null的结点），迭代链表结点，将每个结点设置为头结点的next，将头结点之前的next结点，设置为当前结点的next。简单来说，头插法就是将新增的结点插入到头结点和其后续结点之间，从而组成一个新的链表。
步骤1：新建头结点（next指针指向null的结点），首次迭代原始链表，并将原始链表第一个结点3，插入到头结点。
首次添加结点
步骤2：迭代原始链表，将第二个结点2，插入到头结点和结点3之间。
第二次添加结点
步骤3：迭代原始链表，将第三个结点1，插入到头结点和结点2之间，迭代结束。
最后一次添加结点
步骤4：反转后的新链表
最终链表
c、递归法：递归实现可以看做是逆向的迭代调用，或者看做是嵌套函数调用。
链表中环的检测：只要后续结点与某个前驱结点一致，说明链表中有环存在。
快慢双指针法：如果有环存在，则两个指针势必会相遇；否则快指针遍历结束。如下图，链表中有环存在，快慢指针在第三次链表迭代后相遇。
链表中环检测
删除倒数第N个节点：将链表反转，删除正数第n个元素后再次反转。
代码实现，GitHub地址：https://github.com/SolodanceMagicq/algorithm_practice/blob/master/src/algo/java/linkedlist/LinkedListAlgo.java
链表与数组性能大比拼
链表VS数组
核心应用
如何基于链表实现缓存LRU淘汰策略？
维护一个有序单链表，越早访问的元素越靠近链表的尾部存储，当有元素访问时，顺序遍历链表。
1、如果当前元素已经在缓存链表中了，则先遍历得到当前元素对应的结点，再将其从缓存中删除，然后将其插入到链表头部。
2、如果当前元素不在缓存链表中，则分两种情况：
a、 当前缓存未满，直接将当前元素插入到链表头部。
b 、当前缓存已满，则链表尾结点删除，将当前元素插入到链表头部。
代码实现，GitHub地址：https://github.com/SolodanceMagicq/algorithm_practice/blob/master/src/algo/java/linkedlist/LRUSingleLinkedList.java
JDK的集合类LinkedList
LinkeList是一个基于双向链表实现的集合，同时实现了双端队列，使其具备了队列和栈的特点。采用空间换时间思想，减少元素搜索的时间复杂度。实现细节详见《ArrayList&LinkedList源码分析》https://www.jianshu.com/p/8f94e7694886
Redis中的有序集合
Redis的有序集合即是跳表实现。跳表是一个由链表+多级索引组成的动态数据结构。其查询、插入、删除操作的时间复杂度均为O(logn)，可实现精确查找、按区间查找等特性。比较值得一提的是传统意义上二分查找只能应用在顺序存储结构（数组）的有序数列上，像链表这样的非顺序的存储结构，通过多级索引巧妙的利用空间换性能（空间复杂度为O(n)）实现了在查询操作上，类似数组的二分查找的时间复杂度O(logn)。
跳表索引动态更新：作为一种动态数据结构跳表是通过“随机函数”来维护索引与原始链表大小的平衡，也就是说如果链表中结点多了，索引结点也相应的增多，避免复杂度退化，以及查找、插入、删除的性能下降。相对于红黑树、AVL树这样的平衡二叉树，是通过左右旋的方式保持左右子树的大小平衡。
流水线设计模式
PipeLine
设计思路：将一整件事情，分成多个流水线Line x ，每条流水线是由A、B、C、D、E等多个结点构成的一条单链表。其中链表的结点也称为流水线的处理环节，且前一个结点的输出是后一个结点的输入。流水线这个复合结点，负责设置并启动线上的各环节结点，处理任务。这样整个事情，横向上切分为三条线并发处理，纵向又被切分为N个阶段。每个阶段由N(流水线条数)个相同的处理任务，将各阶段的任务统一交由一个固定线程数的线程池处理。虽然横向上每个流水线的执行效率固定（各环节均要等待其前面的环节数据到来才开始处理自己的事情）；但如果流水线数量多，各环节同类任务的处理效率就有了提升。因此流水线模式适合将大的问题拆分成大量流水线处理数据的场景，如果流水线数量少，各环节同类任务少，则整体性能体现不明显。
总结
链表和数组都是非常基础的线性表结构。
数组支持随机访问特性，可以充分利用CPU缓存行，通过寻址公式来高效访问内存中的元素时间复杂度是O(1)，但由于数组要维护物理存储空间连续性，在大量插入、删除元素后迁移数据，时间复杂度是O(n)。
链表不需要维护连续的内存空间，可以充分利用碎片化的空闲内存，但失去了对CPU缓存的支持。通过逻辑指保持相邻结点间的位置关系，因此只能从头遍历查找定位元素，时间复杂度是O(n)。但删除和插入操作不需移动元素，只是改变相邻元素的指针，时间复杂度是O(1)。
随着对链表的扩展及基于链表衍生的新的数据结构，像双向链表、跳表等，都是采用空间换性能的方式，来降低链表的查询复杂度。
网友评论