数组与链表

[1, , 3] 比 [1, 2, 3] 慢，原因是读每个下标都要先判断是不是 hole，是 hole 就得沿原型链去找，V8 无法生成"按偏移直接取"的机器码。map、forEach 会跳过 hole，for 循环却读到 undefined。混存类型退化的代价在热循环里最明显：变成 PACKED_ELEMENTS 后每次读都要解引用指针、做类型判断，没法整块预取。

链表在 JS 里怎么写

JS 没有指针，链表就是"对象里存另一个对象的引用"：

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

// 手工串一条 1 -> 2 -> 3
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

业务代码几乎不用链表：小数据量下 arr.splice 更快。真正需要链表的是"遍历过程中要频繁摘除节点，且已经持有节点引用"的场景。

React Fiber 是典型例子：每个 fiber 用 child、sibling、return 三根指针串成树，遍历可以在任意节点暂停、恢复。

const fiber = { child: null, sibling: null, return: null };
fiber.child = { type: 'span' };  // 第一个子节点
fiber.sibling = { type: 'p' };   // 下一个兄弟节点
fiber.return = { type: 'div' };  // 父节点，命名避开了关键字

LRU 缓存同理：哈希表存 key → 节点，双向链表维护访问顺序，命中后把节点摘下来挂到头部，全程 O(1)。

选型对照

常见误区

很多人以为"链表插入是 O(1)，所以一定比数组快"。 实际上 O(1) 的前提是已经拿到那个节点，找位置本身要 O(n)；节点散落在堆上，每跳一次都可能 cache miss，几千条以内 splice 常常反超。

很多人以为 JS 数组就是 C 的动态数组。 实际上它是对象，长度不固定、可以稀疏、可以挂任意属性（arr.foo = 1）。连续存储只是 V8 对密集整数索引的优化，出现空洞或混存就退回慢路径。

常考题型

1. 反转链表

思路：三指针原地翻转，prev 记住前驱，cur 往前走之前先把 next 存下来，否则链会断。

function reverseList(head) {
    let prev = null;
    let cur = head;
    while (cur) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

时间 O(n)，空间 O(1)。易错点：返回 prev 而不是 head，循环结束后 head 已经是尾节点。

2. 合并两个有序链表

思路：哨兵节点省掉"谁是头"的判断，双指针每次取较小的那个接在尾部。

function mergeTwoLists(l1, l2) {
    const dummy = { val: 0, next: null };
    let tail = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 || l2; // 剩下的整段直接接上
    return dummy.next;
}

时间 O(m + n)，空间 O(1)。易错点：忘记把剩余部分接上；比较要和 <= 才能保持稳定。

3. 删除链表的倒数第 N 个节点

思路：快指针先走 n + 1 步，再和慢指针一起走，快指针到头时慢指针正好停在待删节点的前驱。

function removeNthFromEnd(head, n) {
    const dummy = { val: 0, next: head };
    let fast = dummy;
    let slow = dummy;
    for (let i = 0; i <= n; i++) fast = fast.next;
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

时间 O(n)，空间 O(1)。易错点：不加 dummy 时删头节点要单独判断；快指针只走 n 步，慢指针会停在待删节点本身。

关联阅读

• 栈与队列：数组和链表都是它们的底层容器
• 哈希表：Map 底层同时用了数组（桶）和链表（冲突链）
• 树与堆：堆就是用数组存的一棵完全二叉树