波仔
⚙️ 第四章 让内存化方为圆
📄 一句话概括

数组往中间插要搬一大串，链表只要改两处线头；代价是不能随机访问——想找第 500 个，得从头爬 500 次。

📝 本节和前面几节的关系

4.5 讲的都是连续存放的容器，这一节换成【串起来放】。

一、数组的痛点在【搬】

往数组中间插一个元素，后面的元素全都要往后挪一格。 8 个元素里插在第 1 个位置，要搬 7 个；1024 个里插在正中间，要搬 512 个。 删掉中间一个也一样，后面的都得往前补。 元素越多、越靠前，这笔搬运费就越贵——而它跟【有没有找到位置】一点关系都没有。

二、链表：每个元素记住下一个在哪儿

链表的元素不必挨着放，可以散在内存各处。 它靠一条额外的信息连起来：每个节点里存着【下一个节点在哪儿】的地址。 于是数据像一根链子串起来，位置在哪里不重要，知道下一环在哪里就行。 这也正好用上了 4.3 的指针——链表是指针最出彩的地方。

三、插入和删除只改线头

往 n1 和 n2 之间插一个新节点 n4，要做的只有两件事： 把 n1 记的【下一个】改成 n4。 把 n4 记的【下一个】设成 n2。 删除反过来：把前一个的【下一个】直接跳过它，指到后一个。 所以不管链表多长，插删永远只要改两处——这是链表最大的便宜。

四、代价：随机访问没了

数组想找第 500 个，是乘一下加一下，一步到位。 链表想找第 500 个，只能从第一个开始，顺着线头爬 500 次。 而且每个节点还要额外存一个地址，比数组多占一点地方。 一句话总结取舍：插删便宜、随机访问贵。 用什么，就看你的程序更常用哪一头。

五、动手 Demo：在链表中添加和删除元素很容易

数组的麻烦在【搬】，链表的办法是【串】。 每个节点 = 数据 + 下一个节点的地址。

# 每个节点 = (名称, 数据, 下一个的名称)
before = (("n1", 10, "n2"), ("n2", 20, "n3"), ("n3", 30, None))
after = (("n1", 10, "n4"), ("n4", 15, "n2"),
         ("n2", 20, "n3"), ("n3", 30, None))
def show(c):
    return " -> ".join("%s(%d)" % (k, v, _) for k, v, _ in c)
print("插入前：", show(before))
print("插入后：", show(after))

实跑输出：

--------------------------------------------------------------------
在链表中添加和删除元素很容易
--------------------------------------------------------------------

**数组的麻烦在【搬】：** 往中间插一个，后面所有元素都得往后挪一格。
**链表的办法是【串】：** 每个元素记住下一个在哪儿，插一个只改两处线头。

  插入位置                    数组要搬动几个     链表要改几处
  ------------------------------------------------------------
  第 1 个（共 8 个）          7 个               2 处
  第 4 个（共 8 个）          4 个               2 处
  第 512 个（共 1024 个）     512 个             2 处

  用一串【节点】把链表画出来，每个节点 = 数据 + 下一个的地址：

    插入前的链：n1(10) -> n2(20) -> n3(30)
    插入 n4(15)：n1(10) -> n4(15) -> n2(20) -> n3(30)
    动的线头只有两条：n1 的下一个，和 n4 的下一个。

  代价是：**链表没法一下跳到中间。**
  想找第 500 个，数组是一步乘法，链表得从头爬 500 次。
  **插删便宜、随机访问贵——两头必有一头要付钱，这就是数据结构的取舍。**

插入只动了 n1 和 n4 两处【下一个】——数组同样位置却要搬 2 个（1024 个元素时要搬 512 个）。 代价是链表不能一下跳到中间，找第 n 个必须从头走。

30 秒实验

  1. 在纸上画 4 个节点，把第 3 个删掉，看要改哪几条线头。
  2. 想想为什么链表节点里存的地址，比数组元素多占几个字节。

常见误区

  1. 以为链表插入不用找位置。找位置仍然要爬，省下的只是搬运。
  2. 以为链表处处比数组好。按下标取数据时，数组快得多。
自测三问（点开对答案） 1. 数组插入元素的代价在哪？ —— 要把插入位置之后的元素全部向后挪一格，元素越多、位置越靠前越贵。 2. 链表插入要做几件事？ —— 改两处：前一个节点的【下一个】指向新节点，新节点的【下一个】指向原先后一个。 3. 链表的代价是什么？ —— 不能随机访问，找第 n 个必须从头逐个爬；每个节点还多存一个地址。

相关笔记