数据结构链表详解：JavaScript 模拟与增删遍历

什么是链表

多个元素组成的列表
元素存储不连续，用 next 指针连在一起
Js 中没有链表，但可以用 Object 模拟链表

这三条里最本质的是第二条：存储不连续。数组的元素在内存里是挨着排的，所以知道首地址和下标就能直接算出任意元素的位置，一步到位。链表把这个前提去掉了，每个节点可以待在内存的任何地方，靠自己保存的一个指向下一个节点的引用把彼此串起来。

这一个改变带来了链表全部的优点和缺点。

数组与链表作用区别

数组：增删非首尾元素时需要移动元素
链表：增删非首尾元素时不需要移动元素，只需要更改 next 的指向即可

数组之所以要移动元素，是因为它必须维持「连续」这个性质。在中间插入一个值，后面所有元素都得整体后移一位给它腾地方，删除则要整体前移填补空缺，所以是 O(n)。链表没有连续性的约束，插入删除只是改几个引用的指向，是 O(1)。

但代价在查找上。数组按下标访问是 O(1)，链表做不到——它没有可以用来计算地址的连续性，想拿到第 k 个节点，只能从头顺着 next 走 k 步，是 O(n)。

所以那句「链表增删是 O(1)」需要加个前提：前提是你已经站在目标位置上了。如果给的条件只是「删除第 k 个节点」，那么找到它就要 O(n)，整体并不比数组快。链表真正占优势的是这种情形：已经持有某个节点的引用，或者在遍历过程中就地增删。反过来说，如果一份数据主要是随机读取、很少改动，数组是更好的选择，而且它内存连续，对 CPU 缓存友好，实际跑起来的常数因子小得多。

另外链表要多花空间存指针，n 个节点就是 n 个额外的引用。

顺带说一下第三条。JS 里确实没有链表类型，但用对象模拟起来非常自然，因为对象属性本来就可以持有另一个对象的引用，next 只是一个普通属性名，没有任何特殊之处。

js 模拟链表

如下代码，打印 a 通过 next 属性就能依次找到 b,c,d

这里的 val 存数据，next 存下一个节点的引用。注意最后一个节点 d 的 next 是 undefined，这就是链表的终止标志，遍历时靠它判断走到了尾部。

const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;

遍历，插入以及删除链表的操作

下面三段是链表的基本操作，各有一处值得留意的地方。

遍历用一个临时变量 p 从头节点开始，每次挪到 p.next，直到 p 为假值退出。这里必须用临时变量而不是直接改 a，否则头节点的引用就丢了，链表再也找不回来。while (p) 这个写法同时处理了空链表和走到尾部两种情况。

插入的顺序是有讲究的。看代码里插 e 那两行，先让 c.next 指向 e，再让 e.next 指向 d——但此时 d 是靠一个独立的变量名拿到的。如果链表里没有 d 这个变量，只能通过 c.next 找到它，那么这个顺序就错了：c.next 一旦被改成 e，通往 d 的唯一引用就断了，后面接不上。正确顺序是先 e.next = c.next 保存住后继，再 c.next = e。这是链表操作最经典的一个坑，改指针前先确认后继还拿不拿得到。

删除那行是把 c.next 直接接回 d，于是 e 不再被任何节点引用，自然就从链表里脱离了。JS 有垃圾回收，不需要手动释放它，只要没有其他引用指向它就会被回收。另外注意删除操作需要拿到的是待删节点的前一个节点，因为要改的是前驱的 next，这也是单链表删除时必须记住前驱指针的原因。

// 遍历链表
let p = a;
while (p) {
  console.log(p.val);
  p = p.next;
}

// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;

// 删除
c.next = d;

场景

Js 中的原型链

原型链就是一条链表，只是指针的名字叫 __proto__ 而不是 next。访问对象上的一个属性，如果自身没有，引擎就顺着 __proto__ 往上一个节点找，一直找到 Object.prototype，它的 __proto__ 是 null，这就是链表的尾部标志。整个查找过程和上面那段 while 循环遍历链表是一模一样的。

理解了这一点，几件事就好解释了：为什么原型链越长属性查找越慢——因为是线性遍历；为什么修改原型上的属性会影响所有实例——因为它们指向同一个节点，不是各存一份。

使用链表指针获取 JSON 信息

嵌套的 JSON 沿着一条固定路径取值，形式上跟遍历链表完全一致：一个游标变量，每次往下走一层。区别只是链表的下一步固定是 next，而这里下一步是路径数组给出的属性名。

下面这段代码里 p 从根对象出发，按 path 里的 a、b、c 依次深入，最终拿到 1。这个写法比 json.a.b.c 的价值在于路径是数据而不是硬编码，路径可以在运行时决定，很多配置读取和表单字段绑定的库内部就是这么做的。

实际用的时候要加防御：某一层不存在时 p 会变成 undefined，下一次取属性就抛错了。在 forEach 里加一个判断，或者改用 reduce 配合可选链，都能解决。

const json = {
  a: { b: { c: 1 } },
  d: { e: 2 },
};

const path = ['a', 'b', 'c'];

let p = json;
path.forEach(k => {
  p = p[k];
});