数组与链表

是什么，为什么存在

数组与 链表（linked list） 都能表示有序序列，但两者组织存储的方式不同。数组为每个元素提供一个整数位置，所有槽位在逻辑上连续。链表把每个元素放入节点，节点记录下一个节点；双向链表还会记录前一个节点。

这种表示方式决定了哪些工作可以直接完成，哪些工作必须遍历或搬移数据。给定有效索引后，数组不必访问之前的元素就能算出目标槽位。链表要从已知节点开始沿链接前进，因此到达位置 i 通常需要访问前面的每个节点。

修改操作会反转部分取舍。数组在中间插入元素时，为了保持索引顺序，需要移动后面的元素。若已经知道链表的前驱或目标节点，插入与删除只需修改固定数量的链接；若节点未知，查找成本可能成为整个操作的主要成本。

「数组」包含两种紧密相关的形式。固定数组在分配存储时确定长度。 动态数组（dynamic array） 常用作可增长向量的底层实现，它同时记录逻辑长度与容量，并在必要时分配更大的底层区域。

链表可以是单向、双向或循环结构。单向节点使用较少的链接存储，适合向前移动。双向节点为每个节点多付出一个链接，使已知节点可以脱离链表，也允许双向遍历。

队列、编辑器、调度器、缓存、邻接表和运行时集合中都会遇到这种选择。多数应用代码应先使用语言提供的标准集合，因为标准集合已经定义边界情况与迭代行为。当某项操作成为热点、对延迟敏感或占用大量内存时，底层模型仍会直接影响结果。

同一种抽象序列也可以使用双端队列、环形缓冲区、树、间隙缓冲区或分块结构。「数组还是链表」只是一套初始成本模型，并不会排除这些替代方案。选择应来自实际工作负载，而不是集合名称。

可运行示例使用 JavaScript，因为本地提供 Node 24。JavaScript Array 规定的是索引行为，不保证永久不变的原始内存布局；引擎可以切换内部表示。链表节点则是普通对象，因此示例展示的是访问路径与不变量，不承诺精确字节布局。

工作原理

对于使用固定宽度槽位的传统连续数组，元素 i 的地址可由 base + i × stride 得到。访问前部或后部的有效索引，需要的计算步骤相同。实现可以在外层执行边界检查，但不必遍历元素 0 到 i - 1。

因此，数组支持 O(1) 随机访问。读取或替换一个已知槽位同样是 O(1)。在无序数组中按值查找仍为 O(n)，因为能直接访问索引，不等于知道某个未知值位于哪个索引。

链表把导航信息与数据一起存储。它的头部标识第一个节点，每个 next 链接再标识后继节点。位置隐含在路径之中：从头部到达第四个节点，需要跟随三次链接。

图中表示的是逻辑相邻关系。数组槽位组成可按索引访问的连续序列。链式节点只要求链接有效，所以即使遍历时表现为一个序列，分配器也可能把节点放在相距很远的位置。

访问与查找

讨论访问时，必须说明使用哪种键。「取得第 500 项」已经给出索引，因此数组占优。「取得订单 A-107 的节点」则需要在无序数组或普通链表中扫描，除非另一个索引结构把订单 ID 映射到位置或节点，例如哈希映射。

两种结构的顺序遍历都是 O(n)。这个渐进结果隐藏了 缓存局部性（cache locality） ：处理器通常会一起取回相邻的数组槽位，而单独分配的节点可能需要访问互不相邻的内存。实际行为取决于元素大小、运行时表示、分配器与硬件，所以在声称具体延迟前，应测量部署环境中的实现。

二分查找需要高效访问中间位置。它在已排序数组中进行 O(log n) 次比较，而且每次都能直接跳到中点。链表不能按索引完成这些跳转，因此二分查找不会把普通链表的按位置遍历变成 O(log n)。

插入与删除

在数组索引 i 插入元素时，从 i 开始的元素需要以新索引保持原顺序。受影响槽位的数量会随尾部长度增加，因此中部与头部插入是 O(n)。删除元素会产生相应的左移。

