一、三条判据，真测一遍

演示里把两个动作放在同一台机器上比：取第 15000 个，插到第 10000 位。 取数：数组 0.0002 毫秒，链表 1.1496 毫秒。数组快三个数量级。 插到中间：数组 0.0071 毫秒，链表 0.00060 毫秒。这次链表快一个数量级。

两个方向正好相反——这就是 3.1 那条结论的完整版：各自的长处正好是对方的短处。

二、那个 0.0071 毫秒得说明一下

演示里注了一句：数组插入测的是「插完再删掉」，把删的时间也计进去了，绝对值偏大。 为什么这么测？因为只插不删的话，数组会越来越长，重复测下去数据量就变了，几次之间没法比。 插完删掉，数组长度回到原样。 代价是绝对值不干净。但和链表比，量级差摆在那儿，不影响「谁快」这个结论。

这是一个常见的取舍： 要干净的绝对值，就固定其他条件；要可比性，就接受一点误差。关键是把它写出来，别装作没这回事。

三、到底该选哪个：一张表

把三条判据摊开，选型就没有玄学了。

最后两行容易被忽略，其实很实用。数据总数固定时，数组连「扩容」这件事都不用考虑，内存一次要够就行。 数据总数天天变时，数组每次扩容都得申请一块更大的、把老的搬过去——这个动作比插入还贵。 教材那句总结值得原样记住：没有「更好的结构」，只有「更配你用途的结构」。 选数据库、选框架，用的都是这一句。

四、环形缓冲区：只有 5 个格子，却能一直收

现在换个场景：串口一直在来数据，你只想留最近 5 条。用数组，满了怎么办？ 用链表，来一条挂一条，内存会一直涨。 环形缓冲区的做法：格子数固定，写满就从头盖。 演示里 5 个格子依次放 1 到 7。放到 6 的时候不报错，直接把最老的 1 盖掉，变成 [6, 2, 3, 4, 5]。

秘密只有一句：写指针加一，然后对长度取余。(pos + 1) % 5，走到 5 就回到 0，所以叫「环形」。 所以它永远只装得下最近 5 条，内存占用是常数，跟来了多少数据无关。这一点在嵌入式里是硬需求。

五、环形缓冲区用在哪

串口收数据、音频采样、日志只留最近 N 条、监控面板的最近曲线——这些场景的共同点是： 只要最近的，老的不重要。 反过来说，要留下全部数据的场合它一定不合适——它天生就会覆盖。 还有一个容易踩的地方：环形缓冲区满了之后， 读的人分不清「还没写过」和「已经绕回来了」。工程上通常再加一个计数器，记录总共写进来多少条。

这句话对应第 3.1 那条结论的另一面： 每个结构都有它不管的事，用之前先问「它不管的那件事我在不在乎」。

六、动手 Demo：三种摆法各测一遍，再看环形缓冲区怎么绕回来

先测数组和链表的取数与插入，各看一个方向。 再建一个只有 5 个格子的环形缓冲区，往里放 1 到 7，看它怎么盖掉最老的。

import time

N = 20000
arr = list(range(N))

class Node:
    def __init__(self, v, nxt=None):
        self.v, self.nxt = v, nxt

head = None
for v in range(N - 1, -1, -1):
    head = Node(v, head)

t = time.perf_counter(); arr[15000]; a1 = time.perf_counter() - t
t = time.perf_counter()
p = head
for _ in range(15000):
    p = p.nxt
a2 = time.perf_counter() - t
print('取第 15000 个  数组 %.4f  链表 %.4f 毫秒' % (a1 * 1e3, a2 * 1e3))

t = time.perf_counter(); arr.insert(10000, -1); arr.pop(10000); b1 = time.perf_counter() - t
t = time.perf_counter(); head = Node(-1, head); b2 = time.perf_counter() - t
print('插到第 10000 位 数组 %.4f  链表 %.5f 毫秒' % (b1 * 1e3, b2 * 1e3))

