数组和链表

数组和链表是存储有序元素序列的两种基本方式：数组将元素存储在连续内存中，以实现常数时间索引访问，而链表通过指针将元素链接起来，以实现廉价的插入和删除。

Definition

数组将元素存储在按位置索引的连续内存位置中，允许常数时间随机访问；链表将元素存储在单独的节点中，每个节点都包含对下一个（以及可能的前一个）节点的引用，允许在给定节点引用的情况下进行常数时间插入或删除。

Scope

本主题涵盖线性、基于序列的结构及其上构建的抽象数据类型——静态和动态数组、单向和双向链表，以及栈和队列ADT。它对比了它们的访问、插入和删除成本，涵盖了动态数组的重新调整大小及其摊销分析，并解释了内存布局后果，例如缓存局部性。它不包括散列表和搜索树中涵盖的关联和层次结构。

Core questions

• 连续（数组）存储何时优于指针链接（列表）存储？
• 动态数组如何通过偶尔的重新调整大小实现摊销常数时间追加？
• 数组与链表在插入、删除和访问方面的成本权衡是什么？
• 栈和队列是如何在这些结构之上实现的？
• 内存布局如何通过缓存行为影响实际性能？

Key concepts

• 连续内存
• 索引访问
• 动态数组调整大小
• 单向和双向链表
• 栈（LIFO）
• 队列（FIFO）
• 摊销成本
• 缓存局部性

Key theories

随机访问与顺序链接

数组支持O(1)索引访问，但在中间插入或删除为O(n)，而链表在给定节点的情况下支持O(1)拼接，但按位置访问为O(n)；正确的选择取决于操作组合。

动态数组的摊销增长

当动态数组满时将其容量加倍，会偶尔执行O(n)的复制操作，但通过聚合或势能法，在任何操作序列中，每次追加的摊销成本为O(1)。

Clinical relevance

数组和列表几乎是每个程序的基石：动态数组实现了大多数语言中的默认列表/向量类型，队列是调度和广度优先搜索的基础，栈是函数调用管理和表达式求值的基础，而数组与列表的权衡是影响性能的常规实际设计决策。

History

数组是最早的数据结构之一，存在于第一批编程语言中，而链表则是在1950年代后期为符号和列表处理（尤其是在Newell、Shaw和Simon的IPL以及后来的Lisp中）引入的。高德纳（Knuth）在《计算机程序设计艺术》中对它们的系统处理确立了其规范分析。

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

如果数组支持快速随机访问，为什么还要使用链表？

链表在给定节点引用的情况下，允许在常数时间内插入或删除，而无需移动其他元素，这是数组在中间无法做到的。当序列频繁变化且不需要按位置随机访问时，链表非常有用。

如果调整大小会复制所有内容，为什么数组追加被认为是常数时间？

调整大小很少发生，因为容量通常会翻倍，因此在n次追加操作中，总的复制工作量与n成比例。分摊到所有追加操作中，即使单个调整大小是O(n)，每次追加的摊销成本也是常数。