一、数据一样，摆法不一样

演示里造了两万个数：0 到 19999。装的東西完全相同，一个不多一个不少。 摆法一：数组。一片连号的内存，第几个就住在第几格。 摆法二：链表。每个数单独住，身上拴一根绳子，指向下一个数在哪儿。

差别只在「它们怎么挨着」——一个挨着住，一个各住各家靠绳子串着。就这一点差别， 后面所有结论都是它的后果。 教材说常见的数据结构有好几种，演示里挑的是最典型的两种：数组和链表。 先把这两个摆明白，其他都是它们的变种或组合。

二、取第 10000 个：一步算出，还是数一万次

数组取第 10000 个：首地址加 10000 乘 4，一次乘法就得到地址，直接去拿。跟数组有多长完全无关。 链表没有这个本事。它只知道「头在哪儿」，第 10000 个在哪儿得顺着绳子数过去，数到第 10000 根才算到。 实测：0.0002 毫秒对 0.7436 毫秒，差 3718 倍。

这个差距的道理，第 2 章 2.4 已经埋过伏笔：数组的地址是算出来的，不是找出来的。能算的就不用找。 3718 倍这个数不必记，要记的是它的性质：它跟数据量成正比。两万条差三千多倍， 二十万条就差三万多倍。

三、往最前面插一个：结论整个反过来了

现在换个动作：在最前面插一个新的。 数组要把后面两万个全部往后挪一格——因为它们是连号住的，前面挤进一个，后面全得让位。 链表只做一件事：新节点的绳子指向原来的头，然后头换成新节点。两根绳子，完事。

实测：0.0081 毫秒对 0.00060 毫秒，反过来差 14 倍。 注意这两个数：取数时数组快 3718 倍，插入时链表快 14 倍。 同一个结构，在这个动作上赢，在那个动作上就输。

四、为什么插入只差 14 倍，比想象的小

按道理数组要挪两万个格子，链表只改两根绳子，差距该像取数那样悬殊。只差 14 倍，是个值得说明的数。 原因是 Python 的 list 底层就是 C 数组，那两万个格子是交给 C 一次性搬的， 不在 Python 里一个循环一个循环地挪。 换句话说：慢动作确实发生了，但执行它的不是 Python。换成 C 手写数组或者 Java 的定长数组， 这个差距会明显得多。

结论不变，量级会变——这句话在本课要反复出现。任何「快多少倍」的数，都得连环境和实现一起说。 所以演示里那行提醒很重要：这里比的是「谁挪得少」，不是「哪台机器快」。

五、没有最快，只有最配

到这里可以立这一章的结论了：「快」没有绝对答案。同一份数据，取数快的地方，插入就慢， 反过来也一样。 所以选结构之前先问一句：我的程序主要在对这批数据干什么？是天天按下标取，还是天天在中间插删？ 这个问法不只适用于数据结构。 选数据库、选框架、选缓存，用的都是同一个问法：我的主要动作是什么，它擅长什么。

后面五节会把这张地图补全：堆栈队列管「按什么顺序进出」，链表管「插删」，树管「层级」， 图管「网状关系」。

六、动手 Demo：同一批数，数组和链表各测一遍

造两万个数，分别用数组和链表存起来，数据一个字都不差。 先测「取第 10000 个」，再测「往最前面插一个」，看两次谁快。 计时用的是同一台机器、同一段代码，只换数据结构。

import time

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

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

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

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

t = time.perf_counter(); arr.insert(0, -1); b1 = time.perf_counter() - t
t = time.perf_counter(); head = Node(-1, head); b2 = time.perf_counter() - t
print('插到最前面   数组 %.5f 毫秒  链表 %.5f 毫秒' % (b1 * 1e3, b2 * 1e3))

实跑输出：

--------------------------------------------------------------------
为什么要学数据结构：同一批数据，三种摆法
--------------------------------------------------------------------


  ① 数据一样，摆法不同
  --------------------------------------------------------------------
  同一批数：0 到 19999，共 20000 个
  摆法一：数组（一片连号内存）
  摆法二：链表（每个数挂一根绳子，串下一个）
  数据完全一样，装的东西也一样。差别只在「它们怎么挨着」。

  ② 取第 10000 个，差多少
  --------------------------------------------------------------------

| 操作 | 数组 | 链表 | 倍数 |
|---|---:|---:|---:|
| 取第 10000 个 | 0.0002 毫秒 | 0.7436 毫秒 | 3718 倍 |

  数组知道第 10000 个在哪儿：首地址加 10000 乘 4，一步算出来。链表不知道，只能从头一个一个数过去。

  ③ 往最前面插一个，反过来
  --------------------------------------------------------------------

| 操作 | 数组 | 链表 | 倍数 |
|---|---:|---:|---:|
| 插到最前面 | 0.0081 毫秒 | 0.00060 毫秒 | 14 倍 |

  插入时数组要把后面 20000 个全部往后挪一格；链表只把新节点的绳子搭到老头上，一次就完。
  ! 这里只差 14 倍，比想象的小。
  原因是 Python 的 list 底层是 C 数组，挪那两万个格子由 C 一次性搬完，比在 Python 里循环快得多。
  换成 Java 或 C 手写数组，差距会明显得多——结论不变，量级会变。
  所以「快」没有绝对答案：同一个结构，取数快的地方，插入就慢，反过来也一样。
  数据结构的全部意义就在这句取舍里。

①数组那边取第 10000 个只有一句 arr[10000]，没有循环。链表那边是一个走一万步的循环。 这个形状上的差别，比任何数字都更能说明问题。 ②插入那一行数组用的是 insert(0, -1)，内部要挪两万个格子； 链表只是 Node(-1, head)，把新节点挂到老头上。 ③两组数都是跑一次的结果，只看量级，不当精确值。 重跑一遍数字会有出入，但 3718 倍和 14 倍这两个量级不会翻。 ④插入只差 14 倍的原因写在演示末尾：Python 的 list 底层是 C 数组，挪格子是 C 在干。 这句话不写，读者会以为链表白赢了。

30 秒实验

1. 把 N 从 20000 改成 200000，看两个倍数各变成多少，验证「差多少倍跟数据量成正比」。
2. 再测一个动作：取最后一个（数组是 arr[-1]，链表要走满全程），看差多少倍。
3. 想一下你手上哪个程序是「天天按下标取」的，哪个是「天天在中间插删」的。

常见误区

1. 「链表比数组高级。」各有一半的活干得比对方快。取数数组赢，插删链表赢。
2. 「数组插入慢是因为 Python 慢。」Python 的 list 底层是 C 数组，挪格子由 C 完成，已经算快了。
3. 「快多少倍是固定的。」跟数据量、语言、实现都有关。结论（谁快）稳定，量级会变。

从下一节起一个个看具体结构。第一个最像日常生活：桌上摞书、收银台排队。

• ☐ （本篇完，下一篇 3.2 堆栈与队列）

相关笔记

• 堆栈与队列
• 数组与下标
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引