柚子快報邀請碼778899分享：【數(shù)據(jù)結構】雙向鏈表

http://yzkb.51969.com/

Hi~！這里是奮斗的小羊，很榮幸您能閱讀我的文章，誠請評論指點，歡迎歡迎 ~~ ??個人主頁：奮斗的小羊 ??所屬專欄：數(shù)據(jù)結構

?本系列文章為個人學習筆記，在這里撰寫成文一為鞏固知識，二為記錄我的學習過程及理解。文筆、排版拙劣，望見諒。

目錄

前言1、鏈表的分類2、雙向鏈表的實現(xiàn)2.1雙向鏈表節(jié)點2.2申請節(jié)點2.3數(shù)據(jù)的打印和查找2.4頭插和尾插2.5頭刪和尾刪2.6在指定位置插入、刪除數(shù)據(jù)2.7銷毀雙向鏈表

3、雙向鏈表完整代碼4、順序表和鏈表比較總結

前言

單鏈表只能通過某個節(jié)點的地址單向的訪問數(shù)據(jù)，而雙向鏈表可以通過某個節(jié)點的地址雙向的訪問數(shù)據(jù)，增刪查改的效率更高，但是代碼的實現(xiàn)卻比單鏈表簡單，總的來說，雙向鏈表優(yōu)勢更明顯一些。

1、鏈表的分類

鏈表分為帶頭的、不帶頭的，單向的、雙向的，循環(huán)的、不循環(huán)的組合起來一共八種，而我們只學習常見的不帶頭單向不循環(huán)鏈表和帶頭雙向循環(huán)鏈表，也就是單鏈表和雙向鏈表。 雙向鏈表： 其實在上篇文章中我們將單鏈表的第一個節(jié)點稱作頭節(jié)點是不準確的，之所以這么稱呼是為了好理解，因為單鏈表是不帶頭的，雙向鏈表才有頭結點，也稱作哨兵位。

雙向鏈表頭節(jié)點內(nèi)不存有效數(shù)據(jù)，存的是無效的數(shù)據(jù)。哨兵位是不能改變的，只能改變其指向

2、雙向鏈表的實現(xiàn)

2.1雙向鏈表節(jié)點

雙向鏈表的節(jié)點需要存數(shù)據(jù)，還要存前一個和后一個節(jié)點的地址，因此雙向鏈表的節(jié)點為：

typedef int dlist_data_type;

//雙向鏈表節(jié)點

typedef struct dlist

{

dlist_data_type data;

struct dlist* next

struct dlist* prev;

}dlist;

2.2申請節(jié)點

不像單鏈表，雙向鏈表最少得有一個節(jié)點，就是頭節(jié)點，也叫哨兵位。 在增刪查改之前，雙向鏈表必須初始化一個哨兵位，哨兵位內(nèi)存一個無效數(shù)據(jù)。

申請的節(jié)點初始時兩個指針指向自己。

//申請節(jié)點

dlist* dlist_buy(dlist_data_type x)

{

dlist* newdlist = (dlist*)malloc(sizeof(dlist));

if (newdlist == NULL)

{

perror("malloc fail!");

return 1;

}

newdlist->data = x;

newdlist->next = newdlist;

newdlist->prev = newdlist;

return newdlist;

}

初始化哨兵位有以下兩種方法： 以參數(shù)的形式返回：

void dlist_init(dlist** pphead)

{

assert(pphead);

*pphead = dlist_buy(-1);

}

這個方法要求使用二級指針。 以返回值的形式返回：

dlist* dlist_init()

{

dlist* phead = dlist_buy(-1);

return phead;

}

這個方法更加簡單易理解。

2.3數(shù)據(jù)的打印和查找

數(shù)據(jù)的打印和查找跟單鏈表區(qū)別不大，就不再贅述了。 唯一需要注意的是結束循環(huán)的條件，當指針指向哨兵位時結束循環(huán)，而不是判NULL。

//打印數(shù)據(jù)

void dlist_print(dlist* phead)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

printf("%d->", pcur->data);

pcur = pcur->next;

}

printf("NULL\n");

}

//查找

