js 实现链表

我们通常会在c++这类语言中学习到链表的概念，但是在js中由于我们可以动态的扩充数组，加之有丰富的原生api。我们通常并不需要实现链表结构。由于突发奇想，我打算用js实现一下：

首先我们要创建链表：

1 //创建链表
2 function CreateLinkNode(data, pre, next){
3     this.data = data;
4     this.preNode = pre;
5     if(this.preNode){
6         pre.nextNode = this;
7     }
8     this.nextNode = next;
9 }

链表最基本的要包括数据部分（data）、指向前一个的指针（preNode）、指向后一个的指针（nextNode）。

为了便于观察结果，我们再写一个打印链表的函数，挂在原型上：

1 //从模一个节点开始打印链表
2 CreateLinkNode.prototype.print = function(){
3     
4     if(this.nextNode){
5         return this.data.name + this.nextNode.print();
6     }else{
7         return this.data.name;
8     }
9 }

打印的函数由某一个节点调用，递归调用，拼装从此之后的所有节点的数据部分。

增删改查都要有吧：

 1 //从某一个节点的后面开始插入一个节点
 2 CreateLinkNode.prototype.insertNode = function(node){
 3     if(this.nextNode && this.nextNode.preNode){
 4         this.nextNode.preNode = node;
 5     }
 6     
 7     node.nextNode = this.nextNode;
 8 
 9     node.preNode = this;
10     this.nextNode = node;
11 }
12 
13 //删除某一个节点
14 CreateLinkNode.prototype.removeNode = function(){
15     this.nextNode.preNode = this.preNode;
16     this.preNode.nextNode = this.nextNode;
17 }

插入节点：在当前的节点后面插入一个节点对象。注意一下，如果当前节点是尾节点时的单独处理。

删除节点：把当前节点删除，并链接后面的节点。

还要有最不能少的反序：

 1 //反序链表
 2 CreateLinkNode.prototype.revertNode = function(){
 3     var tmp = null;//{nextNode: null, preNode: null};
 4     function revert(){
 5         if(!this.nextNode){
 6             this.preNode = null;
 7             this.nextNode = tmp;
 8             return this;
 9         }else{
10             this.preNode = this.nextNode;
11             this.nextNode = tmp;
12             tmp = this;
13             return revert.call(this.preNode);
14         }
15     }
16 
17     return revert.call(this);
18 
19 }

保证链表基本机构不变，并要返回新的头节点（原来的尾节点）。和对尾节点的单独处理。

我们来测试一下（好激动）

 1 //  start
 2 var ln1 = new CreateLinkNode({"name": "1"}, null, null);
 3 var ln2 = new CreateLinkNode({"name": "2"}, ln1, null);
 4 var ln3 = new CreateLinkNode({"name": "3"}, ln2, null);
 5 var ln4 = new CreateLinkNode({"name": "4"}, ln3, null);
 6 var ln5 = new CreateLinkNode({"name": "5"}, null, null);
 7 var lHead = ln1;
 8 ln4.insertNode(ln5);
 9 
10 console.log(lHead.print());//12345
11 
15 ln3.removeNode();
16 console.log(lHead.print());// 1245
17 ln2.insertNode(ln3);
18 console.log(lHead.print());// 12345
19 lHead = lHead.revertNode();
20 console.log(lHead.print());// 54321

大功告成！