鏈表有多種不同的類型话速，雙向鏈表和普通鏈表的區(qū)別在于，在鏈表中购公，一個節(jié)點(diǎn)只有鏈向下一個節(jié)點(diǎn)的鏈接萌京，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素宏浩，另一個鏈向前一個元素知残。
單鏈表的缺陷
單鏈表只能從頭節(jié)點(diǎn)開始訪問鏈表中的數(shù)據(jù)元素，如果需要逆序訪問單鏈表中的數(shù)據(jù)元素將極其低效比庄。
從鏈表的頭節(jié)點(diǎn)遍歷到尾節(jié)點(diǎn)很簡單求妹，但反過來從后向前遍歷則沒那么簡單。通過給Node對象增加一個屬性佳窑，該屬性存儲指向前驅(qū)節(jié)點(diǎn)的鏈接制恍，這樣就容易多了。此時神凑，向鏈表插入一個節(jié)點(diǎn)需更多的工作净神，需指出該節(jié)點(diǎn)正確的前驅(qū)和后驅(qū)。但從鏈表中刪除節(jié)點(diǎn)時溉委，效率提高了鹃唯，無需再查找待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。
function Node(element){
this.element = element;
this.prev = null;
this.next = null;
}
function Llist(){
this.head = new Node('head');
this.find = find;
this.insert = insert;
this.display = display;
this.remove = remove;
this.findLast = findLast;
this.dispReverse = dispReverse;
}
function find(item){
var current = this.head;
while(current.element!=item){
current = current.next
}
return current;
}
//雙向鏈表的插入與單向鏈表類似瓣喊，但需設(shè)置新節(jié)點(diǎn)的prev屬性坡慌，使其指向該節(jié)點(diǎn)的前驅(qū)。
function insert(item,element){
var current = this.find(item);
var node = new Node(element);
node.prev = current;
node.next = current.next;
current.next = node;
}
// 雙向鏈表的刪除比單向鏈表效率更高藻三，因為不需要再查找前驅(qū)節(jié)點(diǎn)洪橘。
// 首先需要在鏈表中找出存儲帶刪除數(shù)據(jù)的節(jié)點(diǎn)絮爷，然后設(shè)置該節(jié)點(diǎn)前驅(qū)的next屬性，使其指向待刪除節(jié)點(diǎn)的后繼梨树。
// 設(shè)置該節(jié)點(diǎn)后繼的previous屬性，使其指向待刪除節(jié)點(diǎn)的前驅(qū)岖寞。
function remove(item){
var current = this.find(item);
if(!(current.next==null)){
current.prev.next = current.next;
current.next.prev = current.prev;
current.next = null;
current.prev = null;
}
}
// 查找最后的節(jié)點(diǎn)抡四，同時避免從前往后遍歷鏈表。
function findLast(){
var current = this.head;
while(!(current.next==null)){
current = current.next;
}
return current;
}
// 以反序顯示鏈表中元素
function dispReverse(){
var current = this.head;
current = this.findLast();
while(!(current.prev == null)){
print(current.element);
current = current.prev;
}
}
function display(){
var current = this.head;
while(!(current.next==null)){
print(current.next.element)
current = current.next;
}
}
var ll = new Llist();
ll.insert('head','conway');
ll.insert('conway','russellville');
ll.insert('russellville','alma');
ll.display();
print();
ll.remove('conway');
ll.display();
print();
ll.dispReverse();
雙向鏈表實現(xiàn)
雙向鏈表提供了兩種迭代列表的方法：從頭到尾仗谆，或反過來指巡。也可訪問一個特定節(jié)點(diǎn)的下一個或前一個元素。
在單向鏈表中隶垮，如果迭代列表時錯過要找的元素藻雪，就需要回到列表起點(diǎn)，重新開始迭代狸吞。這就是雙向鏈表的一個優(yōu)點(diǎn)勉耀。
function DoublyLinkedList(){
var Node = function(element){
this.element = element;
this.prev = null;
this.next = null;
};
var length = 0;
var head = null;
var tail = null;
}
在任意位置插入新元素
-
場景1：在鏈表起點(diǎn)插入新元素
在鏈表起點(diǎn)插入元素
若鏈表為空只需把head和tail都指向這個新節(jié)點(diǎn)。如果非空蹋偏，current變量將是對鏈表中第一個元素的引用便斥。就像在鏈表中所做的，將node.next設(shè)置為current威始，而head將指向node（它將成為列表中第一個元素）枢纠。不同之處在于，我們還需要為指向上一個元素的指針設(shè)置一個值黎棠。current.prev指針將由指向null變成指向新元素晋渺。node.prev指針已經(jīng)是null，因此無需再更新任何東西脓斩。
-
場景2：在鏈表最后添加新元素
在鏈表末尾插入元素
因為控制著指向最后一個元素的指針（tail）木西，current變量將引用最后一個元素。然后開始建立第一個鏈接：node.prev將引用current俭厚。current.next指針（指向null）將指向node（由于構(gòu)造函數(shù)户魏，node.next已經(jīng)指向了null）。最后是更新tail挪挤，它將由指向current變?yōu)橹赶騨ode叼丑。
-
場景3：在鏈表中間插入新元素
在鏈表中間插入新元素
迭代列表直到到達(dá)要找的位置，將在current和previous元素之間插入新元素扛门。首先鸠信，node.next將指向current，而previous.next將指向node论寨，這樣就不會丟失節(jié)點(diǎn)之間的鏈接星立。然后需要處理所有的鏈接current.prev將指向node爽茴，而node.prev將指向previous。
this.insert = function(position,element){
if(position>=0 && position<=length){
var node = new Node(element);
var current = head;
if(position==0){
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if(position === length){
current = tail;
current.next = node;
node.prev = current;
tail = node;
}else{
var index = 0;
var previous;
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;
}
};
從任意位置移除元素
-
場景1：從頭部移除一個元素
current變量是對列表中第一個元素的引用绰垂，也就是想要移除的元素室奏。需要做的是改變head的引用，將其從current修改為下一個元素（current.next）劲装。但還需更新current.next指向上一個元素的指針胧沫，因為第一個元素的prev指針是null。因此占业，把head.prev的引用改為null - 因為head也指向列表中新的第一個元素绒怨，或者也可以用current.next.prev。由于還需控制tail的引用谦疾，可以檢查要移除的元素是否是第一個元素南蹂。若是則只需把tail設(shè)置為null。
雙向鏈表移除第一個元素 -
場景2：從最后一個位置移除元素
既然已有對最后一個元素的引用（tail）念恍，就無需找到它而迭代列表六剥。可把tail的引用賦給current變量峰伙，把tail的引用更新為列表中倒數(shù)第二個元素（current.prev或tail.prev）仗考。既然tail指向倒數(shù)第二個元素，就只需把next指針更新為null（tail.next=null）词爬。
從最后一個位置移除元素 -
場景3：從列表中間移除一個元素
首先需要迭代列表直到到達(dá)要找的位置秃嗜，current變量所引用的就是要移除的元素。要移除它可通過更新previous.next和current.next.prev的引用顿膨，在列表中跳過它锅锨。因此，previous.next將指向current.next恋沃，而current.next.prev將指向previous必搞。
從列表中間移除一個元素
this.removeAt = function(position){
//檢查越界值
if(position>-1 && position<length){
var current = head;
//移除第一項
if(position===0){
head = current.next;
//若只有一項則更新tail
if(length===1){
tail = null;
}else{
head.prev = null;
}
}else if(position === length-1){//移除最后一項
current = tail;
tail = current.prev;
tail.next = null;
}else{//移除中間相
var index = 0;
var previous;
while(index++ < position){
previous = current;
current = current.next;
}
//將previous和current的下一項鏈接起來，跳過current囊咏。
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
}else{
return null;
}
};
