雙向鍊錶和普通鍊錶的區別在於，在鍊錶中，一個節點只有鏈向下一個節點的鏈接，而在雙向鍊錶中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。 雙向鍊錶提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以存取一個特定節點的下一個或前一個元素。在單向鍊錶中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鍊錶的一個優點。本文主要介紹JavaScript資料結構之雙向鍊錶與雙向循環鍊錶的實作。
雙向鍊錶：單向鍊錶只能向一個方向遍歷鍊錶節點，而在節點指標域中增加了前向指標的雙向鍊錶，則可以向著兩個方向遍歷節點。這使得雙向鍊錶也可以在任何一個節點遍歷整個鍊錶。
function DoublyLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = Node(element),
current,
previous;
if(!head){
head = node;
tail = node;
}else{
current = head;
while(current){
previous = current;
current = current.next;
}
node.next = current;
current.prev = node;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}
this.insert = function(position,element){
if(position > -1 && position < length){
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if (position === length -1){
current = tail;
current.next = node;
node.prev = current;
}else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if (position === 0) {
head = current.next;
if(length === 1){
tail = null;
}else{
head.prev = null;
}
}else if(position === length - 1){
current = tail;
tail = current.prev;
tail.next = null;
} else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
};
length-- ;
return current.element;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous;
if(current.element === element){
head = current.next;
}
previous = current;
current = current.next;
while(current){
if (current.element = element) {
previous.next = current.next;
current.next.prev = previous;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if (length === 0) {
return false;
};
var current = head,
previous;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(current){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if (current.element === element) {
return index;
};
current = current.next;
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '';
while(current){
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
};
}雙向循環鍊錶：將雙向鍊錶的頭尾指標相連，就構成了雙向循環鍊錶。這種鍊錶從任一節點都可以同時向兩個方向進行節點遍歷，查詢節點的速度也是最快的。
/*双向循环链表*/
function DoublyCircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null;
};
var length = 0,
head = null,
tail = null;
this.append = function(element){
var node = new Node(element),
current,
previous;
if (!head) {
head = node;
tail = node;
head.prev = tail;
tail.next = head;
}else{
current = head;
while(current.next !== head){
previous = current;
current = current.next;
}
current.next = node;
node.next = head;
node.prev = current;
};
length++;
return true;
};
this.insert = function(position, element){
if(position >= 0 && position <= length){
var node = new Node(element),
index = 0,
current = head,
previous;
if(position === 0){
if(!head){
node.next = node;
node.tail = node;
head = node;
tail = node;
}else{
current.prev = node;
node.next = current;
head = node;
node.prev = tail;
}
}else if(position === length){
current = tail;
current.next = node;
node.prev = current;
tail = node;
node.next = head;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
current.prev = node;
node.next = current;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
index = 0,
previous;
if(position === 0){
current.next.previous = tail;
head = current.next;
}else if(position === length - 1){
current = tail;
current.prev.next = head;
head.prev = current.prev;
tail = current.prev;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return true;
}else{
return false;
}
};
this.remove = function(element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck === 0){
current.next.prev = tail;
head = current.next;
}else{
current.next.prev = previous;
previous.next = current.next;
}
length--;
return true;
}
previous = current;
current = current.next;
indexCheck++;
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
tail = previous.next;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index++ < length){
if(current.element === element){
return index;
}
current = current.next;
}
return false;
};
this.toString = function(){
var current = head,
indexCheck = 0,
string = '';
while(current && indexCheck < length){
string += current.element;
indexCheck++;
current = current.next;
}
return string;
};
this.isEmpty = function(){
return length === 0;
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
};
this.size = function(){
return length;
};
}相關推薦：
#以上是JavaScript雙向鍊錶和雙向循環鍊錶的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