dlist* dlist_find(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

if (pcur->data == x)

{

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

2.4頭插和尾插

與單鏈表不同的是，雙向鏈表的增刪查改操作不會改變哨兵位，因此只需要傳值調(diào)用就可。 雙向鏈表的插入操作需要對三個節(jié)點做修改，在修改的過程中，注意先修改新節(jié)點，再修改后一個節(jié)點，最后修改前一個節(jié)點。

//插入操作不改變哨兵位，因此傳一級指針即可

//尾插

void dlist_push_back(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* newdlist = dlist_buy(x);

//新尾節(jié)點

newdlist->prev = phead->prev;

newdlist->next = phead;

//舊尾節(jié)點

phead->prev->next = newdlist;

//頭節(jié)點（哨兵位）

phead->prev = newdlist;

}

//頭插

void dlist_push_front(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* newdlist = dlist_buy(x);

//新節(jié)點

newdlist->prev = phead;

newdlist->next = phead->next;

//舊節(jié)點

phead->next->prev = newdlist;

//哨兵位

phead->next = newdlist;

}

2.5頭刪和尾刪

刪除操作的前提是不能沒有節(jié)點（哨兵位不算），在刪除前還是先保存節(jié)點的地址，將雙向鏈表重新拼接起來后再釋放節(jié)點。

//尾刪

void dlist_pop_back(dlist* phead)

{

assert(phead);

assert(phead->next != phead);//雙向鏈表不能為空

dlist* del = phead->prev;

//新尾節(jié)點

del->prev->next = phead;

//哨兵位

phead->prev = del->prev;

free(del);

del = NULL;

}

//頭刪

void dlist_pop_front(dlist* phead)

{

assert(phead);

assert(phead->next != phead);

dlist* del = phead->next;

del->next->prev = phead;

phead->next = del->next;

free(del);

del = NULL;

}

2.6在指定位置插入、刪除數(shù)據(jù)

//在指定位置之后插入數(shù)據(jù)

void dlist_insert_back(dlist* pos, dlist_data_type x)

{

assert(pos);

dlist* newdlist = dlist_buy(x);

newdlist->prev = pos;

newdlist->next = pos->next;

pos->next->prev = newdlist;

pos->next = newdlist;

}

//刪除指定位置的節(jié)點

void dlist_erase(dlist* pos)

{

assert(pos);

dlist* del = pos;

pos->prev->next = pos->next;

pos->next->prev = pos->prev;

free(pos);

pos = NULL;

}

刪除指定位置的數(shù)據(jù)后，因為這個函數(shù)我們用的是傳值調(diào)用，在釋放掉指定位置的節(jié)點后，只是把形參指針置NULL，而實參指針依舊指向這個位置，因此在函數(shù)調(diào)用結束后要給實參指針置NULL。

2.7銷毀雙向鏈表

雙向鏈表銷毀的結束條件也是當遍歷指針指向頭節(jié)點時跳出循環(huán)，最后還要單獨釋放哨兵位，雙向鏈表的銷毀函數(shù)調(diào)用結束后，也要給指向哨兵位的指針置NULL。

//銷毀

void dlist_destroy(dlist* phead)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

dlist* next = pcur->next;

free(pcur);

pcur = next;

}

free(pcur);

pcur = NULL;

}

3、雙向鏈表完整代碼

dlist.h:

#pragma once

#include

#include

#include

typedef int dlist_data_type;

//雙向鏈表節(jié)點

typedef struct dlist

{

dlist_data_type data;

struct dlist* next;

struct dlist* prev;

}dlist;

//初始化

//插入數(shù)據(jù)之前，雙向鏈表必須初始化到只有一個頭節(jié)點（哨兵位）

//void dlist_init(dlist** pphead);//以參數(shù)的形式返回

dlist* dlist_init();//以返回值的形式返回

//打印數(shù)據(jù)

void dlist_print(dlist* phead);

//查找

dlist* dlist_find(dlist* phead, dlist_data_type x);

//尾插

void dlist_push_back(dlist* phead, dlist_data_type x);

//頭插

void dlist_push_front(dlist* phead, dlist_data_type x);

//尾刪

void dlist_pop_back(dlist* phead);

//頭刪

void dlist_pop_front(dlist* phead);

//在指定位置之后插入數(shù)據(jù)

void dlist_insert_back(dlist* pos, dlist_data_type x);

//刪除指定位置的節(jié)點

void dlist_erase(dlist* pos);

//銷毀

void dlist_destroy(dlist* phead);

dlist.c:

#define _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

//申請節(jié)點

dlist* dlist_buy(dlist_data_type x)

{

dlist* newdlist = (dlist*)malloc(sizeof(dlist));

if (newdlist == NULL)

{

perror("malloc fail!");

return 1;

}

newdlist->data = x;

newdlist->next = newdlist;

newdlist->prev = newdlist;

return newdlist;

}

//初始化

//void dlist_init(dlist** pphead)

//{

// assert(pphead);

// *pphead = dlist_buy(-1);

//}

dlist* dlist_init()

{

dlist* phead = dlist_buy(-1);

return phead;

}

//打印數(shù)據(jù)

