数据结构与算法-链表

链表

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用。

缓存大小有限，当缓存被用满时，需要缓存淘汰策略决定数据删除和保留。常见策略有：

先进先出FIFO(First In, First Out)
最少使用策略LFU(Least Frequently Used)
最近最少使用策略LRU(Least Recently Used)

单链表

链表通过指针将一组零散的内存块串联起来使用。每个链表由结点组成，结点中除了存储数据外，还有一个指向下一个结点的后继指针。单链表如下所示：

从图中可以看出，有两个结点比较特殊：

头结点：用来记录链表的基地址
尾结点：指向一个空地址NULL，用来表示链表的结束

链表的插入和删除

链表的插入和删除都只需要考虑相邻结点的指针改变，其对应的时间复杂度是O(1). 示意图如下：

链表的随机访问

由于链表并不是一段连续的内存空间，因此不能像数组一样直接使用地址寻址找到第K个元素，只能遍历链表，因此平均时间复杂度是O(n).

循环链表

循环链表是一种特殊的单链表，单链表的尾结点指向一个NULL，循环链表不一样，是指向链表的尾结点指针是指向链表的头结点，如一个环一样首尾相连，所以叫做“循环”链表。

循环链表优点：从链尾到链头比较方便。

双向链表

双向链表指的是支持两个方向的操作，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。示意图如下：

如果存储相同的数据，双向链表要比单向链表占用更多的内存空间，但是也带来了双向链表操作的灵活性。因为双向链表可以在O(1)的时间复杂度下找到前驱结点，使得双向链表在某些情况下的插入、删除等操作都要比单链表要简单、高效。

双向链表体现了用空间换取时间的设计思想。对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以用过消耗更多的时间（时间换空间）来降低内存的消耗。

结合循环链表和双向链表的特点，就是双向循环链表：

数组 VS 链表

数组和链表是两种截然不同的组织方式，它们的插入、删除、随机访问操作的时间复杂度刚好相反：

数组使用连续的内存空间，借助CPU的缓存机制，可以预读数组中的数据，所以访问效率更高，链表由于不是连续存储，对CPU缓存不够友好，没办法有效预读。

数组需要固定空间，过大，导致内存不足，过小，满足不了需求，尽管有动态数组，但是有申请新空间和拷贝数据的操作，费时。链表本身没有大小的限制，天然地支持动态扩容。

链表的每个结点需要额外的内存空间，如果内存的使用非常严苛的情况下，使用数组更好。如果对链表频繁的插入、删除操作，会导致频繁的内存申请和释放，容易产生内存碎片，如果是Java，可能会导致频繁的GC（Garbage Collection，垃圾回收）。

链表适合插入、删除操作频繁的场景，查询的时间复杂度较高。

如何实现LRU缓存淘汰算法

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

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

不管缓存有没有满，都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度是O(n).

如何正确写出正确的链表代码

技巧一：理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄露

插入结点时，一定要注意操作的顺序，要先将插入结点x的next指针指向结点a的下一个结点b，再把结点a的next指针指向结点x，这样才不会丢失指针，导致内存泄露。

删除链表结点时，也一定要记得手动释放内存空间。

技巧三：利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

# 在链表p后面插入一个新结点
new_node.next = p.next
p.next = new_node

# 空链表插入第一个结点
if (head == null):
    head = new_node

# 链表头和中间删除
p.next = p.next.next

# 尾结点删除
if (current.next == None):
    current = None

上面的过程过于复杂，不够简洁，因此我们引入哨兵，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点，把这种带有哨兵结点的链表叫做带头链表；相反，没有哨兵结点的链表就叫做不带头链表。带头链表的示意图如下：

举例：在一个数组中查找key值的位置，代码一：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
  // 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 这里有两个比较操作：i<n 和 a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return -1;
}

代码二：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// 我举 2 个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
  // 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
  char tmp = a[n-1];
  // 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循环比起代码一，少了 i<n 这个比较操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1
    return -1;
  } else {
    // 否则，返回 i，就是等于 key 值的元素的下标
    return i;
  }
}

技巧四：重点留意边界条件处理

在处理链表时，经常用来检查链表代码是否正确的边界条件有：

如果链表为空
如果链表只有一个结点
如果链表只包含两个结点
代码逻辑在处理头结点和尾结点的时候，是否正确

技巧五：举例画图，辅助思考

利用画图将思路画出来，针对单链表插入一个结点的操作示意图如下：

技巧六：多写多练，没有捷径

链表5个常见操作：

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点

注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture

Super Agents of AI

链表

单链表