链表

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

单链表

->[data]{next}->[data]{next}->...->[data]{next}->NULL

从图中可以看出，单链表有两个结点比较特殊，分别是第一个结点和最后一个结点。

一般把第一个结点叫作 头结点，把最后一个结点叫作 尾结点。

• 其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。
• 尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL

链表要想随机访问第 k 个元素，就没有数组那么高效了

• 由于访问每个元素的概率是一样的，所以平均时间复杂度为(1+2+...n)/n=O(n)

循环链表和双向循环链表

1. 循环链表跟单链表唯一的区别就在尾结点，循环链表的尾结点指针是指向链表的头结点。

    v--------------------------------------<+
->[data]{next}->[data]{next}->...->[data]{next}

2. 双向链表

->{prev}[data]{next}<>{prev}[data]{next}<>...<>{prev}[data]{next}->NULL

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

删除给定指针指向的结点：

• 删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
• 对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。

在链表的某个指定结点前面插入一个结点

• 双向链表可以在 O(1) 时间复杂度搞定
• 单向链表需要 O(n) 的时间复杂度

3. 双向循环链表

    +------------------>--------------------------------+
    ^     v---------------------------------------------v----<+
->{prev}[data]{next}<>{prev}[data]{next}<>...<>{prev}[data]{next}

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

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

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

正确写出链表代码，包括链表反转、有序链表合并等操作

1. 技巧一：举例画图，辅助思考

插入结点x
            [x]{}               x->next = p->next; // 将x的结点的next指针指向b结点；
            /   \               p->next = x; // 将p的next指针指向x结点；
->[]{}->[a]{}x>[b]{}->[]{}
         ^
         p

注意上图的两个步骤，不能弄反了， 否则整个链表就会被断成了两半，从结点b往后的所有结点都无法访问到了。

删除结点x

            +>---------v              p->next = p->next->next; // p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址
->[]{}->[a]{}x>[x]{}->[b]{}->[]{}     free(x结点);
         ^
         p

对于不支持GC的编程语言，在删除链表结点时，也一定要记得手动释放内存空间。

2. 技巧二：利用哨兵简化实现难度

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

1
2
3
4
5

// 插入操作
if (head == null) { head = new_node;}

// 删除操作
if (head->next == null) { head = null;}

哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

为了避免上面的特殊逻辑，我们可以添加一个哨兵，保证在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。
因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

我们也把这种有哨兵结点的链表叫 带头链表。相反，没有哨兵结点的链表就叫作 不带头链表。

3. 技巧三：重点留意边界条件处理

常用来检查链表代码是否正确的边界条件有这样几个：

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

4. 技巧四：多写多练，没有捷径

5 个常见的链表操作:

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

上一篇 « 数组 下一篇 » 栈