一句话定义
链表由节点及链接组成。已知所需节点或前驱时可以局部调整链接;寻找位置和按下标访问通常需要遍历。
为什么重要
- 与数组形成鲜明对比,是理解“数据结构权衡”的最好例子。
- 双向链表是 LRU 缓存、
deque、操作系统任务队列等的基础。 - 链表题(反转、判环、合并)是面试与算法训练的经典入门。
使用边界
单链表删除一个节点通常还需要它的前驱,不能仅凭目标节点就保证 O(1)。deque 使用固定大小块组成的双向结构,也不是每个元素独占一个链表节点。
原理 / 图解
| 操作 | 数组 | 链表 |
|---|---|---|
| 按下标访问 | ||
| 头部插入/删除 | ||
| 已知节点后插入 | ||
| 内存局部性 | 好(连续) | 差(分散) |
CPython 的 collections.deque 用由固定大小块组成的双向链表实现,两端操作 :源码 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 耗时——这就是链式结构在两端操作上的优势。
常见误区
- “链表插入总是 ”:前提是已经拿到了插入位置的节点;先查找位置仍是 。
- 在 Python 里手写链表追求性能:节点是 Python 对象,开销很大;实际应用用
list或deque。 - 反转时丢失后继:先保存
nxt = cur.next再改指针。 - 忘记处理空链表和单节点等边界情况。
与 AI 开发的关系
- LRU 缓存:哈希表 + 双向链表;
functools.lru_cache的实现正是这一思路。https://github.com/python/cpython/blob/main/Lib/functools.py - KV Cache 分页管理:vLLM 的 PagedAttention 把 KV Cache 分块存放并用块表映射,思想类似“非连续存储 + 索引”。https://arxiv.org/abs/2309.06180
- 流式处理:滑动窗口、对话历史截断常用
deque(maxlen=...)。
延伸阅读
collections.deque文档:https://docs.python.org/3/library/collections.html#collections.deque- Floyd 判圈算法(维基百科):https://en.wikipedia.org/wiki/Cycle_detection
- 《算法导论》第 10 章“基本数据结构”。
理解检查
只给出单链表中一个节点的值,删除它能直接 O(1) 完成吗?
参考答案:一般不能。先定位目标和前驱的成本通常为 O(n)。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:09_linked_list.py。
配套代码与核验资料