周立功新著內(nèi)容分享：雙向鏈表是什么？

近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對本書內(nèi)容進(jìn)行連載。

>>>>1.1 雙向鏈表

單向鏈表的添加、刪除操作，都必須找到當(dāng)前結(jié)點(diǎn)的上一個結(jié)點(diǎn)，以便修改上一個結(jié)點(diǎn)的p_next指針完成相應(yīng)的操作。由于單向鏈表的結(jié)點(diǎn)沒有指向其上一個結(jié)點(diǎn)的指針，因此只有從頭結(jié)點(diǎn)開始遍歷鏈表。當(dāng)某一結(jié)點(diǎn)的p_next指向當(dāng)前結(jié)點(diǎn)時，表明它為當(dāng)前結(jié)點(diǎn)的上一個結(jié)點(diǎn)。顯然每次都要從頭開始遍歷，其效率極為低下。在單向鏈表中，之所以可以直接獲取單向鏈表中當(dāng)前結(jié)點(diǎn)的下一個結(jié)點(diǎn)，是因?yàn)榻Y(jié)點(diǎn)中包含了指向下一個結(jié)點(diǎn)的指針p_next。如果在雙向鏈表的結(jié)點(diǎn)中再增加一個指向它的前一個結(jié)點(diǎn)的前向指針p_prev，則一切問題將迎刃而解。那么，既有指向下一個結(jié)點(diǎn)的指針，又有指向前一個結(jié)點(diǎn)的指針的鏈表稱之為雙向鏈表，示意圖詳見圖3.15。

圖3.15 雙向鏈表示意圖

