经典链表应用场景：LRU缓存淘汰算法

缓存是一种提高数据读取性能技术，硬件设计和软件开发中都有应用：CPU缓存、数据库缓存、浏览器缓存等。缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留，需要缓存淘汰策略来决定，如：先进先出策略(first in first out)、最少使用策略LFU(least frequently used)、最近最少使用策略(least recently used)。
所以想一下，如何用链表来实现LRU缓存淘汰策略？

数组&链表：底层存储结构

数组需要一块连续的内存空间来存储，对内存的要求比较高。如果需要申请一个100MB大小的数组，当内存中没有连续的、足够大的内存空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。
链表，不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

链表结构

单链表

链表通过指针将一组零散的内存块串联在一起。我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，把这个记录下个结点地址的指针叫做后继指针next。

单链表中，有两个结点是比较特殊的，分别是第一个结点和最后一个结点。习惯性地把第一个结点叫做头结点，把最后一个结点叫做尾结点。头结点用来记录链表的基地址，通过它可以遍历得到整条链表。尾结点的指针不是指向下一个结点，而是指向一个空地址null，表示这是链表上最后一个结点。
与数组一样，链表也支持数据的查找、插入和删除操作。
在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是O(n)。而在链表中插入或者删除一个数据，不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。
针对链表的插入和删除操作，只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。

但是，链表要想随机访问第k个元素，就没有数组那么高效了。因为链表中的数据不是连续存储的，就无法像数组那样，根据首地址和下标，通过寻址公式只算计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

循环链表

循环链表是一种特殊的单链表。唯一区别在于尾结点。单链表的尾结点指针指向空地址，表示这是最后的结点；而循环链表的尾结点指针指向链表的头结点。

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环形结构特点时适合采用，比如著名的约瑟夫问题。

双向链表

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

双向链表需要额外的两个空间来存储后继节点和前驱结点的地址。所以如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。但它支持双向遍历。

双向循环链表

单链表&双向链表比较

1.删除结点中“值等于某个给定值”的结点

2.删除给定指针指向的结点

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过前面讲的指针操作将其删除。尽管单纯的删除操作时间复杂度是O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度是O(n)。
对于第二种情况，已经找到了要删除的结点，但是删除某个结点q需要知道指向它的前驱结点p，而单链表不支持直接获取前驱结点，所以为了找到前驱结点，还是要从头结点开始遍历链表，知道p->next=q，说明p是q的前驱结点。但是对于双向链表来说，因为双向链表的结点中已经保存了前驱结点的指针，就不需要像单链表那样遍历。
对于插入操作，在链表的指定结点前面插入一个结点，双向链表可以在O(1)时间复杂度搞定，而单向链表需要O(n)的时间复杂度。
除此之外，对于一个有序链表，双向链表的按值查询的效率要比单链表高一些。因为双向链表可以记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
Java中LinkedHashMap的实现中就用到了双向链表这种数据结构。

空间换时间

当内存空间充足的时候，如果我们更加追求代码的执行速度，就可以选择空间复杂度相对较高但时间复杂度相对很低的算法或者数据结构。
相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，要反过来用时间换空间的设计思路。
实际上，缓存就是利用了空间换时间的设计思想。

链表&数组：性能比较


数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高；而链表在内存中不是连续存储，所以对CPU缓存不友好，没办法有效预读。
引申：CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(具体大小这里不确定，跟CPU实现有关)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取，反之要去内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义：为了弥补内存访问速度过慢与CPU执行速度快之间的矛盾。对于数组来说，存储空间是连续的，所以在加载某个下标的时候就可以把后面的几个下标元素也加载到CPU缓存，这样执行速度就快于存储空间不连续的链表存储。
链表本身没有大小限制，天然的支持动态扩容，插入元素只需要修改指针的指向就可以，这是我理解的链表与数组的最大区别。

如何基于链表实现LRU缓存淘汰算法

思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表：
1.如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，将其从原来的位置删除，然后再插入到链表的头部。
2.如果此数据没有在缓存链表中：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则删除链表尾结点，再将新的数据结点插入到链表的头部。
这样，不管缓存有没有满，都需要遍历一遍链表，这种基于链表的实现思路，缓存访问的时间复杂度是O(n)。
引申：引入散列表(Hash Table)来记录每个数据的位置，可以将缓存访问的时间复杂度降到O(1)。

如何基于数组实现LRU缓存淘汰策略？

思路：维护一个有序的数组，越靠近数组首位置的数据越是最早访问的，当有一个新的数据被访问时：
1.如果这个数据已经存在于数组中，把对应位置的数据删掉，直接把这个数据加到数组的最后一位。时间复杂度为O(n)。
2.如果这个数据不存在这个数组中，数组还有空间的话，就把这个数据直接添加到最后一位；没有空间的话，删除掉数组的第一个元素，然后把数据插入到数组最后一个。时间复杂度为O(n)。

如果判断一个用单链表存储的字符串是回文字符串？相应的时间空间复杂度？

思路：使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。在慢指针前进的过程中，同时修改其next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
      return true;
    }

    ListNode prev = null;
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      ListNode next = slow.next;
      slow.next = prev;
      prev = slow;
      slow = next;
    }

    if (fast != null) {  //奇数个结点时
      slow = slow.next;
    }

    while (slow != null) {
      if (slow.val != prev.val) {
        return false;
      }
      slow = slow.next;
      prev = prev.next;
    }

    return true;
  }
}