單鏈表從頭到尾遍歷奠蹬、插入元素比較方便，但是刪除元素就沒有那么方便了嗡午，此時我們需要用到雙向鏈表囤躁。
雙向鏈表，顧名思義就是有兩個方向(指針)，每個節(jié)點有兩個指針狸演，一個后驅(qū)指針指向它后面的節(jié)點言蛇，一個前驅(qū)指針指向前面的節(jié)點。
雙向鏈表.png
由上圖可以看出宵距，雙向鏈表占用了更多的內(nèi)存空間猜极，但是由于其支持雙向遍歷，所以雙向鏈表也更加靈活消玄。
接下來我們實現(xiàn)一個基于對象的雙向鏈表。
先定義node類
function Node(val)
{
this.val=val;
this.next=null;
this.previous=null;
}
然后我們看看linkList類
function linkList()
{
this.head=new Node(0);
this.find=find; //此方法和單鏈表里對應(yīng)方法相同
this.insert=insert;
this.remove=remove;
this.findLast=findLast; //此方法和單鏈表里對于方法相同
}
插入元素丢胚，插入元素的時候要記得處理節(jié)點的前驅(qū)指針翩瓜。
雙鏈表的插入.png
function insert(new_data,item)
{
var new_node=new Node(new_data);
if(item)
{
var curNode=this.find(item);
if(curNode)
{
new_node.next=curNode.next;
new_node.previous=curNode;
curNode.next=new_node;
}
}
else
{
var finder=this.findLast();
new_node.next=finder.next;
new_node.prev=finder;
finder.next=new_node;
}
}
刪除元素，雙鏈表刪除元素的時候携龟，不需要再去遍歷尋找當(dāng)前節(jié)點的前一個節(jié)點兔跌。
雙鏈表刪除元素.png
function remove(item)
{
var finder=this.find(item);
if(finder)
{
finder.previous.next=finder.next;
finder.next.previous=finder.previous;
finder.next=null;
finder.previous=null;
}
}
接下來我們看一下鏈表的反轉(zhuǎn)。
首先我們看看單鏈表的反轉(zhuǎn)
單鏈表反轉(zhuǎn).png
由上圖可以看出，我們可以把鏈表分成兩部分，一部分為去掉頭節(jié)點之后的剩余節(jié)點揍魂，另外一部分則用于存儲處理頭節(jié)點称鳞。
另外我們需要將之前的指針做個翻轉(zhuǎn)。
function listReverse(head)
{
var curNode=head;
var prev=null;
while(curNode!=null)
{
var newTemp=curNode.next;
curNode.next=prev;
prev=curNode;
curNode=newTemp;
}
return prev;
}
接下來咨演，我們用更加容易實現(xiàn)的雙向鏈表，來實現(xiàn)鏈表的反序表示問題。
function reverseList()
{
var curNode=this.findLast();
while(curNode.prev!=null)
{
console.log(curNode. val);
curNode=curNode.prev;
}
}
