链表(Linked List)

链表由节点及链接组成。已知所需节点或前驱时可以局部调整链接;寻找位置和按下标访问通常需要遍历。

一句话定义

链表由节点及链接组成。已知所需节点或前驱时可以局部调整链接;寻找位置和按下标访问通常需要遍历。

为什么重要

  • 与数组形成鲜明对比,是理解“数据结构权衡”的最好例子。
  • 双向链表是 LRU 缓存、deque、操作系统任务队列等的基础。
  • 链表题(反转、判环、合并)是面试与算法训练的经典入门。

使用边界

单链表删除一个节点通常还需要它的前驱,不能仅凭目标节点就保证 O(1)。deque 使用固定大小块组成的双向结构,也不是每个元素独占一个链表节点。

原理 / 图解

图 1
操作 数组 链表
按下标访问 O(1)O(1) O(n)O(n)
头部插入/删除 O(n)O(n) O(1)O(1)
已知节点后插入 O(n)O(n) O(1)O(1)
内存局部性 好(连续) 差(分散)

CPython 的 collections.deque 用由固定大小块组成的双向链表实现,两端操作 O(1)O(1):源码 https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c ;文档 https://docs.python.org/3/library/collections.html#collections.deque 。

快慢指针判环(Floyd 判圈):慢指针每次走 1 步、快指针走 2 步;若有环,二者必在环内相遇。

可运行示例

手写单链表(插入、遍历、反转、快慢指针判环),并对比 list 与 deque 的头部操作(Python 3.15.0 一稿运行记录):

# 文件:examples/09_linked_list.py
# 链表:节点通过指针相连;头部插入 O(1),按下标访问 O(n)
from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    next: Optional["Node"] = None

class LinkedList:
    def __init__(self): self.head = None; self.size = 0
    def push_front(self, v):                 # O(1)
        self.head = Node(v, self.head); self.size += 1
    def find(self, v):                       # O(n)
        cur, steps = self.head, 0
        while cur:
            steps += 1
            if cur.val == v: return steps
            cur = cur.next
        return None
    def reverse(self):                       # 经典面试题:原地反转
        prev, cur = None, self.head
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        self.head = prev
    def __iter__(self):
        cur = self.head
        while cur: yield cur.val; cur = cur.next

ll = LinkedList()
for v in [3, 2, 1]: ll.push_front(v)
print("链表:", " -> ".join(map(str, ll)))
print("查找 3 走了", ll.find(3), "步")
ll.reverse(); print("反转后:", " -> ".join(map(str, ll)))

# 快慢指针判环
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False
a, b, c = Node(1), Node(2), Node(3); a.next, b.next, c.next = b, c, a
print("有环吗:", has_cycle(a), "| 普通链表有环吗:", has_cycle(ll.head))

# 标准库里的双向链表实现:collections.deque(块状链表)
from collections import deque
from timeit import timeit
lst, dq = list(range(100_000)), deque(range(100_000))
print(f"头部插入删除 1000 次: list {timeit(lambda: lst.insert(0,1) or lst.pop(0), number=1000)*1000:.1f} ms"
      f" | deque {timeit(lambda: dq.appendleft(1) or dq.popleft(), number=1000)*1000:.2f} ms")

一稿留存输出:

链表: 1 -> 2 -> 3
查找 3 走了 3 步
反转后: 3 -> 2 -> 1
有环吗: True | 普通链表有环吗: False
头部插入删除 1000 次: list 34.2 ms | deque 0.06 ms

头部插入删除:比较日志中的 list 与 deque 耗时——这就是链式结构在两端操作上的优势。

常见误区

  • “链表插入总是 O(1)O(1)”:前提是已经拿到了插入位置的节点;先查找位置仍是 O(n)O(n)。
  • 在 Python 里手写链表追求性能:节点是 Python 对象,开销很大;实际应用用 list 或 deque。
  • 反转时丢失后继:先保存 nxt = cur.next 再改指针。
  • 忘记处理空链表和单节点等边界情况。

与 AI 开发的关系

延伸阅读

理解检查

只给出单链表中一个节点的值,删除它能直接 O(1) 完成吗?

参考答案:一般不能。先定位目标和前驱的成本通常为 O(n)。

核验与复现

核验日期:2026-10-14。示例状态:运行通过。本轮日志:09_linked_list.py。

配套代码与核验资料

继续浏览基础 返回知识 →返回顶部 ↑
本篇目录
教程图解100%
教程图解