柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表
柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表
Hi~！這里是奮斗的小羊，很榮幸您能閱讀我的文章，誠(chéng)請(qǐng)?jiān)u論指點(diǎn)，歡迎歡迎 ~~ ??個(gè)人主頁(yè)：奮斗的小羊 ??所屬專欄：數(shù)據(jù)結(jié)構(gòu)
?本系列文章為個(gè)人學(xué)習(xí)筆記，在這里撰寫(xiě)成文一為鞏固知識(shí)，二為記錄我的學(xué)習(xí)過(guò)程及理解。文筆、排版拙劣，望見(jiàn)諒。
目錄
前言1、鏈表的分類2、雙向鏈表的實(shí)現(xiàn)2.1雙向鏈表節(jié)點(diǎn)2.2申請(qǐng)節(jié)點(diǎn)2.3數(shù)據(jù)的打印和查找2.4頭插和尾插2.5頭刪和尾刪2.6在指定位置插入、刪除數(shù)據(jù)2.7銷毀雙向鏈表
3、雙向鏈表完整代碼4、順序表和鏈表比較總結(jié)
前言
單鏈表只能通過(guò)某個(gè)節(jié)點(diǎn)的地址單向的訪問(wèn)數(shù)據(jù)，而雙向鏈表可以通過(guò)某個(gè)節(jié)點(diǎn)的地址雙向的訪問(wèn)數(shù)據(jù)，增刪查改的效率更高，但是代碼的實(shí)現(xiàn)卻比單鏈表簡(jiǎn)單，總的來(lái)說(shuō)，雙向鏈表優(yōu)勢(shì)更明顯一些。
1、鏈表的分類
鏈表分為帶頭的、不帶頭的，單向的、雙向的，循環(huán)的、不循環(huán)的組合起來(lái)一共八種，而我們只學(xué)習(xí)常見(jiàn)的不帶頭單向不循環(huán)鏈表和帶頭雙向循環(huán)鏈表，也就是單鏈表和雙向鏈表。 雙向鏈表： 其實(shí)在上篇文章中我們將單鏈表的第一個(gè)節(jié)點(diǎn)稱作頭節(jié)點(diǎn)是不準(zhǔn)確的，之所以這么稱呼是為了好理解，因?yàn)閱捂湵硎遣粠ь^的，雙向鏈表才有頭結(jié)點(diǎn)，也稱作哨兵位。
雙向鏈表頭節(jié)點(diǎn)內(nèi)不存有效數(shù)據(jù)，存的是無(wú)效的數(shù)據(jù)。哨兵位是不能改變的，只能改變其指向
2、雙向鏈表的實(shí)現(xiàn)
2.1雙向鏈表節(jié)點(diǎn)
雙向鏈表的節(jié)點(diǎn)需要存數(shù)據(jù)，還要存前一個(gè)和后一個(gè)節(jié)點(diǎn)的地址，因此雙向鏈表的節(jié)點(diǎn)為：
typedef int dlist_data_type;
//雙向鏈表節(jié)點(diǎn)
typedef struct dlist
{
dlist_data_type data;
struct dlist* next
struct dlist* prev;
}dlist;
2.2申請(qǐng)節(jié)點(diǎn)
不像單鏈表，雙向鏈表最少得有一個(gè)節(jié)點(diǎn)，就是頭節(jié)點(diǎn)，也叫哨兵位。 在增刪查改之前，雙向鏈表必須初始化一個(gè)哨兵位，哨兵位內(nèi)存一個(gè)無(wú)效數(shù)據(jù)。
申請(qǐng)的節(jié)點(diǎn)初始時(shí)兩個(gè)指針指向自己。
//申請(qǐng)節(jié)點(diǎn)
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);
}
這個(gè)方法要求使用二級(jí)指針。 以返回值的形式返回：
dlist* dlist_init()
{
dlist* phead = dlist_buy(-1);
return phead;
}
這個(gè)方法更加簡(jiǎn)單易理解。
2.3數(shù)據(jù)的打印和查找
數(shù)據(jù)的打印和查找跟單鏈表區(qū)別不大，就不再贅述了。 唯一需要注意的是結(jié)束循環(huán)的條件，當(dāng)指針指向哨兵位時(shí)結(jié)束循環(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頭插和尾插
與單鏈表不同的是，雙向鏈表的增刪查改操作不會(huì)改變哨兵位，因此只需要傳值調(diào)用就可。 雙向鏈表的插入操作需要對(duì)三個(gè)節(jié)點(diǎn)做修改，在修改的過(guò)程中，注意先修改新節(jié)點(diǎn)，再修改后一個(gè)節(jié)點(diǎn)，最后修改前一個(gè)節(jié)點(diǎn)。
//插入操作不改變哨兵位，因此傳一級(jí)指針即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);
//新尾節(jié)點(diǎn)
newdlist->prev = phead->prev;
newdlist->next = phead;
//舊尾節(jié)點(diǎn)
phead->prev->next = newdlist;
//頭節(jié)點(diǎn)（哨兵位）
phead->prev = newdlist;
}
//頭插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);
//新節(jié)點(diǎn)
newdlist->prev = phead;
newdlist->next = phead->next;
//舊節(jié)點(diǎn)
phead->next->prev = newdlist;
//哨兵位
phead->next = newdlist;
}
2.5頭刪和尾刪
刪除操作的前提是不能沒(méi)有節(jié)點(diǎn)（哨兵位不算），在刪除前還是先保存節(jié)點(diǎn)的地址，將雙向鏈表重新拼接起來(lái)后再釋放節(jié)點(diǎn)。
//尾刪
void dlist_pop_back(dlist* phead)
{
assert(phead);
assert(phead->next != phead);//雙向鏈表不能為空
dlist* del = phead->prev;
//新尾節(jié)點(diǎn)
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é)點(diǎn)
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ù)后，因?yàn)檫@個(gè)函數(shù)我們用的是傳值調(diào)用，在釋放掉指定位置的節(jié)點(diǎn)后，只是把形參指針置NULL，而實(shí)參指針依舊指向這個(gè)位置，因此在函數(shù)調(diào)用結(jié)束后要給實(shí)參指針置NULL。
2.7銷毀雙向鏈表
雙向鏈表銷毀的結(jié)束條件也是當(dāng)遍歷指針指向頭節(jié)點(diǎn)時(shí)跳出循環(huán)，最后還要單獨(dú)釋放哨兵位，雙向鏈表的銷毀函數(shù)調(diào)用結(jié)束后，也要給指向哨兵位的指針置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é)點(diǎn)
typedef struct dlist
{
dlist_data_type data;
struct dlist* next;
struct dlist* prev;
}dlist;
//初始化
//插入數(shù)據(jù)之前，雙向鏈表必須初始化到只有一個(gè)頭節(jié)點(diǎn)（哨兵位）
//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é)點(diǎn)
void dlist_erase(dlist* pos);
//銷毀
void dlist_destroy(dlist* phead);
dlist.c:
#define _CRT_SECURE_NO_WARNINGS
#include "dlist.h"
//申請(qǐng)節(jié)點(diǎn)
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;
}
//插入操作不改變哨兵位，因此傳一級(jí)指針即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);
//新尾節(jié)點(diǎn)
newdlist->prev = phead->prev;
newdlist->next = phead;
//舊尾節(jié)點(diǎn)
phead->prev->next = newdlist;
//頭節(jié)點(diǎn)（哨兵位）
phead->prev = newdlist;
}
//頭插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);
//新節(jié)點(diǎn)
newdlist->prev = phead;
newdlist->next = phead->next;
//舊節(jié)點(diǎn)
phead->next->prev = newdlist;
//哨兵位
phead->next = newdlist;
}
//尾刪
void dlist_pop_back(dlist* phead)
{
assert(phead);
assert(phead->next != phead);//雙向鏈表不能為空
dlist* del = phead->prev;
//新尾節(jié)點(diǎn)
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é)點(diǎn)
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;//手動(dòng)置空
}
int main()
{
test();
return 0;
}
4、順序表和鏈表比較
順序表鏈表（雙向鏈表）存儲(chǔ)空間上邏輯、物理上都連續(xù)邏輯上連續(xù)、物理上不一定連續(xù)隨機(jī)訪問(wèn)復(fù)雜度O(1)復(fù)雜度O(N)任意位置插入或刪除數(shù)據(jù)需要挪動(dòng)數(shù)據(jù)，復(fù)雜度O(N)只需要改變指針指向插入動(dòng)態(tài)順序表，空間不夠時(shí)擴(kuò)容，擴(kuò)容本身就有消耗，還容易空間浪費(fèi)沒(méi)有容量的概念應(yīng)用場(chǎng)景數(shù)據(jù)高效存儲(chǔ)+頻繁訪問(wèn)任意位置頻繁插入、刪除數(shù)據(jù)緩存利用率高低
順序表和鏈表優(yōu)勢(shì)互補(bǔ)，在不同的應(yīng)用場(chǎng)景下能發(fā)揮各自的優(yōu)勢(shì)。
總結(jié)
如果應(yīng)用場(chǎng)景中需要頻繁進(jìn)行查找和刪除操作，并且能夠接受更多的內(nèi)存消耗，雙向鏈表可能更加合適。如果內(nèi)存比較有限或者對(duì)查找和刪除操作的效率要求不高，單鏈表可能更適合.
柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表
文章來(lái)源
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Falabella時(shí)尚廊
