开篇问题

问题：如何用链表来实现 LRU 缓存淘汰策略呢？

## 链表的作用

链表一个经典的应用场景就是LRU缓存淘汰算法；

缓存是一种提高数据读取性能的技术，在开发中有着非常广泛的应用，由于缓存的大小有限，当缓存被占满时，哪些数据应该被清理，哪些数据应该被保留？这就需要淘汰策略来决定，常见的淘汰策略有三种：先进先出策略FIFO（First In, First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）。

打个比方：假如说你买了很多书籍，但有一天发现书太多了，太占空间，你要做个大扫除。那么这个时候你会选择扔掉哪些书籍？对应一下，其实就是我们上边说的三种策略；

什么是链表？

为了理解起来更容易，我们拿数组来做对比；

相比数组，链表是一种稍微复杂一点的数据结构。从底层的存储结构上来看：数组需要一块儿连续的内存空间，堆内存的要求比较高，如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的空间的时候，即便内存的剩余总可用空间大于100MB，仍然会申请失败；而链表恰恰相反，它并不需要一块儿连续的内存空间，它通过“指针”将一组零散的内存块串联起来，所以如果我们申请100MB大小的链表，如果没有100MB连续的内存空间，且内存的剩余总可用空间大于100MB，根本不会有问题；

数组和链表的内存分布图

常见的链表结构

链表的结构五花八门，今天重点来介绍下三种最常见的链表结构，分别是：单链表、双向链表和循环链表。

单链表

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

单链表

从图中我们发现，有两个节点是比较特殊的，分别是第一个节点和最后一个节点。我们称第一个节点为头结点，最后一个节点叫做尾节点。其中头结点用来记录链表的基地址，有了它我们就可以遍历得到整条链表；而为节点特殊的地方是：指针不是指向下一个节点，而是指向一个空地址 NULL，表示这是链表上的最后一个节点；

链表的增删改查

我们在进行数组的插入、删除操作的时候，为了保持内存数据的连续性，需要进行大量的数据搬移工作，所以时间复杂度为 O(n)；而在链表中插入或者删除一个数据我们并不需要为了保持内存的连续性而搬移节点，因为链表本身的存储空间也不是连续的，所以在链表中插入和删除一个数据是非常快的；

插入数据：我们只需要将要插入位置的前一个数据单元的next指针指向插入数据的内存地址，插入数据的next指针指向下一个数据的内存地址；

删除数据：将要删除数据的前一个数据单元的next指针指向要删除数据的下一个数据单元的内存地址，然后再删除数据；

链表的插入与删除

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

链表就好比是在学校站队一样，假如我们都只知道自己后面的人是谁，如果我们想知道第k个人是谁，我们就需要从第一个人开始，一个一个的往下数。所以，链表随机访问的性能没有数组好，需要O(n)的时间复杂度；

循环链表

循环链表其实就是一种特殊的单链表，它根单链表唯一的区别就在于尾节点，上文我们提到单链表的尾节点的next指针指向空地址，表示这是最后的节点了；而循环链表的尾节点指针指向的是链表的头结点，如下图，它就像一个环一样收尾项链，所以叫做循环链表。

循环链表

和单链表相比，循环链表的优点是从链尾到连头比较方便，当要处理的数据具有环形特点时，就特别适合使用循环链表。

双向链表

单链表只有一个方向，节点只有一个后继指针next指向后面的节点。而双向链表支持两个方向，每个节点不仅有一个后继指针，还有一个前驱指针prev指向前面的节点。

双向链表

从图中我们不难看出，双向链表需要额外的两个空间来存储后继节点和前驱节点的地址。所以存储同样多的数据，双向链表占用的空间要大于单向链表。虽然内存的占用增大了，但是可以支持双向遍历，这样使得双向链表的操作更加灵活。

双向链表相比单向链表：从结构上看，双向链表可以支持 O(1)时间复杂度下找到前驱节点，也使得双向链表在某些情况下的插入和删除等操作要比单链表更加的简单高效。

在上文中我们说单向链表的时候，提到单链表的增加和删除操作的时间复杂度也是 O(1) ，但这种结果偏于理论，接下来我们通过实际的例子来分析。

删除操作

在实际开发中，从链表中删除一个数据无外乎两种情况：

  1. 删除节点中“值等于某个给定的值”的节点；
  2. 删除给定指针指向的节点；

对于第一种情况，不管是单链表还是双链表，为了查找值等于给定值的节点，都需要从头节点开始一个一个依次遍历对比，知道找到值等于给定值的节点，然后在进行删除操作；

尽管单纯的删除操作时间复杂度是O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)，根据时间复杂度分析中的加法法则，删除值等于给定值的节点对应的链表操作的总时间复杂为O(n)。

对于第二种情况，我们已经找到了要删除的节点，但是删除某个节点 q ，需要知道其前驱节点，而单链表并不支持直接获取前驱节点，所以为了找到前驱节点，我们还是要从头节点开始遍历链表，直到找到 p->next=q，说明p是q的前驱节点；

但是对于双向链表来讲，这种情况就比较有优势。因为双向链表中的节点已经保存了前驱节点的指针，不需要像单链表那样遍历。所以针对第二种情况，单链表删除的操作需要O(n)的时间复杂度，而双向链表只要O(1)的时间复杂度。

同理，如果我们希望在链表的某个节点前面插入一个节点；双向链表比单链表有很大的优势。双向链表可以再O(1)的时间复杂度搞定，而单向链表需要O(n)的时间复杂度，可以参考上边删除操尝试自己分析一下；

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

链表&数组性能对比

数组和链表的存储方式截然不同，正是因为内存存储方式的不同，它们插入、删除、随机访问操作的时间复杂度正好相反；

数组 链表
插入、删除 O(n) O(1)
随机访问 O(1) O(n)

不过在实际开发中要根据实际场景来选择具体的数据结构存储，不能仅仅通过时间复杂度来决定；

数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读取数组中的数据，所以访问效率更高；而链表在内存中并不是连续的所以对CPU缓存不友好，没办法有效预读。

数组的缺点是大小固定，已经声明就要占用整块连续的内存空间；如果声明数组过大，可能会导致内存不足，如果声明数组过小，可能会导致容量不够用，这是就需要在申请一个更大的内存空间，把原数组copy进去，非常耗时；链表本身没有大小的限制，天然支持动态扩容。虽然Java中的ArrayList也支持动态扩容，但是其本质就是当容量不足时去申请一个更大的空间去存储；

解题开篇

好了，关于链表的知识我们就讲完了。我们现在回过头来看下开篇留给你的思考题。如何基于链表实现 LRU 缓存淘汰算法？

我的思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

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

如何判断一个字符串是否是回文字符串的问题？

思路

  1. 首先用一个快指针，一个慢指针来遍历链表。快指针每次走两步，慢指针每次走一步。等到快指针遍历完链表，慢指针就正好停留在链表的中央。
  2. 将链表的后半部分进行反转。
  3. 将链表的前半部分与后半部分逐个比对。若都相同，则为回文链表，否则不是。 链表遍历的时间复杂度大约为 n/2。反转的时间复杂度为n/2。逐个比对的复杂度为n/2，所以总体的时间复杂度为O(n).而其中用于暂存的节点只有两个。因此空间复杂度为O(1)。

实现

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
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;
  }
}