链表插入只修改一个很小的局部范围。对于单向链表，在已知节点后插入时，先让新节点指向原后继，再让前驱指向新节点。这些链接更新是 O(1)，与链表总长度无关。

「已知节点」是关键条件。如果 API 只收到数字位置或元素值，它可能要先花 O(n) 从头部开始遍历。复杂度说明应同时包含查找与修改，不能只引用最后几次指针赋值。

从双向链表移除已知节点时，可以在 O(1) 内重新连接其前驱与后继。单向链表通常需要前驱，而不仅是目标节点，因为它必须修改前驱的 next 链接。保存节点句柄不会消除这种区别。

增长与摊还

固定数组无法原地增长到超过已分配区域。动态数组保留空余容量，因此许多追加操作只需填入下一个空槽位。容量耗尽时，它会分配更大的区域，复制或移动已有元素，然后再追加新元素。

因此，某一次触发扩容的追加可能耗费 O(n)。如果容量按几何比例增长，那么在很长的操作序列中，总复制量与追加次数成正比，从而使每次追加得到 O(1) 的 摊还复杂度（amortized complexity） 。「摊还」不表示每一次追加的延迟都是常数。

链表通常为每次插入单独分配节点，除非节点来自对象池或区域分配器。增长时它不必复制序列的其他部分，却要为每个节点支付分配管理成本和链接存储。大量小型分配的成本可能超过省下的复制成本。

头部、尾部与不变量

实用的链式集合会保存操作所需的端点。同时持有 head 与 tail 的队列，可以在尾部入队并在头部出队，两项操作都是 O(1)。若单向链表只有头部，追加到末尾就需要遍历整个链表，除非接口选择在头部插入。

空链表与单节点链表之间的转换需要明确规则。移除队列的最后一个节点后，head 与 tail 都必须为 null。向空队列添加节点时，两个端点都必须指向新节点。

对于双向链表，每条前向链接都应与相应的后向链接一致。若 a.next 是 b，则除非位于有明确约定的哨兵边界，b.previous 应为 a。每次成功插入或删除都必须让长度元数据恰好变化一次。

初步决策表

这些只是倾向，不是完整实现契约。双端队列可以避免数组头部移动，紧凑链式结构可以改善局部性，运行时也可能优化特殊情况。应阅读所选集合的文档，并分析真实访问分布。

示例

下面的示例从按位置访问开始，再展示局部插入，最后实现带有明确端点不变量的队列。每个文件都用本地 Node 24 运行，输出块来自对应进程的实际输出。

对比按位置访问的路径

数组表达式直接访问索引 3。linkedAt() 必须从 head 开始并统计访问的节点，使隐藏的遍历过程变得可见。

两种结构返回了同一个订单 ID，但完成的工作不同。链式函数为了取得位置 3，访问了四个节点；索引越大，遍历越长。它的范围检查还表明，API 必须明确负数索引的语义，不能悄悄把负数当成零。

为了保持示例简短，构造链表后没有再修改链接；节点属性本身仍然可变。生产代码应把改链操作隐藏在集合方法之后，避免调用方意外创建环或断开后半段链表。

分离查找成本与改链成本

两种集合都在 "running" 与 "done" 之间插入 "paused"。数组已经知道数字索引 2；链式版本则已经持有 running 节点，这正是常数时间插入成立的条件。

function insertIntoArray(items, index, value) {
  const shiftedSlots = items.length - index;
  items.splice(index, 0, value);
  return shiftedSlots;
}

function insertAfter(node, value) {
  const inserted = { value, next: node.next };
  node.next = inserted;
  return inserted;
}

function linkedValues(head) {
  const values = [];
  for (let node = head; node !== null; node = node.next) {
    values.push(node.value);
  }
  return values;
}

const arrayJobs = ["queued", "running", "done"];
const shifted = insertIntoArray(arrayJobs, 2, "paused");

const done = { value: "done", next: null };
const running = { value: "running", next: done };
const linkedJobs = { value: "queued", next: running };
insertAfter(running, "paused");

console.log(`array: ${arrayJobs.join(" -> ")}`);
console.log(`array indexed slots changed: ${shifted}`);
console.log(`linked: ${linkedValues(linkedJobs).join(" -> ")}`);
console.log("linked predecessor already known: yes");

