鏈表有多種不同的類型，這一節介紹雙向鏈表。雙向鏈表和普通鏈表的區別在於，在鏈表中，一個節點只有鏈向下一個節點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素，如下圖所示：
先從實現DoublyLinkedList類所需的變動開始：
function DoublyLinkedList {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的
};
let length = 0;
let head = null;
let tail = null; //新增的
//這裡是方法
}
在代碼中可以看到，LinkedList類和DoublyLinkedList類之間的區別標為新增的。在Node類裡有prev屬性（一個新指針），在DoublyLinkedList類裡也有用來保存對列表最後一項的引用的tail屬性。
雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以訪問一個特定節點的下一個或前一個元素。在單向鏈表中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鏈表的一個優點。
5.3.1 在任意位置插入新元素
向雙向鏈表中插入一個新項跟（單向）鏈表非常類似。區別在於，鏈表只要控制一個next指針，而雙向鏈表則要同時控制next和prev（previous，前一個）這兩個指針。
這是向任意位置插入一個新元素的算法：
this.insert = function(position, element){
//檢查越界值
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //在第一個位置添加
if (!head){ //新增的 {1}
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //新增的 {2}
head = node;
}
} else if (position === length) { //最後一項 //新增的
current = tail; // {3}
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){ //{4}
previous = current;
current = current.next;
}
node.next = current; //{5}
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++; //更新列表的長度
return true;
} else {
return false;
}
};
我們來分析第一種場景：在列表的第一個位置（列表的起點）插入一個新元素。如果列表為空（行{1}），只需要把head和tail都指向這個新節點。如果不為空，current變量將是對列表中第一個元素的引用。就像我們在鏈表中所做的，把node.next設為current，而head將指向node（它將成為列表中的第一個元素）。不同之處在於，我們還需要為指向上一個元素的指針設一個值。current.prev指針將由指向null變為指向新元素（node——行{2}）。node.prev指針已經是null，因此不需要再更新任何東西。下圖演示了這個過程：
現在來分析一下，假如我們要在列表最後添加一個新元素。這是一個特殊情況，因為我們還控制著指向最後一個元素的指針（tail）。current變量將引用最後一個元素（行{3}）。然後開始建立第一個鏈接：node.prev將引用current。current.next指針（指向null）將指向node（由於構造函數，node.next已經指向了null）。然後只剩一件事了，就是更新tail，它將由指向current變為指向node。下圖展示了這些行為：
然後還有第三種場景：在列表中間插入一個新元素。就像我們在之前的方法中所做的，迭代列表，直到到達要找的位置（行{4}）。我們將在current和previous元素之間插入新元素。首先，node.next將指向current（行{5}），而previous.next將指向node，這樣就不會丟失節點之間的鏈接。然後需要處理所有的鏈接：current.prev將指向node，而node.prev將指向previous 。下圖展示了這一過程：
我們可以對
insert和remove這兩個方法的實現做一些改進。在結果為否的情況下，我們可以把元素插入到列表的尾部。性能也可以有所改進，比如，如果position大於length/2，就最好從尾部開始迭代，而不是從頭開始（這樣就能迭代更少列表中的元素）。
5.3.2 從任意位置移除元素
從雙向鏈表中移除元素跟鏈表非常類似。唯一的區別就是還需要設置前一個位置的指針。我們來看一下它的實現：
this.removeAt = function(position){
//檢查越界值
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//移除第一項
if (position === 0){
head = current.next; // {1}
//如果只有一項，更新tail //新增的
if (length === 1){ // {2}
tail = null;
} else {
head.prev = null; // {3}
}
} else if (position === length-1){ //最後一項 //新增的
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){ // {5}
previous = current;
current = current.next;
}
//將previous與current的下一項鏈接起來——跳過current
previous.next = current.next; // {6}
current.next.prev = previous; //新增的
}
length--;
return current.element;
} else {
return null;
}
};
我們需要處理三種場景：從頭部、從中間和從尾部移除一個元素。
我們來看看如何移除第一個元素。current變量是對列表中第一個元素的引用，也就是我們想移除的元素。需要做的就是改變head的引用，將其從current改為下一個元素（current.next——行{1}）。但我們還需要更新current.next指向上一個元素的指針（因為第一個元素的prev指針是null）。因此，把head.prev的引用改為null（行{3}——因為head也指向列表中新的第一個元素，或者也可以用current.next.prev）。由於還需要控制tail的引用，我們可以檢查要移除的元素是否是第一個元素，如果是，只需要把tail也設為null（行{2}）。
下圖勾畫了從雙向鏈表移除第一個元素的過程：
下一種場景是從最後一個位置移除元素。既然已經有了對最後一個元素的引用（tail），我們就不需要為找到它而迭代列表。這樣我們也就可以把tail的引用賦給current變量（行{4}）。接下來，需要把tail的引用更新為列表中倒數第二個元素（current.prev，或者tail.prev也可以）。既然tail指向了倒數第二個元素，我們就只需要把next指針更新為null（tail.next = null）。下圖演示了這一行為：
第三種也是最後一種場景：從列表中間移除一個元素。首先需要迭代列表，直到到達要找的位置（行{5}）。current變量所引用的就是要移除的元素。那麼要移除它，我們可以通過更新previous.next和current.next.prev的引用，在列表中跳過它。因此，previous.next將指向current.next，而current.next.prev將指向previous，如下圖所示：
要瞭解雙向鏈表的其他方法的實現，請參閱本書源代碼。源代碼的下載鏈接見本書前言。