據(jù)說單鏈表沒有回路，那么雙鏈表也出現(xiàn)了，既包括后繼指針，又加入了前驅(qū)指針，某個元素可以尋找他上面一個元素，也可以尋找到下一個元素。當(dāng)然雙鏈表也是鏈表的一種。

物理存儲結(jié)構(gòu)：不一定是連續(xù)的存儲區(qū)域 邏輯存儲結(jié)構(gòu)：邏輯上存儲是連續(xù)的

使用場景：跟單鏈表一樣，適用于對數(shù)據(jù)的大量新增和刪除元素，對訪問元素?zé)o要求，預(yù)先無法確定數(shù)據(jù)量的程序 首先創(chuàng)建存儲元素結(jié)構(gòu) /// <summary>/// 雙鏈表/// </summary>class DLinkList{public string data;//上一個節(jié)點public DLinkList prior;//下一個節(jié)點public DLinkList next;}

創(chuàng)建操作類和表頭
/// <summary>/// 雙鏈表操作/// </summary>class DLinkListClass{//創(chuàng)造雙鏈表的頭元素public DLinkList dhead = new DLinkList(); }

插入數(shù)據(jù)：同樣跟單鏈表一樣有兩種方式插入，時間空間復(fù)雜度為：O(n)

#region 建立雙鏈表-頭插法 O(n)public void CreateListFrist(string[] split){DLinkList s;dhead.next = null;for (int i = 0; i < split.Length; i++){s = new DLinkList();s.data = split[i];//新增的這一級找到以前head指向的下一級，作為nexts.next = dhead.next;//頭部的下一級的prior以前指向的是head，那么現(xiàn)在這級的prior先找到新插入的元素if (dhead.next!=null){s.next.prior = s;}//head的下一級指向新增項dhead.next = s;//新增項的prior上一級指向heads.prior = dhead;}}#endregion#region 建立雙鏈表-尾插法 O(n)public void CreateListEnd(string[] split){DLinkList p, s;p = dhead;for (int i = 0; i < split.Length; i++){//插入新項s = new DLinkList();s.prior = p;s.data = split[i];//尾部的下一級指向新增項p.next = s;//新增項轉(zhuǎn)換成尾部p = s;}p.next = null;}#endregion

輸出雙鏈表，時間空間復(fù)雜度為：O(n)
#region 輸出雙鏈表表 O(n)public string DispList(){string str = "";DLinkList p;p = dhead.next;while (p != null){str += p.data + " ";p = p.next;}return str;}#endregion

輸出雙鏈表的長度，時間空間復(fù)雜度為：O(n)
#region 雙鏈表的長度 O(n)public int ListLength(){int i = 0;DLinkList p;p = dhead;while (p.next != null){i++;p = p.next;}return i;}#endregion

獲取元素item項的值，時間空間復(fù)雜度為：O(n)
#region 獲取第item項的值 O(n)public bool GetElem(int item, ref string e){DLinkList p = dhead;int j = 0;if (item < 1){return false;}//循環(huán)找到item的位置while (j < item && p != null){j++;p = p.next;}//判斷item位置是否存在if (p == null){return false;}else{e = p.data;return true;}}#endregion

根據(jù)元素值獲取位置，時間空間復(fù)雜度為：O(n)
#region 根據(jù)元素值獲取item位置 O(n)public int LoateElem(string e){DLinkList p = dhead.next;int item = 0;//開始找元素里面的data與e相等while (p != null && p.data != e){//計數(shù)item++;//下一個元素p = p.next;}//如果雙鏈表沒有元素或者沒有找到與雙鏈表匹配的值，輸出為0if (p == null){return 0;}else{return item;}}#endregion

指定位置插入元素，時間空間復(fù)雜度為：O(n) 1.這里先找到插入元素位置，獲取前一個元素 2.將這個元素的后繼地址給新增元素的后繼地址 3.然后把下一個元素的前驅(qū)地址換成新元素的地址 4.然后將新元素的前驅(qū)地址換成前一個元素的地址 5.前一個元素的后繼地址換成新元素地址
#region 在item插入值 O(n)public bool ListInsert(int item, string values){DLinkList p, s;p = dhead;int j = 0;while (j<item-1 && p!=null){p = p.next;j++;}if (p==null){return false;}else{//創(chuàng)造一個新增元素s = new DLinkList();s.data = values;//新增項找到下一級s.next = p.next;//新增項的下一級的prior找到新增元素if (s.next!=null){s.next.prior = s;}//新增項的prior上一級s.prior = p;//新增項上一級的nextp.next = s;return true;}}#endregion

刪除定點的元素，時間空間復(fù)雜度為：O(n) 1.尋找到這個元素的位置

2.這里先找到刪除元素的上一級，這個上一級的后繼地址指向刪除元素的下一級元素 3.然后這個上一級的前驅(qū)元素指向刪除元素的上一級 #region 刪除item項public bool ListDelete(int item, ref string values){DLinkList p, s;p = dhead;int j = 0;while (j<item-1 && p!=null){p = p.next;j++;}if (p==null || p.next==null){return false;}else{s = p.next;values = s.data;//刪除項的上一級next尋找刪除項下一級p.next = s.next;//刪除項的下一級的prior尋找刪除項的上一級if (p.next != null){s.next.prior = p;}//釋放空間s = null;return true;}}#endregion 結(jié)論：雙鏈表相比順序表新增刪除省了不少事，不用每次都要重新操作后面的移位問題，但是相對于鏈表內(nèi)存消耗多了指針域

優(yōu)點：沒有空間限制，存儲元素的個數(shù)無上限，基本只與內(nèi)存空間大小有關(guān)。插入和刪除元素速率高。

缺點：占用額外的空間以存儲指針(浪費空間)。隨機(jī)存取元素速率低。雙鏈表要找一個數(shù)，必須要從表頭開始找起，存取率元素的速率非常的低。

循環(huán)雙鏈表，操作跟雙鏈表一樣，只是注意尾元素的后繼不是指向空地址，而是指向head頭元素，頭元素的前驅(qū)地址指向的是尾元素的地址，這里的頭元素在循環(huán)鏈表中做了一個參照物的作用，如果你不知道頭元素在哪里，可能操作的時候會出現(xiàn)一直循環(huán)下去，最終會導(dǎo)致程序崩潰。

總結(jié)

以上是生活随笔為你收集整理的C#数据结构-双链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。