第二章：数组与链表

本章目标

本章比较数组和链表两种线性结构。你会理解为什么 Python list 擅长随机访问，而链表擅长在已知节点后插入。

学完后，你应该能根据查找、插入、删除的频率选择合适结构，而不是把所有序列问题都写成 list。

核心概念

数组使用连续存储，按下标随机访问是 O(1)，但在中间插入会移动后续元素，时间复杂度通常是 O(n)。

链表通过指针连接节点。已知前驱节点时插入是 O(1)，但要找到第 k 个节点必须从头走，随机访问是 O(n)。

Python 示例

Python list 可以用下标直接读取元素，这就是随机访问。

numbers = [10, 20, 30, 40]
print(numbers[2])  # 30
numbers.insert(1, 15)  # 可能移动后续元素

单向链表插入节点时只调整指针，但前提是你已经拿到插入位置。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def insert_after(node, value):
    new_node = Node(value)
    new_node.next = node.next
    node.next = new_node
    return new_node

复杂度与常见误区

list 末尾 append 平均是 O(1)，但头部 insert(0, x) 是 O(n)。不要把所有插入都当成常数时间。

链表删除节点看似 O(1)，但如果只有目标值而没有前驱节点，查找前驱仍然需要 O(n)。

本章要点

数组适合大量下标访问和末尾追加；链表适合频繁在已知位置附近插入、删除。

在 Python 实战中，内置 list 的工程价值很高。链表更多用于理解指针、合并链表、反转链表等面试和底层结构问题。