什么是「链表科普」？
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
什么是「顺序存储结构科普」？
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。
多数高级语言的「数组」使用「顺序存储结构」，不过早期的 javascript 引擎用了「链式存储结构」。Chrome 的 V8 的数组使用了「顺序存储结构」与「链式存储结构」混合模式；大多数情况下，V8 下的数组是「顺序存储结构」，所以我们就假装 V8 的数组使用的是「顺序存储结构」吧！（-_-! 心虚）
javascript 开发需要「链表」吗？自问自答
大多数情况下 javascript 开发关心的是「数据的逻辑结构」而非「数据的存储结构」，似乎「链表」跟 javascript 开发没什么关系。But…「链表」在一些情况下能有效提升代码的性能，特别是在H5游戏的过程中。
假设有一个业务需要高频率地向一张「线性表科普」插入或删除节点。通常笔者会用数组表示「线性表」，因为 javascript 的数组有一系列成熟好用的 APIs （如：unshift / push / shift / pop / splice 等）可以完成插入与删除节点的操作。但是数组（顺序存储结构）的unshift&shift&splice的算法时间复杂度是 O(n) ，这情况可能「链表」是更好的选择。
图解链表
先看一下最简单的单向链表：
往链表里插入一个节点：
剔除链表里的节点：
往链表里插入一条链表：
剪除链表的一段切片：
通过上面的图示，可以很清晰地了解到单链表的优势：插入节点或链表片段的算法时间复杂度为O(2)；删除节点或链表片段的算法时间复杂度为O(1)
实现双向链表
「单向链表」效率虽然高，不过局限性比较大。所以笔者想实现的是「双向链表」。双向链表插入节点或链表的算法时间复杂度为 O(4)，删除节点或链表片段的算法时间复杂度为O(2)。
双向链表的结构如下：
节点指针 ——「前驱」与「后继」
链表指针 —— 「头指针」、「尾指针」和「游标指针」
用一个匿名对象作为链表上的节点，如下伪代码：
JavaScript
functiongenerateNode(data){
return{
data:data,// 数据域
next:null,// 前驱指针
prev:null// 后继指针
}
}
声明变量HEAD,TAIL,POINTER&length分别指代「头指针」，「尾指针」，「游标指针」和 「链表长度」，那么构建一个双向链表如下伪代码：
JavaScript
letHEAD,TAIL,POINTER,length=0;
// 创建一条长度为5的双向链表
[0,1,2,3,4].forEach((data,index,arr)=>{
letnode=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。数组有一系列成熟且好用的 APIs，笔者想借鉴数组的 APIs 为链表定制以下的 APIs:
NameDetailNameDetailNameDetailNameDetail
shift参见数组unshift参见数组pop参见数组push参见数组
slice参见数组splice参见数组concat参见数组reverse参见数组
sort参见数组indexOf参见数组length[属性]参见数组––
at指针定位prev指针前移next指针后退curr当前指针
first头节点last尾节点remove删除节点clone克隆链表
insertAfter插入节点insertBefore插入节点insertChainAfter插入链表insertChainBefore插入链表
HEAD[属性]头指针TAIL[属性]尾指针setHead重置头指针setTail重置尾指针
POINTER[属性]游标指针（当前位置）setPointer设置当前指针––––
上表与数组同名的 APIs，表示用法与功能与数组一样。
为了突显「链表性」笔者添加了四个insert*。insert*的作用是向主链表指定位置插入节点或链表。APIs 不小心被笔者写多了，这里就不展开介绍它们的实现过程了。有兴趣的同学可以移步：https://github.com/leeenx/es6-utils/blob/master/modules/Chain_v2.js
循环链表
笔者以往都是用数组来模拟循环链表，如下：
JavaScript
Array.prototype.next=function(){
varcur=this[0];
this.push(this.shift());
returncur;
}
vararr=[1,2,3,4,5];
varcount=0;
while(count++<20){
console.log(arr.next());
}
有了Chain类后，可以直接这样写：
JavaScript
letcircle=newChain([1,2,3,4,5]);
// 链表头咬尾
circle.TAIL.next=circle.HEAD;
for(leti=0;i<20;++i){
console.log(chain.next());
}
+群289683894领取资料，交流学习
