链表

链表：通过“指针”将零散的内存块联系起来。
常见链表结构：单链表、循环链表和双链表。

单链表

1.头结点记录链表基地址。
2.尾结点指向空地址NULL。

单链表.jpg

对比数组学习单链表

1.数组插入、删除（在保证内存数据连续性的情况下）需要数据搬移时间复杂度O(n)。
2.链表插入删除如上图所示，只需要考虑相邻指针的改变时间复杂度为O(1)。
3.随机访问某个位置的元素链表没数组高效。需要遍历结点。使劲按复杂度数组时O(1)，链表是O(n)。
4.数组采用连续的内存空间，可借助CPU的缓存机制，预读数据，这样效率更高，而链表是不连续的，没法有效预读。
5.数组申请空间过大，可能出现OutOfMemeory。过小，需要重新申请更大内存，拷贝原数组，费时。 
6.链表天然支持动态扩容没大小限制。这和数组区别很大。
7.链表更适合插入删除操作频繁的场景。
7.对链表频繁的插入删除操作会导致内存申请和释放，造成内存碎片化。在java中可能会频繁导致GC。

循环链表

在单链表基础上尾结点指针指向头结点。

循环链表.png

双向链表

对比单链表学习双向链表

1.双向链表有前驱和后继两个指针。单链表没有前驱。
2.双向链表比单链表所以内存空间更大。
3.双向链表支持双向遍历。
4.双向链表找到前驱时间复杂度O(1)。

双向链表.png

对比单链表和双向链表的插入删除操作。

删除操作（双链表有优势的地方）：

1.删除结点中“等于某个给定值的结点”。
      单链表和双链表都需要从头结点依次遍历，直到找到给定值的结点。然后删除。时间复杂度O(n)。
2.删除给定指针指向的结点。
      删除某个结点要获取其前驱结点，然而单链表需要从头遍历找到，直到p->next=q，才找到，而双链表有前驱结点的信息。所以这种情况下单链表删除时间复杂度为O(n)（查询加删除）。双链表时间复杂度则为O(1)。

总结：在某个指定结点前面删除结点双链表比单链表有很大优势。同理，插入数据也是这样。

查询操作（双链表优势的地方---特殊场景）

1.对于有序链表，进行查询操作，可以记录上次查找的位置p,每次查找都根据要查找的值与p的大小关系，觉得往前还是往后查找，能减少一半的查询量。java中linkedHashMap就用到了双向链表这种结构。

经典应用方式：页面置换算法。

LRU页面置换算法.png

实现思路：

1.基于有序单链表。
2.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
3. 如果此数据没有在缓存链表中：
   如果此时缓存未满，则将此结点直接插入到链表的头部；
   如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

总结：基于这种链表，缓存访问的时间复杂度为O(n)。引入散列表可降低时间复杂度为O(1)。基于数组也能实现。

链表相关code：https://github.com/wangzheng0822/algo/tree/master/java/06_linkedlist

链表练习题java版：

1.单链表反转：https://blog.csdn.net/lwkrsa/article/details/82015364
2.链表中环的检测：https://blog.csdn.net/wanf425/article/details/83048761
3.两个有序链表合并：https://blog.csdn.net/o9109003234/article/details/84245783
4.删除链表中倒数第n个结点：https://blog.csdn.net/qq_38640439/article/details/81842754
5.求链表的中间结点：https://www.taowong.com/blog/2018/10/20/data-strutctures-and-algorithm-05.html