链表

链表（Linked List）是什么

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

生活中的类比

类比1：寻宝游戏

  • 每个地点有一张纸条
  • 纸条上写着下一个地点的地址
  • 你要按顺序一个一个找下去

类比2：火车车厢

  • 每节车厢装着货物（数据）
  • 车厢之间用挂钩连接（指针）
  • 火车头就是链表的头节点

链表的基本结构

节点（Node）

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # 节点存储的数据
        self.next = next    # 指向下一个节点的指针

链表示意图

1
2
3
4
5
6
单向链表：
[数据|指针] → [数据|指针] → [数据|指针] → None
  节点1        节点2        节点3

具体例子：
[1|*] --> [2|*] --> [3|*] --> None

为什么需要链表？

数组的缺点

1
2
3
4
5
6
7
8
# 数组（Python列表）在内存中是连续的
arr = [1, 2, 3, 4, 5]

# 在中间插入元素很慢
arr.insert(2, 99)  # 需要移动后面的所有元素 O(n)

# 删除中间元素也很慢
arr.pop(2)  # 同样需要移动元素 O(n)

链表的优点

1
2
3
4
5
6
7
8
9
10
11
12
# 链表在内存中是分散的
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3

# 在中间插入很快
new_node = ListNode(99)
new_node.next = node2  # 新节点指向node2
node1.next = new_node  # node1指向新节点
# 只需要修改指针 O(1)

链表的类型

1. 单向链表

每个节点只有指向下一个节点的指针。

1
head → [1|*] → [2|*] → [3|*] → None

2. 双向链表

每个节点有指向前一个和后一个节点的指针。

1
None ← [*|1|*] ↔ [*|2|*] ↔ [*|3|*] → None

3. 循环链表

最后一个节点指向第一个节点。

1
2
3
  ┌─────────────────────┐
  ↓                     │
[1|*] → [2|*] → [3|*] ─┘

链表的基本操作

创建链表

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
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 方法1：一个一个创建
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3

# 方法2：链式创建
head = ListNode(1, ListNode(2, ListNode(3)))

# 方法3：从列表创建
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

head = create_linked_list([1, 2, 3, 4, 5])
# 比较链表某个元素的大小
if head.val == head.next.val
# 比较两个位置是不是链表中的同一位置
if head.next is head

遍历链表

1
2
3
4
5
6
7
8
def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=" → ")
        current = current.next
    print("None")

# 输出：1 → 2 → 3 → 4 → 5 → None

插入节点

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
# 在开头插入
def insert_at_beginning(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # 新节点成为新的头

# 在结尾插入
def insert_at_end(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head

# 在指定位置插入
def insert_at_position(head, val, position):
    if position == 0:
        return insert_at_beginning(head, val)
    
    new_node = ListNode(val)
    current = head
    for _ in range(position - 1):
        if not current:
            raise IndexError("位置超出范围")
        current = current.next
    
    new_node.next = current.next
    current.next = new_node
    return head

删除节点

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
34
35
36
# 删除第一个值为val的节点
def delete_node(head, val):
    if not head:
        return None
    
    # 如果要删除的是头节点
    if head.val == val:
        return head.next
    
    current = head
    while current.next and current.next.val != val:
        current = current.next
    
    if current.next:
        current.next = current.next.next
    
    return head

# 删除指定位置的节点
def delete_at_position(head, position):
    if not head:
        return None
    
    if position == 0:
        return head.next
    
    current = head
    for _ in range(position - 1):
        if not current.next:
            raise IndexError("位置超出范围")
        current = current.next
    
    if current.next:
        current.next = current.next.next
    
    return head

链表 vs 数组

操作 数组 链表
访问第i个元素 O(1) O(n)
在开头插入 O(n) O(1)
在结尾插入 O(1)* O(n)
在中间插入 O(n) O(1)
删除元素 O(n) O(1)
内存使用 连续，较少 分散，每个节点多一个指针
缓存友好 是 否

*Python列表是动态数组，结尾插入平均O(1)

常见算法题示例

1. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def reverse_list(head):
    prev = None
    current = head
    
    while current:
        next_temp = current.next  # 保存下一个节点
        current.next = prev       # 反转指针
        prev = current            # 移动prev
        current = next_temp       # 移动current
    
    return prev  # 新的头节点

# 1 → 2 → 3 → None
# 变成 3 → 2 → 1 → None

2. 检测环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head      # 慢指针，每次走一步
    fast = head.next # 快指针，每次走两步
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

3. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def merge_two_lists(l1, l2):
    dummy = ListNode(0)  # 虚拟头节点
    current = dummy
    
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # 连接剩余部分
    current.next = l1 or l2
    
    return dummy.next

4. 找中间节点

1
2
3
4
5
6
7
8
9
def middle_node(head):
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow  # 奇数长度返回中间，偶数返回第二个中间节点

5. 判断是否有环形

1
2
3
4
5
6
7
8
9
10
# 如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环

链表的优缺点总结

优点

  • ✅ 动态大小，不需要预先分配
  • ✅ 插入和删除快（O(1)），只需要修改指针
  • ✅ 内存利用灵活，不需要连续空间

缺点

  • ❌ 随机访问慢（O(n)），必须从头遍历
  • ❌ 额外内存开销（每个节点需要存储指针）
  • ❌ 缓存不友好（节点在内存中分散）

实际应用场景

  1. 实现栈和队列
  2. LRU缓存（使用双向链表）
  3. 文件系统（FAT文件系统）
  4. 浏览器历史记录（双向链表）
  5. 音乐播放列表（循环链表）
  6. 图的邻接表表示

链表是数据结构的基础，理解它对学习更复杂的数据结构（树、图等）很有帮助！