链表详解：原理、代码与时间复杂度

链表解决什么问题

数组（Python 的 list）把元素存放在一整块连续内存中。读取 a[i] 是瞬间完成的，但在开头插入元素会让其余所有元素都向右移动一格，代价是 O(n)。链表避免了这种移动：每个元素都放在各自的节点里，节点之间靠引用相连，插入时只需修改几个引用。

链表是许多其他数据结构的基础：栈、队列、哈希表的桶（拉链法）、LRU 缓存，以及图的邻接表。

用大白话理解链表

把它想象成寻宝游戏：每条线索都告诉你下一条线索在哪里。你不能直接跳到第 7 条线索，必须先依次找到第 1 到第 6 条。链表本身只记得第一个节点，称为头节点（head）。最后一个节点不指向任何东西（None）。

示例演练：插入与删除

从链表 3 -> 7 -> 9 开始。我们先在 3 后面插入 5，再删除 7。

1. 创建一个值为 5 的新节点。
2. 把 new.next 指向 3 后面的节点（即节点 7）。
3. 把 node3.next 指向新节点。此时链表变为 3 -> 5 -> 7 -> 9。
4. 要删除 7，先从头节点开始遍历，找到它的前一个节点（5）。
5. 执行 node5.next = node5.next.next，这样就跳过了 7。链表变为 3 -> 5 -> 9。Python 的垃圾回收器会释放这个不可达的节点。

用 Python 实现单向链表

这个类保存头节点的引用和一个大小计数器，支持在头部和尾部添加、删除第一个匹配的值，以及迭代。

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

push_back 这里要遍历整个链表，所以是 O(n)。额外维护一个 tail 引用就能让它变成 O(1)，真实的队列实现正是这么做的。

经典操作：反转与判环

原地反转链表是最常见的链表面试题。只需遍历一遍，把每个 next 指针调转方向。

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle 用的是 Floyd 的龟兔赛跑算法（tortoise and hare）：慢指针每次走一步，快指针每次走两步。如果存在环，快指针最终会追上慢指针；如果没有环，快指针会走到 None。它只需要 O(1) 的额外内存。

时间与空间复杂度

在实际运行中，即使某些操作链表的大 O 更优，数组往往还是更快，因为数组元素在内存中紧挨着，能充分利用 CPU 缓存，而链表节点是分散的。

变体与常见错误

• 忘记处理空链表：读取 head.next 之前，一定要先检查 head is None。
• 在保存之前就覆盖了 next，导致丢失链表的其余部分（见 reverse 中的 nxt）。
• 删除第一个节点时没有更新 head，或删除最后一个节点时没有更新 tail。
• 对很长的链表使用递归：Python 默认递归深度限制约为 1000 层，所以迭代写法更安全。
• 使用哑节点（哨兵头节点）可以消除大部分特殊情况：这样每个真实节点都有前驱节点。
• 在双向链表中，每次插入和删除都必须更新四个引用；漏掉一个就会悄无声息地破坏链表。

何时使用链表，Python 里用什么

当你经常在两端或中间已持有引用的位置插入和删除，并且很少需要随机访问时，就适合用链表。例如 LRU 缓存（双向链表加哈希表）、内存分配器的空闲链表、撤销历史，或哈希表的桶。

日常 Python 代码里很少需要自己写链表。需要队列或双端队列时，用 collections.deque，它在两端追加和弹出都是 O(1)。一般的序列用 list。自己实现链表适合用于学习、面试，以及需要像 LRU 缓存那样在 O(1) 时间内拼接节点的场景。

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]