buf = [None] * 5
pos = 0
for i in range(1, 8):
    buf[pos] = i
    pos = (pos + 1) % 5
    print('put', i, '->', buf)

实跑输出：

--------------------------------------------------------------------
数组、链表、环形缓冲区：三种摆法各自的快
--------------------------------------------------------------------


  ① 三条判据，真测一遍
  --------------------------------------------------------------------

| 操作 | 数组 | 链表 |
|---|---:|---:|
| 取第 15000 个 | 0.0002 毫秒 | 1.1496 毫秒 |
| 插到第 10000 位 | 0.0071 毫秒 | 0.00060 毫秒 |

  数组按下标取，一步到位；链表插到中间，改两根绳子。各自的长处正好是对方的短处。
  ! 上面数组插入测的是「插完再删掉」，把删的时间也计进去了，所以绝对值偏大；
  但和链表比，量级差摆在那儿，不影响结论。

  ② 到底该选哪个
  --------------------------------------------------------------------

| 你的程序主要在干什么 | 选它 | 原因 |
|---|---|---|
| 老是按下标取第几个 | 数组 | 地址一算就到 |
| 老是在中间插、删 | 链表 | 改两根指针 |
| 数据总数基本不变 | 数组 | 不用预留空位 |
| 数据总数天天变 | 链表 | 来一个挂一个 |

  没有「更好的结构」，只有「更配你用途的结构」。这句话在选数据库、选框架时同样成立。

  ③ 环形缓冲区：只有 5 个格子，却能一直收数据
  --------------------------------------------------------------------
  缓冲区 5 个格子，依次放进 1 到 7：
    put 1  ->  [1, None, None, None, None]
    put 2  ->  [1, 2, None, None, None]
    put 3  ->  [1, 2, 3, None, None]
    put 4  ->  [1, 2, 3, 4, None]
    put 5  ->  [1, 2, 3, 4, 5]
    put 6  ->  [6, 2, 3, 4, 5]
    put 7  ->  [6, 7, 3, 4, 5]
  放满之后不报错，直接盖掉最老的那一个。
  下标走到头就回到 0——「加一之后对长度取余」这一句就是环形缓冲区的全部秘密。
  用在哪：串口收数据、音频采样、日志最近 N 条、监控面板的最近曲线。
  这些场景的共同点是「只要最近的，老的不重要」。

①取数那组差三个数量级，插入那组反过来差一个。两组用的是同一份数据、同一台机器。 ②插入测的是「插完再删」，所以数组的绝对值偏大。演示末尾那行说明写的就是这件事。 ③环形缓冲区那段只有两句是核心：buf[pos] = i 和 pos = (pos + 1) % 5。 取余让 pos 在 0 到 4 之间循环。 ④put 6 的时候 [6, 2, 3, 4, 5]——第 0 格被盖掉了。 整个过程没有扩容、没有报错、没有挪动任何其他格子。

30 秒实验

1. 把 % 5 改成 % 4，看输出变成什么样，想想为什么会这样。
2. 给环形缓冲区加一个 count，记录一共写进来多少条，用它区分「空」和「已经绕回来一圈」。
3. 把 buf 换成一个长度为 5 的 deque(maxlen=5)，看结果是否一样。

常见误区

1. 「环形缓冲区满了会报错。」不报错，直接盖最老的。这是设计，不是缺陷。
2. 「链表插入快，所以链表更好。」取数慢三个数量级，还多占内存。
3. 「数据总数会变就用链表。」只在「插删频繁」时才值。只是追加的话，数组的 append 也很快。

数组、链表、堆栈、队列、环形缓冲区，都是「一排」。下一节换个形状：一层一层往下分叉。

• ☐ （本篇完，下一篇 3.5 树与二叉树）

相关笔记

• 链表：单向与双向
• 为什么要学数据结构
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引