JavaScript数据结构4——循环列表和双向链表

循环列表仅仅是将表尾指向表头
以下代码说明了循环列表的初始化，push和合并操作

//节点
function Node(data,next) {
    this.data = data;
    this.next = next;
};
//用一个节点来初始化一个循环链表
function NodeList(node0){
    this.next = node0;
    this.tail = node0;
    this.tail.next = this;
}
//为循环链表的尾部增加一个节点
NodeList.prototype.push = function(node){
    this.tail.next = node;
    this.tail = node;
    this.tail.next = this;
}
//合并两个循环列表
NodeList.prototype.concat = function(list){
    var list1 = list.next;
    this.tail.next = list1;
    this.tail = list.tail;
    this.tail.next = this;
}
//遍历一个循环列表
NodeList.prototype.ergodic = function(){
    var node = this.next;
    while(node!=this){
        console.info(node.data);
        node = node.next;
    }
}
var list1 = new NodeList(new Node(1,null));
list1.push(new Node(2,null));
list1.push(new Node(3,null));
list1.push(new Node(4,null));
var list2 = new NodeList(new Node(5,null));
list2.push(new Node(6,null));
list2.push(new Node(7,null));
list2.push(new Node(8,null));
list1.concat(list2);
list1.ergodic();

输出如下

1
2
3
4
5
6
7
8

双向链表在插入的时候，应该遵循以下的思路

1. 先操作要插入的节点，对其的前驱和后继进行赋值；

• 操作其他节点的前驱和后继

代码如下

//节点
function Node(data) {
   this.data = data;
};
//用一个节点来初始化一个双向不循环链表
function NodeList(node0){
   this.next = node0;
   this.prior = null;
   node0.prior = this;
   node0.next = null;
}
//插入节点
NodeList.prototype.insert = function(j,node){
   var point = this.next;
   if(j<1){
       return 1;
   }
   for (var i = 1; i < j; i++) {
       point = point.next;
   }
   node.next = point;
   node.prior = point.prior;
   point.prior.next = node;
   point.prior = node;
}
//遍历一个循环列表
NodeList.prototype.ergodic = function(){
   var node = this.next;
   while(node!=null){
       console.info(node.data);
       node = node.next;
   }
}
var list1 = new NodeList(new Node(1));
list1.insert(1,new Node(2));
list1.insert(1,new Node(3));
list1.insert(2,new Node(4));
list1.ergodic();

输出如下

3
4
2
1