array: queued -> running -> paused -> done
array indexed slots changed: 1
linked: queued -> running -> paused -> done
linked predecessor already known: yes

数组函数返回的数量表示本次调用影响的索引后缀，不描述 Node 内部采取的物理复制策略。JavaScript 的 splice() 保证有序索引行为，引擎仍可自由选择数组内部表示。在逻辑层面，这个三元素示例中有一个旧槽位改变了索引。

无论链表多长，链式插入都只赋值两个 next 引用。如果调用方给出的只是 "running"，而不是节点对象，普通链表仍需扫描才能找到前驱。可以另外建立从任务 ID 到节点的映射来消除扫描，但它会增加内存占用和一致性维护成本。

维护链式队列

这个队列同时保存两个端点和当前大小。最后一次移除会重置尾部，因此下一次入队可以从有效的空状态开始，不会连接到已经脱离队列的节点。

class LinkedQueue {
  #head = null;
  #tail = null;
  size = 0;

  enqueue(value) {
    const node = { value, next: null };
    if (this.#tail === null) {
      this.#head = node;
    } else {
      this.#tail.next = node;
    }
    this.#tail = node;
    this.size += 1;
  }

  dequeue() {
    if (this.#head === null) return undefined;
    const value = this.#head.value;
    this.#head = this.#head.next;
    this.size -= 1;
    if (this.#head === null) this.#tail = null;
    return value;
  }

}

const jobs = new LinkedQueue();
for (const job of ["thumbnail", "search-index", "receipt"]) {
  jobs.enqueue(job);
}

console.log(`next: ${jobs.dequeue()}`);
console.log(`remaining: ${jobs.size}`);
console.log(`next: ${jobs.dequeue()}`);
console.log(`next: ${jobs.dequeue()}`);
console.log(`empty: ${jobs.dequeue()}`);
console.log(`remaining: ${jobs.size}`);

next: thumbnail
remaining: 2
next: search-index
next: receipt
empty: undefined
remaining: 0

因为两个端点都可直接访问，enqueue() 与 dequeue() 只接触固定数量的链接。这里把空队列移除定义为返回 undefined；API 也可以选择抛出异常或返回带标签的结果，但如果 undefined 本身也可作为存储值，就必须明确区分两种情况。

链表不是高效队列的唯一表示。环形缓冲区使用数组存储和头尾索引，既避免反复删除头部，也保留局部性。应根据最大大小、增长方式、元素表示和目标运行时中的测量结果，在两者之间选择。

陷阱

只根据 Big-O 选择

修复方法： 记录操作比例、集合大小与延迟要求。在目标运行时中使用代表性数据做基准测试；若集合很大，还要检查分配次数或内存剖析结果。

隐藏插入前的查找

修复方法： 明确每项操作的输入是索引、值、前驱、节点句柄还是迭代器。分别报告查找与改链成本，再按调用方实际使用的 API 合并成本。

破坏端点与链接不变量

修复方法： 集中管理改链操作，并在测试中的每次修改后断言不变量。覆盖空到单节点、单节点到空、头部、尾部、中部与重复删除等转换。

用数组头部删除实现队列

修复方法： 保存头部索引，使用环形缓冲区或双端队列，或者使用带尾部的链式队列。应按测量得到的策略偶尔压缩索引缓冲区，不要在每次出队时移动元素。

假定所有语言的数组都有同一种物理布局

修复方法： 区分抽象索引接口与具体实现。契约需要定宽数字存储时使用类型化数组，查阅运行时文档，并测量生产环境中的确切元素形状。

保留失效节点句柄

修复方法： 让节点句柄保持不透明，使脱离节点失效或留下明确标记，并在同一个修改边界内更新索引。测试对已删除句柄执行第二次操作，并规定它应该拒绝还是不做任何事。

延伸阅读

• ECMAScript 语言规范：Array 对象
• MDN Web Docs：Array
• V8：元素类型
• NIST 算法与数据结构词典：数组
• NIST 算法与数据结构词典：链表