什么是「链表」？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

什么是「顺序存储结构」？

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

多数高级语言的「数组」使用「顺序存储结构」，不过早期的 javascript 引擎用了「链式存储结构」。Chrome 的 V8 的数组使用了「顺序存储结构」与「链式存储结构」混合模式；大多数情况下，V8 下的数组是「顺序存储结构」，所以我们就假装 V8 的数组使用的是「顺序存储结构」吧！（-_-! 心虚）

javascript 开发需要「链表」吗？自问自答
大多数情况下 javascript 开发关心的是「数据的逻辑结构」而非「数据的存储结构」，似乎「链表」跟 javascript 开发没什么关系。But…「链表」在一些情况下能有效提升代码的性能，特别是在H5游戏的过程中。

假设有一个业务需要高频率地向一张「线性表」插入或删除节点。通常笔者会用数组表示「线性表」，因为 javascript 的数组有一系列成熟好用的 APIs （如：unshift / push / shift / pop / splice 等）可以完成插入与删除节点的操作。但是数组（顺序存储结构）的 unshift& shift & splice 的算法时间复杂度是 O(n) ，这情况可能「链表」是更好的选择。

实现双向链表

「单向链表」效率虽然高，不过局限性比较大。所以笔者想实现的是「双向链表」。双向链表插入节点或链表的算法时间复杂度为 O(4)，删除节点或链表片段的算法时间复杂度为O(2)。
双向链表的结构如下：

· 节点指针 ——「前驱」与「后继」

· 链表指针 —— 「头指针」、「尾指针」和「游标指针」

用一个匿名对象作为链表上的节点，如下伪代码：

function generateNode(data) {
return {
data: data, // 数据域
next: null, // 前驱指针
prev: null // 后继指针
} 
}

声明变量 HEAD, TAIL, POINTER & length 分别指代「头指针」，「尾指针」，「游标指针」和 「链表长度」，那么构建一个双向链表如下伪代码：

let HEAD, TAIL, POINTER, length = 0; 
// 创建一条长度为5的双向链表
[0, 1, 2, 3, 4].forEach((data, index, arr) => {
let node = generateNode(data); 
// 第一个节点
if(index === 0) {
HEAD = node; 
} 
else {
// 指定前驱后继指针
[node.prev, POINTER.next] = [POINTER, node]; 
// 最后一个节点
index === arr.length - 1 && (TAIL = node)
}
// 指向当前节点
POINTER = node; 
++length; 
}); 
// 游标指针回退到头部
POINTER = HEAD;

链表结构本身是个很简单的结构，20行左右代码可以完成双向链表数据结构的构建。

定制 APIs

上一节虽然实现了「双向链表」的数据结构，但链表还处在很原始的状态，操作起来比较麻烦，为了方便操作链表得为链表量身定做一套 APIs。

循环链表

笔者以往都是用数组来模拟循环链表，如下：

Array.prototype.next = function() { 
var cur = this[0]; 
this.push(this.shift()); 
return cur;
}
var arr = [1, 2, 3, 4, 5]; 
var count = 0; 
while(count++<20) {
console.log(arr.next());
}

有了 Chain 类后，可以直接这样写：

let circle = new Chain([1, 2, 3, 4, 5]); 
// 链表头咬尾
circle.TAIL.next = circle.HEAD; 
for(let i = 0; i < 20; ++i) {
console.log(chain.next()); 
}

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标WEB前端JavaScript频道！