前言：在前面我們學習了順序表、單向鏈表，今天我們在單鏈表的基礎上進一步來模擬實現(xiàn)一個帶頭雙向鏈表。
?? 博主CSDN主頁:衛(wèi)衛(wèi)衛(wèi)的個人主頁 ??
?? 專欄分類:數(shù)據(jù)結構 ??
??代碼倉庫:衛(wèi)衛(wèi)周大胖的學習日記??
??關注博主和博主一起學習!一起努力！
雙向鏈表
帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結構，都是帶頭雙向循環(huán)鏈表(如下圖所示)。通常我們會使用一個頭節(jié)點head其并不存儲數(shù)據(jù)只是作為一個哨兵位的作用負責指向下一個元素。
雙向鏈表的基本功能:
- 雙向鏈表的初始化
- 雙鏈表的銷毀
- 創(chuàng)建一個新的節(jié)點
- 打印鏈表中的元素
- 雙向鏈表尾插
- 雙向鏈表尾刪
- 雙向鏈表頭插
- 雙向鏈表的頭刪
- 雙鏈表元素查找
- 雙向鏈表在pos的前面進行插入
- 雙向鏈表刪除pos位置的節(jié)點
雙向鏈表的定義
//雙向鏈表的定義
typedef int LTDatatype;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDatatype val;
}LTNode;
雙向鏈表-創(chuàng)建新的節(jié)點
因為我們是動態(tài)開辟的鏈表，因此我們在對鏈表進行操作的時候，每插入一個節(jié)點時都要開辟一個節(jié)點，因此我們一樣寫一個接口函數(shù)來實現(xiàn)。
代碼思路:我們只需要直接和前面單鏈表一樣開辟思路即可，無非我們需要多管理一個prev指針，這里我們讓其置為空即可。
代碼實現(xiàn)：
LTNode* ListCreate(LTDatatype x)//創(chuàng)建一個新的節(jié)點
{
LTNode* newnode = malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->val = x;
newnode->prev = NULL;
return newnode;
}
雙向鏈表-初始化
代碼思路：因為雙向鏈表中，我們需要一個哨兵位(頭節(jié)點)來管理，因此我們在初始化的時候，需要開辟一個節(jié)點作為哨兵位，然后將其的pre和next指針置為空即可。
代碼實現(xiàn):
LTNode* ListInit()//雙鏈表的初始化
{
LTNode* phead = ListCreate(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
雙向鏈表-打印鏈表中的元素
代碼思路：由于我們是一個循環(huán)雙向鏈表，在前面的圖可以知道，我們不能夠直接通過判斷尾指針是否為空指針來判定是否是鏈表中的尾部元素，但是我們可以知道的是：鏈表中的最后一個節(jié)點的下一個節(jié)點，是該鏈表的頭部，所以我們通過判定鏈表中當前節(jié)點的下一個節(jié)點是不是頭節(jié)點，就可以知道是否是鏈表的尾部了。
代碼實現(xiàn):
void ListPrint(LTNode* pHead)//打印鏈表中的元素
{
assert(pHead);
LTNode* cur = pHead;
printf("哨兵位-> ");
while (pHead != cur->next)
{
printf("%d->", cur->next->val);
cur = cur->next;
}
printf("\n");
雙向鏈表-尾插
代碼思路:由于雙向循環(huán)鏈表的特性，我們可以知道哨兵位的pre指向的是尾部節(jié)點，因此我們在尾插的時候不用特意的去尋找尾節(jié)點，我們只需要，用哨兵位的前驅指針找到尾部節(jié)點，讓其指向新開辟的空間。因此：
- 通過哨兵位的前驅指針找到尾部節(jié)點
- 讓尾部節(jié)點指向新開辟的空間。
- 讓新開辟的空間的前驅指針指向原理的尾部節(jié)點，再讓其尾指針指向頭節(jié)點，即可完成雙向鏈表的尾插。(如下圖所示)
函數(shù)實現(xiàn)：
void ListPushBack(LTNode* pHead, LTDatatype x)//雙向鏈表尾插
{
assert(pHead);
LTNode* newnode = ListCreate(x);
LTNode* cur = pHead->prev;//尾結點
pHead->prev = newnode;
newnode->next = pHead;
newnode->prev = cur;
cur->next = newnode;
}
函數(shù)測試:
void Test_ListPushBack()
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
ListPrint(sl);
}
運行結果:
雙向鏈表-尾刪
代碼思路:這里我們依然要重復利用剛剛說到的循環(huán)雙鏈表的性質，我們直接通過哨兵位的前驅指針來找到尾結點，來幫助我們進行尾刪。
- 通過哨兵位前驅指針找到尾節(jié)點
- 找到尾結點的前驅指針，即倒數(shù)第二個節(jié)點，讓其指向頭節(jié)的前驅指針指向倒數(shù)第二個節(jié)點。
- 此時在將倒數(shù)第二個節(jié)點的尾部節(jié)點指向頭節(jié)點，即可完成尾刪，此時在釋放掉原本的尾部節(jié)點即可。(如下圖所示)
代碼實現(xiàn):
void ListPopBack(LTNode* pHead)//雙向鏈表尾刪
{
assert(pHead);
assert(pHead->next);
LTNode* tail = pHead->prev;//尾部節(jié)點
pHead->prev = tail->prev;//讓頭節(jié)點指向倒數(shù)第二個節(jié)點
tail->prev->next = pHead;//尾部節(jié)點指向頭節(jié)點
free(tail);
tail = NULL;
}
函數(shù)測試:
void Test_ListPopBack()//雙向鏈表尾刪
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("刪除前\n");
ListPrint(sl);
ListPopBack(sl);
printf("刪除后\n");
ListPrint(sl);
}
運行結果:
雙向鏈表-頭插
代碼思路:
- 我們將哨兵位的next指針指向新開辟的節(jié)點。
- 將新節(jié)點的前驅指針指向原本的哨兵位
- 將新節(jié)點的next指向原本的第二個節(jié)點
- 將原本的第二個節(jié)點的前驅指針指向新節(jié)點，即可完成頭插。(如下圖)
代碼實現(xiàn):
void ListPushFront(LTNode* pHead, LTDatatype x)//雙向鏈表頭插
{
assert(pHead);
LTNode* newnode = ListCreate(x);
LTNode* tail = pHead->next;//記錄頭節(jié)點的下一個節(jié)點的位置
pHead->next = newnode;//讓頭節(jié)點的下一個節(jié)點指向新節(jié)點
newnode->prev = pHead;//讓新節(jié)點的前驅指針指向頭節(jié)點
tail->prev = newnode;//讓原本的第二個節(jié)點的前驅指針指向newnode
newnode->next = tail;//新節(jié)點的尾部節(jié)點指針原本的第二個節(jié)點
}
函數(shù)測試:
void Test_ListPushFront()//雙向鏈表頭插
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("頭插前\n");
ListPrint(sl);
printf("頭插后\n");
ListPushFront(sl, 10);
ListPrint(sl);
}
運行結果：
雙向鏈表-頭刪
代碼思路:
- 我們直接通過哨兵位找到頭節(jié)點，然后將哨兵位的后驅指針指向頭節(jié)點的下一個節(jié)點。
- 將頭節(jié)點的下一個節(jié)點的前驅指針指向哨兵位
- 在將原本的頭節(jié)點釋放掉即可完成頭刪（如下圖）
代碼實現(xiàn):
void ListPopFront(LTNode* pHead)//雙向鏈表的頭刪
{
assert(pHead);
assert(pHead->next);
LTNode* tail = pHead->next;
pHead->next = tail->next;//找到第二個節(jié)點指向哨兵位后驅指針
tail->next->prev = pHead;//讓次節(jié)點指向哨兵位
free(tail);
tail = NULL;
}
函數(shù)測試:
void Test_ListPopFront()//雙向鏈表的頭刪
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("頭刪前\n");
ListPrint(sl);
printf("頭刪后\n");
ListPopFront(sl);
ListPrint(sl);
}
運行結果:
雙向鏈表-元素查找
代碼思路:
- 這里我們依然通過雙向鏈表的性質來幫助我們判斷是否走到了鏈表尾部。
- 我們定義一個cur指針去幫助我們查找
- 當cur碰到了尾部的時候說明查找完了，如果此時還沒找到就返回空即可
- 在查找的過程中碰到了要查找的值直接返回此時cur的地址即可。(如下圖)
代碼實現(xiàn):
LTNode* ListFind(LTNode* pHead, LTDatatype x)//雙鏈表查找
{
assert(pHead);
LTNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
函數(shù)測試：
void Test_ListFind()//雙向鏈表的查找
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("%p\n", ListFind(sl, 2));
printf("%p\n", ListFind(sl, 999));
}
運行結果:
雙向鏈表-在pos的前面進行插入
代碼思路:
- 我們找到要插入的pos的前一個節(jié)點，讓其的next指向新開辟的節(jié)點
- 在讓此時pos前驅指針所在的位置指向新開辟的節(jié)點
- 再讓原本插入的節(jié)點的next指向新開辟的節(jié)點
- 再讓新開辟的節(jié)點的前驅指針和next分別指向原本pos的前一個節(jié)點和指向pos。（如下圖）
代碼實現(xiàn):
void ListInsert(LTNode* pos, LTDatatype x)// 雙向鏈表在pos的前面進行插入
{
LTNode* newnode = ListCreate(x);
LTNode* cur = pos->prev;//找到pos前的一個節(jié)點
pos->prev = newnode;//讓其前一個結點指向新結點
cur->next = newnode;
newnode->prev = cur;
newnode->next = pos;
}
函數(shù)測試:
void Test_ListInsert()
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("插入前\n");
ListPrint(sl);
ListInsert(ListFind(sl, 2), 99);
printf("插入后\n");
ListPrint(sl);
}
運行結果:
雙向鏈表-刪除pos所在的位置
代碼思路:
- 我們找到pos所在位置的下個一個節(jié)點讓其指向pos所在位置的前一個結點
- 此時在釋放掉pos所在的位置即可完成刪除
代碼實現(xiàn):
void ListErase(LTNode* pos)// 雙向鏈表刪除pos位置的節(jié)點
{
assert(pos);
LTNode* tail = pos->next;
tail->prev = pos->prev;
pos->prev->next = tail;
free(pos);
pos = NULL;
}
函數(shù)測試:
void Test_ListErase()
{
LTNode* sl = ListInit();
ListPushBack(sl, 5);
ListPushBack(sl, 2);
ListPushBack(sl, 1);
ListPushBack(sl, 8);
printf("刪除前\n");
ListPrint(sl);
printf("刪除后\n");
ListErase(ListFind(sl, 2));
ListPrint(sl);
}
運行結果:
雙向鏈表-鏈表的銷毀
關于雙向鏈表的銷毀這里就不做過多的總結了，這個和前面的打印元素有比較像，因此不懂的可以參考一下即可。
代碼實現(xiàn):
void ListDestory(LTNode* pHead)//雙鏈表的銷毀
{
assert(pHead);
LTNode* cur = pHead->next;
while (pHead != cur)
{
LTNode* tail = cur->next;
free(cur);
cur = tail;
}
free(pHead);
}
總結
到這里我們可以發(fā)現(xiàn)，當我們寫了一個插入之后會發(fā)現(xiàn)，那雙向鏈表的頭插和尾插，我們可以直接用我們剛剛寫的插入的函數(shù)直接來實現(xiàn)，就完全沒必要單獨寫尾插和頭插了，至于為什么放在最后才說，是因為作者想和大家一起鍛煉一下自己的思維能力，這里直接放代碼就不演示了。文章來源：http://www.zghlxwxcb.cn/news/detail-791786.html
void ListPushBack(LTNode* pHead, LTDatatype x)//雙向鏈表尾插
{
assert(pHead);
ListInsert(pHead,x);//直接再phead之前插入即可
}
void ListPushFront(LTNode* pHead, LTDatatype x)//雙向鏈表頭插
{
assert(pHead);
ListInsert(pHead->next, x);
}
結語：今天的內容就到這里吧，謝謝各位的觀看，如果有講的不好的地方也請各位多多指出，作者每一條評論都會讀的，謝謝各位。文章來源地址http://www.zghlxwxcb.cn/news/detail-791786.html
到了這里，關于【數(shù)據(jù)結構】雙向帶頭循環(huán)鏈表的實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
