循環(huán)列表僅僅是將表尾指向表頭
以下代碼說明了循環(huán)列表的初始化或颊，push和合并操作
//節(jié)點
function Node(data,next) {
this.data = data;
this.next = next;
};
//用一個節(jié)點來初始化一個循環(huán)鏈表
function NodeList(node0){
this.next = node0;
this.tail = node0;
this.tail.next = this;
}
//為循環(huán)鏈表的尾部增加一個節(jié)點
NodeList.prototype.push = function(node){
this.tail.next = node;
this.tail = node;
this.tail.next = this;
}
//合并兩個循環(huán)列表
NodeList.prototype.concat = function(list){
var list1 = list.next;
this.tail.next = list1;
this.tail = list.tail;
this.tail.next = this;
}
//遍歷一個循環(huán)列表
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
雙向鏈表在插入的時候，應(yīng)該遵循以下的思路
- 先操作要插入的節(jié)點，對其的前驅(qū)和后繼進(jìn)行賦值；
- 操作其他節(jié)點的前驅(qū)和后繼
代碼如下
//節(jié)點
function Node(data) {
this.data = data;
};
//用一個節(jié)點來初始化一個雙向不循環(huán)鏈表
function NodeList(node0){
this.next = node0;
this.prior = null;
node0.prior = this;
node0.next = null;
}
//插入節(jié)點
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;
}
//遍歷一個循環(huán)列表
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
