数据结构的世界如同一堵厚实的砖墙。

链表的砖块分散各处，连接的藤蔓自由地穿梭于砖缝之间。

Reference: Hello 算法 链表

Outline

• linked list
  • definition
    • 链表是一种通过 “引用” 连接每个节点的线性数据结构。
    • 使用链表可以有效利用计算机系统内分散在内存各处的空间。
    • 链表节点 = 节点 + 节点指针
  • Common operation
    • Initial Linked List: 建立链表分为两步，初始化各个节点对象，构建引用指向关系。
    • Insert Node: 改变两个节点引用（指针）即可插入节点。
    • Delete Node: 改变待删除节点前一个节点的指针即可。
    • Visit Node: 从头节点出发，逐个向后遍历，直至找到目标节点。
    • Search Node

Definition

链表是一种通过“引用”连接每个节点的线性数据结构。

复杂的系统运行环境下，空闲的内存空间散落在内存各处。

使用链表可以有效利用计算机系统内分散在内存各处的空间。

链表节点 = 节点 + 节点指针

• 尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为 null、nullptr、None。
• 在 C、C++、Go 和 Rust 等支持指针的语言中，上述的“引用”应被替换为“指针”。
• 链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。在相同数据量下，链表比数组占用更多的内存空间。

image.png

Java中定义链表节点。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        this.val = x;
    }
}

Common operation

Initial Linked List

建立链表分为两步：

1. 初始化各个节点对象。
2. 构建引用指向关系。

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// Step 1. 初始化各个节点
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Step 2. 构建引用指向
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

数组整体是一个变量，通常将头节点当作链表的代称。

Insert Node

想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需要改变两个节点引用（指针）即可。

img

时间复杂度 \(O(1)\)，相比之下，数组中插入元素的时间复杂度为 \(O(n)\)，在大数据量下的效率较低。

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

Delete Node

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

img

时间复杂度 \(O(1)\)，相比之下，数组中删除元素的时间复杂度为 \(O(n)\)，在大数据量下的效率较低。

/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode n0) {
	// judge parameter node is tail node or not
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

Visit Node

访问数组中的任意元素的时间复杂度是 \(O(1)\) 。

访问链表中的任意元素的时间复杂度是 \(O(n)\) 。

因为需要从头节点出发，逐个向后遍历，直至找到目标节点。

/* 访问链表中索引为 index 的节点 */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

Search Node

遍历链表，查找链表内值为 target 的节点，输出节点在链表中的索引。此过程也属于线性查找。

时间复杂度为 \(O(n)\)。

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

Linked List v.s. Array

由于数组和链表采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。

	数组	链表
存储方式	连续内存空间	分散内存空间
缓存局部性	友好	不友好
容量扩展	长度不可变	可灵活扩展
内存效率	占用内存少、内存利用率低	占用内存多、内存利用率高
访问元素	\(O(1)\)	\(O(n)\)
添加元素	\(O(n)\)	\(O(1)\)
删除元素	\(O(n)\)	\(O(1)\)

Common linked list types

• 单向链表：即上述介绍的普通链表，尾节点指向空 None 。
• 环形链表：如果我们令单向链表的尾节点指向头节点（即首尾相接），则得到一个环形链表。
• 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。更灵活占用更多内存。

/* 双向链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向后继节点的引用
    ListNode prev;  // 指向前驱节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

img

Typical applications of linked lists

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

• 栈：当插入和删除操作都在链表的同一端进行时，它表现出先进后出的的特性，对应栈；
• 队列：当插入和删除操作在链表的不同端进行时，它表现出先进先出的特性，对应队列。
• 哈希表：链地址法是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
• 图：邻接表是表示图的一种常用方式，在其中，图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常被用于需要快速查找前一个和下一个元素的场景。

• 高级数据结构（红黑树、B 树）：需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
• 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
• LRU 算法：在缓存淘汰算法（LRU）中，我们需要快速找到最近最少使用的数据，以及支持快速地添加和删除节点。这时候使用双向链表就非常合适。

循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。

• 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现。
• 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用到循环链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个循环链表，以便实现无缝播放。