波仔
⌨️ 第三章 数值和数据的处理方法
📄 一句话概括

链表和数组是存一串数据的两条路线：数组要一整块连续内存、按下标直达；链表是节点加指针串成的串，内存散落各处、只能顺着链【顺序访问】——两者取长补短，是数据结构的第一场世纪对决。

📝 本节和前面几节的关系

3-8 的数组靠【连续内存】吃饭，这一篇的链表靠 3-14 的指针串门——它是指针的第一个正经应用，也是 3-13 哈希冲突链表的真身。回收 C++ 课 7.4 指针的语法做地基。

一、链表：节点加指针串成串

链表的每个元素是一个节点（node）：里面两样东西——数据 + 下一个节点的地址（指针）：

[A | *] --> [B | *] --> [C | None]      （单向链表）

节点散落在内存各处，靠指针互相指认；None（C 里是 NULL）表示【到头了】。要找第 5 个元素？从第 1 个顺着指针一个个数过去——这就是【顺序访问】：不能跳，只能走。

二、三种链表

种类 每个节点带什么 特点
单向链表 数据＋【下一个】指针 只能从头往尾走
双向链表 【上一个】＋【下一个】两个指针 两个方向都能走、删除节点时方便；每个节点多花 8~16 字节存回程指针
环形链表 末节点的【下一个】指回头 没有尽头，转圈走——适合【轮流】场景（操作系统轮流分配时间片、游戏回合循环）

三、世纪对决：数组 vs 链表

操作 数组 链表
按下标直达 O(1)（地址一算就到） O(n)（从头数过去）
中间插入／删除 O(n)（后面全体搬家） O(1)（接两根指针的事）
内存 必须一整块连续 散着放、见缝插针
额外开销 无 每个节点多一个指针

取长补短的现实：要【随机读】（查表、下标访问）用数组；要【频繁插删】（队列、编辑器撤销历史、音乐播放列表）用链表。Python 的 list 是动态数组（3-8）；标准库里真正的链表是 collections.deque（双向队列，双向链表思想）。

四、动手 Demo：手搓一个迷你单向链表

class Node:                # 节点 = 数据 + 指针
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node("A")              # 手工串三个节点
b = Node("B")
c = Node("C")
a.next = b
b.next = c

head = a                   # 记住头，就能走全表
while head:
    print(head.data, end=" ")
    head = head.next
print()

看到什么算成功：输出 A B C。

读结果：while head 一句就是【顺序访问】的全部——从 head 出发、顺 next 走、到 None 停。删 B 只需 a.next = c（改一根指针，节点 C 前插上、B 脱链）——不用像数组那样让后面全体搬家。

五、30 秒实验

用 Python 列表对比两种操作的代价：lst = list(range(100000))；跑 lst.insert(0, -1)（头部插入，后面 10 万个元素全体搬家）和字典／下标直达 lst[99999]。insert 一秒前后的停顿感 vs 下标读取的瞬间——两种结构的性格差异，30 秒摸得到。

六、常见误区

  1. 【链表也是连续内存，只是不能随机访问】——错。链表的节点散落各处，连续性恰恰是它牺牲掉的东西——换来的是插删不搬家。
  2. 【链表各方面比数组先进】——错。它是取舍不是升级：按下标直达 O(1) 是数组独有；链表顺序访问 O(n)，【读多写少】的场景数组碾压。
  3. 【环形链表会死循环是 bug】——看场景。它【没有 None 结尾】是设计使然，遍历要用【回到起点就停】的条件；普通遍历代码拿来就走不完——这也是【圆环】数据的第一道面试题。
自测三问（点开对答案） 1. **数组和链表最本质的结构差异？** 答：数组要一整块连续内存、按下标直达；链表节点散落内存、靠指针串起来、只能顺序访问。 2. **双向链表比单向多付出什么、换来什么？** 答：每节点多一个指回上家的指针（多占内存）；换来两个方向遍历与 O(1) 的节点删除。 3. **什么场景链表明显胜出？** 答：频繁在中间插入／删除（不需要搬家、只改指针）——如队列、播放列表、撤销历史。

相关笔记