首先，明白什么是雙向鏈表。所謂雙向鏈表是如果希望找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度都是 O(1)，那么，需要在結(jié)點(diǎn)中設(shè)兩個(gè)引用域，一個(gè)保存直接前驅(qū)結(jié)點(diǎn)的地址，叫 prev，一個(gè)直接后繼結(jié)點(diǎn)的地址，叫 next，這樣的鏈表就是雙向鏈表(Doubly Linked List)。雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)示意圖如圖所示。

雙向鏈表結(jié)點(diǎn)的定義與單鏈表的結(jié)點(diǎn)的定義很相似， ，只是雙向鏈表多了一個(gè)字段 prev。其實(shí)，雙向鏈表更像是一根鏈條一樣，你連我，我連你，不清楚，請(qǐng)看圖。

雙向鏈表結(jié)點(diǎn)類的實(shí)現(xiàn)如下所示

//一個(gè)鏈條的類

public class DbNode<T>
{

//當(dāng)前的數(shù)據(jù)所在
private T data; //數(shù)據(jù)域記錄的數(shù)據(jù)的 
private DbNode<T> prev; //前驅(qū)引用域 前驅(qū) 引用位置 
private DbNode<T> next; //后繼引用域 后來鏈條的位置

//構(gòu)造器 這是不是初始化 
public DbNode(T val, DbNode<T> p)
{
data = val;
next = p;
}

//構(gòu)造器 這是不是初始化
public DbNode(DbNode<T> p)
{
next = p;
}

//構(gòu)造器  吧這個(gè)鏈子相應(yīng)值 傳遞給他
public DbNode(T val)
{
data = val;
next = null;
}

//構(gòu)造器  構(gòu)造一個(gè)空的鏈子
public DbNode()
{
data = default(T);
next = null;
}

//數(shù)據(jù)域?qū)傩?br />public T Data
{
get
{
return data;
}
set
{
data = value;
}
}

//前驅(qū)引用域?qū)傩?br />public DbNode<T> Prev
{
get
{
return prev;
}
set
{
prev = value;
}
}

//后繼引用域?qū)傩?br />public DbNode<T> Next
{
get
{
return next;
}
set
{
next = value;
}
}
}

說了這么多雙向鏈表接點(diǎn)的類的屬性，我們要看一看他的相關(guān)的操作。這里只做一些畫龍點(diǎn)睛地方的描述

操作：設(shè) p是指向雙向鏈表中的某一結(jié)點(diǎn)，即 p存儲(chǔ)的是該結(jié)點(diǎn)的地址，現(xiàn)要將一個(gè)結(jié)點(diǎn) s 到結(jié)點(diǎn) p 的后面，的源代碼如下所示：操作如下： 

? p.Next.Prev = s;
? s.Prev = p;
? s.Next = p.Next;
? p.Next = s;

過程如圖所示（以 p 的直接后繼結(jié)點(diǎn)存在為例） 。

注意：引用域值的操作的順序不是唯一的，但也不是任意的，操作?必須放到操作?的前面完成，否則 p 直接后繼結(jié)點(diǎn)的就找不到了。這一點(diǎn)需要讀者把每個(gè)操作的含義搞清楚。此算法時(shí)間操作消耗在查找上，其時(shí)間的復(fù)雜度是O(n).

下面，看他的刪除操作，以在結(jié)點(diǎn)之后刪除為例來說明在雙向鏈表中刪除結(jié)點(diǎn)的情況。 設(shè) p是指向雙向鏈表中的某一結(jié)點(diǎn)，即 p存儲(chǔ)的是該結(jié)點(diǎn)的地址，現(xiàn)要將一個(gè)結(jié)點(diǎn) s到結(jié)點(diǎn) p的后面 。偽代碼如下：操作如下：

? p.Next = P.Next.Next;
? p.Next.Prev = p.Prev;

刪除過程如圖所示（以 p的直接后繼結(jié)點(diǎn)存在為例）

相應(yīng)的算法的時(shí)間復(fù)雜度也是消耗到結(jié)點(diǎn)的查找上，其復(fù)雜度應(yīng)該是O(n)

查找操作與單鏈表的極其的類似，也是從頭開始遍歷。相應(yīng)偽代碼如圖所示：

current.next=p.next.next

current.prev=p.next.prev;

相應(yīng)的偽代碼如下圖所示：

該算法的時(shí)間復(fù)雜度，是一個(gè)個(gè)的遍歷的過程中，顧時(shí)間復(fù)雜度是O(n)

獲取當(dāng)前的雙向鏈表長(zhǎng)度與 查找類似，不做過多的贅述，這里，我們把雙向鏈表基本概念和操作基本介紹完了，下面介紹一個(gè)重要的鏈表——環(huán)形鏈表。

