第一个 Linked List 的故事
Source: Dev.to
🙋♂️ 嗨
在这个故事中，我们将揭示链表是如何首次被用来解决由简单数组带来的数据结构挑战的。让我们开始吧。
序章：一个无序的问题
那是 1950 年代初期，计算机仍然是由真空管和穿孔卡片组成的庞大房间。最紧迫的挑战之一是 dynamic memory management——在运行时集合的大小可能变化时，如何存储一组项目。早期的机器如 ENIAC 和 Manchester Mark 1 使用固定大小的数组；每个元素占据内存中预先确定的槽位。如果程序需要的空间超过了已预留的空间，它要么崩溃，要么浪费宝贵的内存。
此时，Allen Newell（随后 Herbert A. Simon 加入）在 RAND 公司出现。他们正在开发一个模拟人类问题求解的程序，这个项目最终成为 Logic Theory Machine。他们的算法需要跟踪一个不断增长的逻辑语句列表，但他们无法预测运行时会生成多少语句。
第 1 章：洞察
在餐巾纸上草绘想法时，Newell 想象了一个 chain of boxes，每个盒子里保存一段数据以及指向下一个盒子的 pointer。他沉思道：“如果每个盒子都知道下一个盒子的位置，我们就可以在任意位置添加新盒子，而无需移动已有的盒子。” 这一概念很简单：数据结构不再是连续的内存块，而是一系列通过地址相连的节点。
他把这个想法展示给同事 Clifford Shaw，后者也在处理早期人工智能程序中的动态数据。两人一起完善了这一概念：每个节点将包含两个字段——data（实际的值）和 link（下一个节点的地址）。第一个节点称为 head，最后一个节点指向一个特殊的 null 值，以表示链的结束。
第2章：首次实现
在 1955 年，Newell、Shaw 和 Simon 为 RAND “Logic Theory Machine” 编写了一个程序，使用这一系列节点来存储推导出的定理。由于定理的数量事先无法确定，链表使程序能够在每证明出一个新定理时分配一个新节点，并将其链接到前一个节点。删除定理同样简单：只需调整前一个节点的链接，使其跳过不需要的节点。
他们用 IBM 704 的汇编语言编写的代码大致如下（为说明而简化）：
ALLOCATE NEW NODE
STORE THEOREM IN NODE.DATA
SET NODE.LINK = NULL
IF LIST IS EMPTY THEN
HEAD = NODE
ELSE
LAST.LINK = NODE
END IF
LAST = NODE该方案的优雅之处在于 O(1) 的尾部插入以及在搜索时 O(n) 的遍历——正是他们所需的权衡。
第三章：出版与传播
Newell 和 Simon 在一篇 1956 年的论文《A Logic Theory Machine》 中发表了他们的研究成果。虽然主要关注点是自动定理证明，审稿人却注意到了其中新颖的数据结构。当时并没有出现 “linked list” 这个术语；作者将其称为 “chain of records”。
大约在同一时期，Donald Knuth 当时还是研究生，在撰写关于排序算法的博士论文时遇到了这一概念。他对术语进行了正式化，在其开创性的 1968 年著作《The Art of Computer Programming》 中创造了 “linked list” 这一说法。Knuth 清晰的阐述帮助该概念在新兴的计算机科学社区中广泛传播。
第4章：链表为何重要
链表解决了早期计算机的一个根本限制：
- 动态大小 – 可以在不重新分配整块内存的情况下添加或删除节点。
- 高效的插入/删除 – 修改链表只需更新少量指针，而不必移动大量数据。
- 内存利用率 – 可以通过释放单个节点来回收未使用的内存，这在内存仅以千字节计量时尤为关键。
这些特性使得链表成为许多早期操作系统组件（进程控制块、文件分配表）的骨干，并且后来在栈、队列以及更复杂的树等数据结构中得到广泛应用。
结语：链条继续
从 1950 年代逻辑理论程序中那条简陋的节点链开始，链表已经发展成为每个一年级计算机科学学生必学的基础概念。现代语言将指针运算隐藏在优雅的抽象之后，但核心思想仍然不变：用引用连接离散的数据块，形成灵活且可扩展的链条。
所以，下次你在 Python 中向栈压入元素或遍历单向链表时，请记住你正在走同样的思路——正如 Allen Newell 和他的同事们半个世纪前所开辟的道路——一次链接，一次节点，从最简单的连接构建出越来越大的结构。
🙋♂️ 再见