void dlist_print(dlist* phead)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

printf("%d->", pcur->data);

pcur = pcur->next;

}

printf("NULL\n");

}

//查找

dlist* dlist_find(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

if (pcur->data == x)

{

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

//插入操作不改變哨兵位，因此傳一級指針即可

//尾插

void dlist_push_back(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* newdlist = dlist_buy(x);

//新尾節(jié)點

newdlist->prev = phead->prev;

newdlist->next = phead;

//舊尾節(jié)點

phead->prev->next = newdlist;

//頭節(jié)點（哨兵位）

phead->prev = newdlist;

}

//頭插

void dlist_push_front(dlist* phead, dlist_data_type x)

{

assert(phead);

dlist* newdlist = dlist_buy(x);

//新節(jié)點

newdlist->prev = phead;

newdlist->next = phead->next;

//舊節(jié)點

phead->next->prev = newdlist;

//哨兵位

phead->next = newdlist;

}

//尾刪

void dlist_pop_back(dlist* phead)

{

assert(phead);

assert(phead->next != phead);//雙向鏈表不能為空

dlist* del = phead->prev;

//新尾節(jié)點

del->prev->next = phead;

//哨兵位

phead->prev = del->prev;

free(del);

del = NULL;

}

//頭刪

void dlist_pop_front(dlist* phead)

{

assert(phead);

assert(phead->next != phead);

dlist* del = phead->next;

del->next->prev = phead;

phead->next = del->next;

free(del);

del = NULL;

}

//在指定位置之后插入數(shù)據(jù)

void dlist_insert_back(dlist* pos, dlist_data_type x)

{

assert(pos);

dlist* newdlist = dlist_buy(x);

newdlist->prev = pos;

newdlist->next = pos->next;

pos->next->prev = newdlist;

pos->next = newdlist;

}

//刪除指定位置的節(jié)點

void dlist_erase(dlist* pos)

{

assert(pos);

dlist* del = pos;

pos->prev->next = pos->next;

pos->next->prev = pos->prev;

free(pos);

pos = NULL;

}

//銷毀

void dlist_destroy(dlist* phead)

{

assert(phead);

dlist* pcur = phead->next;

while (pcur != phead)

{

dlist* next = pcur->next;

free(pcur);

pcur = next;

}

free(pcur);

pcur = NULL;

}

test.c:

#define _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

void test()

{

//dlist* plist = NULL;

//dlist_init(&plist);

dlist* plist = dlist_init();

//尾插

dlist_push_back(plist, 1);

dlist_push_back(plist, 2);

dlist_push_back(plist, 3);

dlist_print(plist);

//頭插

//dlist_push_front(plist, 1);

//dlist_push_front(plist, 2);

//dlist_push_front(plist, 3);

//dlist_print(plist);

//尾刪

//dlist_pop_back(plist);

//dlist_pop_back(plist);

//dlist_pop_back(plist);

//dlist_print(plist);

//頭刪

//dlist_pop_front(plist);

//dlist_print(plist);

//dlist_pop_front(plist);

//dlist_print(plist);

//dlist_pop_front(plist);

//dlist_print(plist);

//dlist* find = dlist_find(plist, 2);

//dlist_insert_back(find, 4);

//dlist_print(plist);

//dlist* find = dlist_find(plist, 2);

//dlist_erase(find);

//find = NULL;

//dlist_print(plist);

dlist_destroy(plist);

plist = NULL;//手動置空

}

int main()

{

test();

return 0;

}

4、順序表和鏈表比較

順序表鏈表（雙向鏈表）存儲空間上邏輯、物理上都連續(xù)邏輯上連續(xù)、物理上不一定連續(xù)隨機訪問復雜度O(1)復雜度O(N)任意位置插入或刪除數(shù)據(jù)需要挪動數(shù)據(jù)，復雜度O(N)只需要改變指針指向插入動態(tài)順序表，空間不夠時擴容，擴容本身就有消耗，還容易空間浪費沒有容量的概念應用場景數(shù)據(jù)高效存儲+頻繁訪問任意位置頻繁插入、刪除數(shù)據(jù)緩存利用率高低

順序表和鏈表優(yōu)勢互補，在不同的應用場景下能發(fā)揮各自的優(yōu)勢。

總結

如果應用場景中需要頻繁進行查找和刪除操作，并且能夠接受更多的內(nèi)存消耗，雙向鏈表可能更加合適。如果內(nèi)存比較有限或者對查找和刪除操作的效率要求不高，單鏈表可能更適合.

柚子快報邀請碼778899分享：【數(shù)據(jù)結構】雙向鏈表

http://yzkb.51969.com/

文章來源