跳到主要内容

链表 (List)

问题向导：​

  • 问题1：如何实现LRU缓存淘汰算法？
  • 思路：
    • 维护一个有序的单链表，越靠近链表尾部的结点是越早之前访问的，当有一个新的数据被访问时，从链表头开始顺序遍历链表。
  • 实现：
  1. 如果在此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，可以分两种情况考虑：
    1. 如果此时缓存未满，则将该结点直接插入到链表的头部。
    2. 如果此时缓存已满，则删除链表的尾结点，将新的数据结点插入到链表的头部。
  • 优化实现：
    • 引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到O(1).
  • 其他实现：
    • 使用数组实现LRU缓存淘汰策略

扩展1：

  • 缓存利用的是空间换时间的设计思想
    • 对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化。
    • 对于消耗过多内存的程序，可以通过消耗更多时间（时间换空间）来降低内存的消耗。 扩展2：
  • 常见缓存淘汰策略
    • FIFO(First In, First Out):先进先出策略
    • LFU(Least Frequently Used): 最少使用策略
    • LRU(Least Recently Used): 最少使用策略

链表概述：​

概念：​

  • 链表是通过指针将一组零散的内存快串联在一起的一种数据结构。
    • 内存块通常被称为链表的结点，每个链表的结点除了存储数据之外，还需要记录下一个节点的地址的指针（通常称为后继指针next）

对比:​

  • 数组：需要一块连续的内存空间来存储，对内存要求比较高
  • 链表：不需要一块连续的内存空间，它通过指针将一组零散的内存块串联使用。

特点：​

  • 支持数据的查找、插入、删除操作
  • 相对与数组，链表更适合插入和删除操作、查找的效率则没有数组高。
  • 插入删除
    • 数组O(n)
    • 链表O(1)
  • 随机访问
    • 数组O(1)
    • 链表O(n)

分类：​

image

  • 单链表
  • 循环链表
  • 双向链表
  • 双向循环链表

链表详解：​

单链表：​

  • 特点：
    • 只有一个方向
    • 结点只有一个后继指针next指向后的结点
    • 头结点记录链表的基地址
    • 尾结点指针指向一个空地址NULL
  • 常用操作的时间复杂度：
    • 查找: O(n)
    • 插入 : O(1)
    • 删除: O(1)

循环链表：​

  • 特点：
    • 是一种特殊的单链表
    • 和单链表唯一的区别在我尾结点，尾结点指针指向连链表的头结点
    • 和单链表相比，优点是从链尾到链头比较方便，当要处理的数据具有环形结构特点时，就适合采用循环链表（单链表实现相对比较繁琐）。比如：约瑟夫问题。

双向链表：​

  • 特点
    • 支持两个方向
    • 每个结点不止有一个后继指针next指向后面的结点，还有前驱指针pre指向前面的结点
    • 相较于单链表，会占用更多的内存。
    • 支持双向遍历，这样也带来了 双向链表操作的灵活性。提高的数据插入和删除的效率。
  • 操作
    • 删除的情况分析：
      1. 删除结点中“值等于某个给定值”的结点；
        • 需要从链表头部依次遍历，知道找到值等于给定值的结点，O(n)，然后执行删除操作O(1)，所以时间复杂度为O(n)
      2. 删除给定指针指向的结点；
        • 此情况需要知道该结点的前驱结点，而单链表不支持获取前驱结点，故需要从头开始遍历O(n)，直到到 p->next=q，说明 p 是 q 的前驱结点。与之对比，使用双向链表操作比较高效，时间复杂度为O(1)。

双向循环链表​

  • 整合了循环链表和双向链表的特点形成了一种链表
  • 首节点的前驱指针指向尾结点，尾结点的后驱指针指向首节点。

链表代码编写技巧指南​

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

  • 指针的理解：
    • 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
  • eg:
    • p->next=q。这行代码是说，p结点中的next指针存储了q结点的内存地址。
    • p->next=p->next->next。这行代码表示，p结点的next指针存储了p结点的下下一个结点的内存地址。

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

  • eg: 单链表的插入操作
  • image
p->next = x; // 将 p 的 next 指针指向 x 结点；
x->next = p->next; // 将 x 的结点的 next 指针指向 b 结点；
  • 分析：
    • p->next 指针在完成第一步操作之后，已经不再指向结点 b 了，而 是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就 断成了两半，从结点 b 往后的所有结点都无法访问到了
  • 正确做法：
    • 先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。
  • 总结：
    • 插入结点时，一定要注意操作的顺序。
    • 删除链表结点时，也一定要记得手动释放内存空间。

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

哨兵：解决的是国家之间的边界问题，同理，在数据结构所说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

eg1: 向空链表中插入第一个结点

if (head == null) {
head = new_node;
}

eg2:单链表结点删除操作

# 删除结点 p 的后继结点
p->next = p->next->next;

# 删除链表中的最后一个结点
if (head->next == null) {
head = null;
}
  • 普通实现的方法总结：
    • 针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理

哨兵方式实现：

image

  • 引入哨兵结点，在任何时候，不管链表是否为空，head指针都会一直指向这个哨兵结点，也称这个哨兵结点的链表交带头链表。
  • 哨兵结点是不存储数据的
  • 插入排序、归并排序、动态规划都使用了哨兵的方式实现。

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

检查链表代码是否正确的边界条件有如下几个：

  • 如果链表为空时，代码是否能正常工作？
  • 如果链表只包含一个结点时，代码能否正常工作？
  • 如果链表只包含两个结点时，代码能否正常工作？
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

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

举例法和画图法：

  • 可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感 觉到思路清晰很多。比如往单链表中插入一个数据这样一个操作，我一般都是把各种情况都举一 个例子，画出插入前和插入后的链表变化，如图所示：
  • image

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

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