與單向鏈表一樣，雙向鏈表也定義了一個頭結(jié)點(diǎn)，基于單向鏈表將應(yīng)用數(shù)據(jù)與鏈表結(jié)構(gòu)相關(guān)數(shù)據(jù)完全分離的設(shè)計(jì)思想，則雙向鏈表結(jié)點(diǎn)僅保留p_next和p_prev指針。其數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct _dlist_node{

struct _dlist_node *p_next;

struct _dlist_node *p_prev;

其中，dlist是double list 的縮寫，表明該結(jié)點(diǎn)是雙向鏈表結(jié)點(diǎn)。由此可見，雖然前向指針使得尋找鏈表的上一個結(jié)點(diǎn)變得非常容易，但由于結(jié)點(diǎn)中新增了一個指針，因此其內(nèi)存開銷將會是單向鏈表的兩倍。在實(shí)際應(yīng)用中，應(yīng)該權(quán)衡效率與內(nèi)存空間，在內(nèi)存資源非常緊缺的場合，如果結(jié)點(diǎn)的添加、刪除操作很少，一點(diǎn)效率的影響可以接受，則選擇使用單向鏈表。而不是一味地追求效率，認(rèn)為雙向鏈表比單向鏈表好，始終選擇使用雙向鏈表。

在圖3.15中，頭結(jié)點(diǎn)的p_prev和尾結(jié)點(diǎn)的p_next直接被設(shè)置為了NULL，此時，如果要直接由頭結(jié)點(diǎn)找到尾結(jié)點(diǎn)，或者由尾結(jié)點(diǎn)找到頭結(jié)點(diǎn)，都必須遍歷整個鏈表?？梢詫@兩個指針稍加利用，使頭結(jié)點(diǎn)的p_prev指向尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的p_next指向頭結(jié)點(diǎn)，此時，該雙向鏈表就成了一個循環(huán)雙向鏈表，示意圖詳見圖3.16。

圖3.16 循環(huán)雙向鏈表示意圖

由于循環(huán)雙向鏈表的效率更高，可以直接從頭結(jié)點(diǎn)找到尾結(jié)點(diǎn)，或者從尾結(jié)點(diǎn)找到頭結(jié)點(diǎn)，且沒有額外的內(nèi)存空間消耗，僅僅是使用了兩個不打算使用的指針，算是廢物利用，因此下面介紹的雙向鏈表均視為循環(huán)雙向鏈表。

類似于單向鏈表，雖然頭結(jié)點(diǎn)與普通結(jié)點(diǎn)的內(nèi)容完全相同，但它們的含義卻有所區(qū)別，頭結(jié)點(diǎn)是鏈表的頭，代表了整個鏈表，擁有此頭結(jié)點(diǎn)，就表示其擁有了整個鏈表。為了便于區(qū)分頭結(jié)點(diǎn)與普通結(jié)點(diǎn)，可以單獨(dú)定義一個頭結(jié)點(diǎn)類型。比如：

typedef dlist_node_t dlist_head_t;

當(dāng)需要使用雙向鏈表時，首先需要使用該類型定義一個頭結(jié)點(diǎn)。比如：

dlist_head_t head;

由于此時還沒有添加其它任何結(jié)點(diǎn)，僅存在一個頭結(jié)點(diǎn)，因此該頭結(jié)點(diǎn)既是第一個結(jié)點(diǎn)（頭結(jié)點(diǎn)），又是最后一個結(jié)點(diǎn)（尾結(jié)點(diǎn)）。按照循環(huán)鏈表的定義，尾結(jié)點(diǎn)的p_next指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的p_prev指向尾結(jié)點(diǎn)，僅有一個結(jié)點(diǎn)的示意圖詳見圖3.17。

圖3.17 空鏈

顯然，僅有頭結(jié)點(diǎn)時，其p_next和p_prev都指向本身。即：

head.p_next = &head;

為了避免用戶直接操作成員，需要定義一個初始化函數(shù)，專門用于初始化鏈表頭結(jié)點(diǎn)中各個成員的值，其函數(shù)原型（dlist.h）為：

int dlist_init(dlist_head_t *p_head);

其中，p_head指向待初始化的鏈表頭結(jié)點(diǎn)。其調(diào)用形式如下：

dlist_head_t head;

dlist_init()函數(shù)的實(shí)現(xiàn)詳見程序清單3.33。

程序清單3.33雙向鏈表初始化函數(shù)

1 int dlist_init(dlist_head_t *p_head)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_head -> p_next = p_head;

7 p_head -> p_prev = p_head;

8 return 0;

與單向鏈表類似，將提供一些基礎(chǔ)的操作接口，它們的函數(shù)原型如下：

dlist_node_t *dlist_prev_get (dlist_head_t *p_head, dlist_node_t *p_pos); //尋找某一結(jié)點(diǎn)的前一結(jié)點(diǎn)

dlist_node_t *dlist_tail_get (dlist_head_t *p_head); //獲取尾結(jié)點(diǎn)

dlist_node_t *dlist_begin_get (dlist_head_t *p_head); //獲取開始位置，第一個用戶結(jié)點(diǎn)

對于dlist_prev_get()和dlist_next_get()，在鏈表結(jié)點(diǎn)中已經(jīng)存在指向前驅(qū)后后繼的指針，詳見程序清單3.34。

程序清單3.34得到結(jié)點(diǎn)前驅(qū)和后繼的函數(shù)實(shí)現(xiàn)

1 dlist_node_t *dlist_prev_get(dlist_head_t *p_head, dlist_node_t *p_pos)

2 {

3 if (p_pos != NULL){

4 return p_pos -> p_prev;

5 }

6 return NULL;

7 }

9 dlist_node_t *dlist_next_get(dlist_head_t *p_head, dlist_node_t *p_pos)

10 {

11 if (p_pos != NULL){

12 return p_pos -> p_next;

13 }

14 return NULL;

dlist_tail_get()函數(shù)用于得到鏈表的尾結(jié)點(diǎn)，在循環(huán)雙向鏈表中，頭結(jié)點(diǎn)的p_reev即指向了尾結(jié)點(diǎn)，詳見程序清單3.35。

程序清單3.35 dlist_tail_get()函數(shù)實(shí)現(xiàn)

1 dlist_node_t *dlist_tail_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL) {

4 return p_head->p_prev;

5 }

6 return NULL;

dlist_begin_get()函數(shù)用于得到第一個用戶結(jié)點(diǎn)，詳見程序清單3.36。

程序清單3.36 dlist_begin_get()函數(shù)實(shí)現(xiàn)

1 dlist_node_t *dlist_begin_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL){

4 return p_head->p_next;

5 }

6 return NULL;

dlist_end_get()用于得到鏈表的結(jié)束位置，當(dāng)雙向鏈表設(shè)計(jì)為循環(huán)雙向鏈表時，則頭結(jié)點(diǎn)的p_prev和尾結(jié)點(diǎn)的p_next都被有效地利用了，任何有效結(jié)點(diǎn)的p_next和p_prev都不再為NULL。顯然，不能再以NULL作為結(jié)束位置了，當(dāng)從第一個結(jié)點(diǎn)開始順序訪問鏈表的各個結(jié)點(diǎn)時，尾結(jié)點(diǎn)的下一個結(jié)點(diǎn)就是鏈表頭結(jié)點(diǎn)（head），因此結(jié)束位置就是頭結(jié)點(diǎn)本身。dlist_end_get()的實(shí)現(xiàn)詳見程序清單3.37。

程序清單3.37 dlist_end_get()函數(shù)實(shí)現(xiàn)

1 dlist_node_t *dlist_end_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL) {

4 return p_head->p_prev;

5 }

6 return NULL;

在公眾號后臺回復(fù)關(guān)鍵字“程序設(shè)計(jì)”，即可在線閱讀《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》；回復(fù)關(guān)鍵字“編程”，即可在線閱讀《面向AMetal框架與接口的編程（上）》。