雙向鏈表又稱“雙向回圈鏈表”，相較于單鏈表，雙向鏈表增加了一個指向前面一個結點的指標，鏈表內的結點不會存在NULL結點，文章有點長，但是干貨滿滿，希望你能看完，
目錄
一、初識雙向鏈表
二、雙向鏈表初始化
三、添加結點
3.1頭插法
3.2尾插法
3.3指定位置插入
四、洗掉結點
4.1洗掉指定位置結點
4.2洗掉整表
五、獲取結點
附：完整原始碼：
一、初識雙向鏈表
在雙向鏈表中，每個結點都有兩個指標域(prior和next)和一個資料域(data)，第一個結點稱”頭結點“，頭結點不存盤資料，但它存盤了指向下一個結點的地址和最后一個結點的地址，從而實作了雙向和回圈，反觀單鏈表，只有一個next，每個節點只能訪問自己的下一個結點，對于CRUD等操作都沒有雙向鏈表靈活，
二、雙向鏈表初始化
來看上面這張圖，對于一個空的雙向鏈表只有一個頭結點，上面說過了頭結點不帶有資料，因此空的雙向鏈表的next指標存盤的就是我自己，prior(前指標)也指向我自己，這就相當于一個空的回圈鏈表，所以通過代碼實作就是上圖的：this.prior=this.next=this;
我們這一次用DoubleLinkList來描述一個雙向鏈表，使用建構式就是
function DoubleLinkList()
{
//初始化頭結點
this.prior=this.next=this;
}對，就是這么簡簡單單的一句話，每次實體化一個DoubleLinkList類的物件的時候都會做一遍這個初始化，自動生成一個空雙向鏈表，
但是貌似還缺少什么？眼力見好的小伙伴可能已經發現了：每個節點不是說都有兩個指標域和一個資料域么？對的，這也屬于初始化作業的一部分，但是這部分的初始化我們用一個內部類去封裝，就叫做結點類DoubleNode
//相當于內部類,保存資料域和兩個指標域
function DoubleNode(data){
this.data=data;
this.prior=null;
this.next=null;
}
至此，初始化作業全部結束，接下來就可以寫我們的業務邏輯：CRUD
三、添加結點
首先來簡單講一下增加結點的核心邏輯：
如圖，在雙向鏈表的任何一個位置插入結點的代碼都是完全一樣的，假設我們實體化得到了一個新結點node，我們想在p結點1和p.next結點3的位置中間把這個新結點node4插入進去，就需要破壞原有的1和3結點的next和prior，如何破壞呢？首先將node的prior指向p，再將node.next指向p.next，此時完成了node結點的prior和next指標的賦值,但是還沒有破壞p和p.next的兩個指標,再來將p.next.prior指向node，此時就破壞了上圖的藍色箭頭(畫了X的)，最后將p.next指向node，就破壞了上圖綠色箭頭,至此新結點node就插進去了，四個步驟不能亂，否則某個結點的地址就會丟失
3.1頭插法
OK，理解了上面的插入，接下來頭插法就好理解了
//頭插法
DoubleLinkList.prototype.insertDouListByHead=function(data){
const node = new DoubleNode(data);
let p=this;
//核心代碼
node.prior = p;
node.next = p.next;
p.next.prior = node;
p.next = node;
}3.2尾插法
尾插法類似，只是他需要尋找到最后一個結點，于是判斷條件就是p.next!==this
DoubleLinkList.prototype.insertDouListByTail=function(data){
const node=new DoubleNode(data);
let p=this.next;
while(p.next!==this){
p=p.next;
}
//核心代碼
node.prior = p;
node.next = p.next;
p.next.prior = node;
p.next = node;
}3.3指定位置插入
指定位置插入，需要用戶傳入一個Pos位置，原理類似
//任意位置插入結點
DoubleLinkList.prototype.insertDouListByPos=function(data,Pos){
const node=new DoubleNode(data);
let p=this,i=0;
while(i<Pos-1 && p.next!==this){
i++;
p=p.next;
}
//核心代碼
node.prior = p;
node.next = p.next;
p.next.prior = node;
p.next = node;
}四、洗掉結點
再來看洗掉結點的核心邏輯：
相對于添加，洗掉似乎簡單許多，主要是要破壞p結點的前后指標域，根據上圖所畫相信大家一目了然，哦~不過如此嘛！只不過不僅要破壞還要重新將p的前后兩個結點連起來，就是上圖紅色的兩個箭頭，要不然就是洗掉包括p在內的后面的所有結點了！
4.1洗掉指定位置結點
//指定位置洗掉
DoubleLinkList.prototype.deleteNode=function(Pos){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法洗掉'));
return false;
}
let i = 0, p = this;
while (i < Pos && p.next !== this) {
i++;
p = p.next;
}
if (Pos > i || Pos < 1) {
console.log(new Error('該位置不存在'));
return false;
}
p.prior.next=p.next;
p.next.prior = p.prior;
}這段代碼頭尾部分應該不用多講，中間部分就是在尋找需要被洗掉的那個結點
4.2洗掉整表
//整表洗掉
DoubleLinkList.prototype.clear=function(){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法清空鏈表'));
return false;
}
let p=this.next;
let i=1;
while(p!==this){
this.deleteNode(1);
p=p.next;
}
}洗掉整表就是從頭結點的下一個結點開始一個一個洗掉，這里直接呼叫了上面的洗掉結點方法，每次洗掉第一個，直至全部洗掉，
五、獲取結點
//獲取指定位置的結點
DoubleLinkList.prototype.getNode=function(Pos){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法獲取'));
return false;
}
let i = 0, p = this;
while (i < Pos && p.next !== this) {
i++;
p = p.next;
}
if (Pos > i || Pos < 1) {
console.log(new Error('該位置不存在'));
return false;
}
return p.data;
}這個和洗掉結點沒有太大的區別，唯一的區別就是最后只需要將獲取結點的資料域回傳出去即可，
附：完整原始碼：
'use strict'
//雙向鏈表
const DoubleLinkList=function(){
const wm=new WeakMap();
//雙向鏈表建構式
function DoubleLinkList(){
//初始化頭結點
this.prior=this.next=this;
//定義私有方法
const privates=wm.get(this) || {};
this.privateInsert=Symbol('private'); //私有方法
this.privateFind=Symbol('private'); //私有方法
privates[this.privateInsert]=privateInsert.bind(this); //插入
privates[this.privateFind]=privateFind.bind(this);
wm.set(this,privates);
}
//相當于內部類,保存資料域和兩個指標域
function DoubleNode(data){
this.data=data;
this.prior=null;
this.next=null;
}
//將頭插法、尾插法相同部分的代碼抽取出來，進一步封裝
function privateInsert(node,p) {
node.prior = p;
node.next = p.next;
p.next.prior = node;
p.next = node;
}
//尋找結點的公共部分，封裝
function privateFind(Pos){
let i = 0, p = this;
while (i < Pos && p.next !== this) {
i++;
p = p.next;
}
if (Pos > i || Pos < 1) {
console.log(new Error('該位置不存在'));
return false;
}
return p;
}
//頭插法
DoubleLinkList.prototype.insertDouListByHead=function(data){
const node = new DoubleNode(data);
let p=this;
wm.get(this)[this.privateInsert](node,p);
}
//尾插法
DoubleLinkList.prototype.insertDouListByTail=function(data){
const node=new DoubleNode(data);
let p=this.next;
while(p.next!==this){
p=p.next;
}
wm.get(this)[this.privateInsert](node,p);
}
//任意位置插入結點
DoubleLinkList.prototype.insertDouListByPos=function(data,Pos){
const node=new DoubleNode(data);
let p=this,i=0;
while(i<Pos-1 && p.next!==this){
i++;
p=p.next;
}
wm.get(this)[this.privateInsert](node,p);
}
//指定位置洗掉
DoubleLinkList.prototype.deleteNode=function(Pos){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法洗掉'));
return false;
}
let p=wm.get(this)[this.privateFind](Pos);
p.prior.next=p.next;
p.next.prior = p.prior;
}
//獲取指定位置的結點
DoubleLinkList.prototype.getNode=function(Pos){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法獲取'));
return false;
}
let p=wm.get(this)[this.privateFind](Pos);
return p.data;
}
//整表洗掉
DoubleLinkList.prototype.clear=function(){
if(this.prior===this && this.next===this){
console.log(new Error('鏈表為空，無法清空鏈表'));
return false;
}
let p=this.next;
let i=1;
while(p!==this){
this.deleteNode(1);
p=p.next;
}
}
return DoubleLinkList;
}();雙向鏈表的學習就到此結束了，
如果對你有用，別忘了點個收藏哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/290676.html
標籤：其他
上一篇：React入門到組件的三大核心