首先，還是老樣子，看看環(huán)形鏈表的定義。有些應(yīng)用不需要鏈表中有明顯的頭尾結(jié)點(diǎn)。在這種情況下，可能需要方便地從最后一個(gè)結(jié)點(diǎn)訪問到第一個(gè)結(jié)點(diǎn)。此時(shí)，最后一個(gè)結(jié)點(diǎn)的引用域不是空引用，而是保存的第一個(gè)結(jié)點(diǎn)的地址（如果該鏈表帶結(jié)點(diǎn)，則保存的是頭結(jié)點(diǎn)的地址） ，也就是頭引用的值。我們把這樣的鏈表結(jié)構(gòu)稱之為環(huán)形鏈表。他就像小朋友手拉手做游戲。如圖所示。

用鏈表如圖所示：

這里基本添加，刪除，操作的操作與單鏈表簡(jiǎn)直是一模一樣，這里就沒有必要寫這些東西。我們主要看他們一些簡(jiǎn)單應(yīng)用。

應(yīng)用舉例一 已知單鏈表 H，寫一算法將其倒置，即實(shí)現(xiàn)如圖所示的操作，其中(a)為倒置前，(b)為倒置后。

算法思路：由于單鏈表的存儲(chǔ)空間不是連續(xù)的，所以，它的倒置不能像順表那樣，把第 i 個(gè)結(jié)點(diǎn)與第 n-i 個(gè)結(jié)點(diǎn)交換（i 的取值范圍是 1 到 n/2，n 為單鏈表的長(zhǎng)度） 。其解決辦法是依次取單鏈表中的每個(gè)結(jié)點(diǎn)到新鏈表中去。并且，為了節(jié)省內(nèi)存資源，把原鏈表的頭結(jié)點(diǎn)作為新鏈表的頭結(jié)點(diǎn)。存儲(chǔ)整數(shù)的單鏈表的倒置的算法實(shí)現(xiàn)如下：

public void ReversLinkList(LinkList<int> H)
{
Node<int> p = H.Next;
Node<int> q = new Node<int>();
H.Next = null;

while (p != null)
{
q = p;
p = p.Next;
q.Next = H.Next;
H.Next = q;
}
}
該算法要對(duì)鏈表中的結(jié)點(diǎn)順序掃描一遍才完成了倒置，所以時(shí)間復(fù)雜度為O(n),但比同樣長(zhǎng)度的順序表多花一倍的時(shí)間，因?yàn)轫樞虮碇恍枰獟呙枰话氲臄?shù)據(jù)元素。這個(gè)是不是你已經(jīng)頭腦糊了嗎？如果糊了把，請(qǐng)看我的圖例的解釋。

舉例2，約瑟夫環(huán)問題，題目如下：

已知n個(gè)人（以編號(hào)1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號(hào)為k的人開始報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。求最后出列的人相應(yīng)的編號(hào)。

　　void JOSEPHUS(int n,int k,int m) //n為總?cè)藬?shù)，k為第一個(gè)開始報(bào)數(shù)的人，m為出列者喊到的數(shù)

　　{

　　/* p為當(dāng)前結(jié)點(diǎn) r為輔助結(jié)點(diǎn)，指向p的前驅(qū)結(jié)點(diǎn) list為頭節(jié)點(diǎn)*/

　　LinkList p,r,list; /*建立循環(huán)鏈表*/

　　for(int i=0；i<n；i++)

　　{

　　p=(LinkList)LNode;

　　p.data=i;

　　if(list==NULL)

　　list=p;

　　else

　　r.link=p;

　　r=p;

　　}

　　p.link=list; /*使鏈表循環(huán)起來*/

　　p=list；　/*使p指向頭節(jié)點(diǎn)*/

　　/*把當(dāng)前指針移動(dòng)到第一個(gè)報(bào)數(shù)的人*/

　　for(i=0;i<k;i++)

　　{

　　r=p；

　　p=p.link;

　　}

　　/*循環(huán)地刪除隊(duì)列結(jié)點(diǎn)*/

　　while(p.link!=p)

　　{

　　for(i=0;i<m-1;i++) 

　　{

　　r=p;

　　p=p.link;

　　}

　　r.link=p.link;

　　console.writeline("被刪除的元素:{0} ",p.data);

　　free(p);

　　p=r.node.;

　　} 

　　console.writeLine("\n最后被刪除的元素是：{0}",P.data);

    具體的算法，如圖所示：

　　}

還和大家分享的一個(gè)例子，就是我做做一個(gè)類似與網(wǎng)易郵箱的產(chǎn)品時(shí)候，幾千萬甚至數(shù)以億級(jí)的大數(shù)量登錄的時(shí)候，發(fā)現(xiàn)用戶登錄的時(shí)候真慢，你猜我開始是怎么做的，就是直接查數(shù)據(jù)庫(kù)，這當(dāng)然是不行的。這怎么辦了， 最后，我在一個(gè)高人的指教下，發(fā)現(xiàn)登錄的時(shí)候速度飛快，怎么搞的。我把所有的數(shù)據(jù)庫(kù)的數(shù)據(jù)讀入到內(nèi)存中，然后把數(shù)據(jù)用鏈表把他們串起來，到我查詢某個(gè)用戶時(shí)候，只比較用戶的 字節(jié)數(shù)。

這就是我眼中的鏈表結(jié)構(gòu)。

最新評(píng)論