??????????????????????????????? ??? ?食用指南：本文在有C基礎的情況下食用更佳?
????????????????????????????? ??? ? ??這就不得不推薦此專欄了：C語言
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??雙向鏈表前置知識：單鏈表?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ??????今日夜電波：Departures ~あなたにおくるアイの歌~ —EGOIST?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3:12?━━━━━━???──────── 4:13? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????? ? ? ?? ? ?? ? ? ? ?? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???關注??點贊??收藏您的每一次鼓勵都是對我莫大的支持???
一、雙向鏈表介紹
什么是雙向鏈表？
? ? ? ? 它是是一種常見的線性數據結構，它由一系列節(jié)點組成，每個節(jié)點包含兩個指針，一個指向前一個節(jié)點（pre指針），一個指向后一個節(jié)點（next指針）。
雙向鏈表的基本結構？
????????一張圖讓你明白：
? ? ? ? 注：此為帶哨兵的雙向鏈表
? ? ? ? ?注：next表示為指向下一個節(jié)點的指針，prev表示為指向上一個節(jié)點的指針，而head則是作為標兵的存在，里面不存數據，其他data存數據，此雙向鏈表無指向NULL的指針，讀者可在下文初始化雙向鏈表得到疑惑的答案。
與單鏈表相比的優(yōu)勢？
-
雙向遍歷：由于每個節(jié)點都存儲了前向和后向指針，可以從頭到尾或者從尾到頭方便地遍歷鏈表。這樣的遍歷方式在某些場景下非常有用，特別是需要反向操作或者雙向查找的情況。
-
方便插入和刪除：在雙向鏈表中，插入和刪除操作相對容易。通過修改前后指針，可以方便地調整節(jié)點的連接關系，無需像單鏈表那樣需要在刪除節(jié)點時找到其前驅節(jié)點。
-
更靈活的操作：雙向鏈表相比單鏈表，對于節(jié)點的操作更加靈活。例如，在單鏈表中，如果要刪除某個節(jié)點，需要先找到它的前驅節(jié)點，而在雙向鏈表中，可以直接通過節(jié)點本身進行刪除操作。
-
提高性能：在某些情況下，雙向鏈表可以提高性能。例如，在需要頻繁從鏈表中刪除節(jié)點或者在給定節(jié)點后插入新節(jié)點的情況下，雙向鏈表可以更高效地完成這些操作。
????????總的來說，雙向鏈表在一些特定場景下相比單鏈表具有更多的優(yōu)勢和靈活性，雙向鏈表是單鏈表的優(yōu)化！
二、總體思路
如何實現？
????????參照??雙向鏈表前置知識：單鏈表?（這是個鏈接，快點！），我們同樣需要實現增、刪、查、改。同樣的我們需要先定義好節(jié)點，以此得到基本的結構->接著定義好接口（定義完后發(fā)現比單鏈表簡單多了）->最后按照接口實現每一個功能 。
? ? ? ? 節(jié)點的定義（結構體）
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
? ? ? ? 接口的定義?
// 創(chuàng)建返回鏈表的頭結點.
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos);三、具體每個接口函數的實現
? ? ? ? 1、初始化（重點）
ListNode* ListCreate()
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (!node)
{
perror("malloc fail:");
exit(-1);
}
node->_next = node;
node->_prev = node;
return node;
}? ? ? ? 可以看到初始化的作用是建立了一個標兵，這個標兵沒有被賦值，因為他的值是多少無關緊要，重點在于：他的next指針指向的是他自己，而prev指針指向的也是他自己。這說明了什么？這說明了雙向鏈表的最開始就是在沒有任何值的時候就只有一個標兵，也就是說雙向鏈表的每一個指針都不是空的，都是有指向的，他們指向的地址不可能為NULL。
? ? ? ? 2、銷毀鏈表
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* tmp = cur->_next;
free(cur);
cur = tmp;
}
free(pHead);
}
? ? ? ? 3、查找功能（返回pos的地址）
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
return cur;
cur = cur->_next;
}
return NULL;
}
? ? ? ? 4、插入節(jié)點的實現（基于查找功能）
ListNode* BuyNode(LTDataType x)//實現節(jié)點的獲取
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->_data = x;
node->_next = NULL;
node->_prev = NULL;
return node;
}
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyNode(x);
ListNode* dist = pos->_prev;
dist->_next = newnode;
newnode->_prev = dist;
newnode->_next = pos;
pos->_prev = newnode;
}? ? ?特別注意
????????? 注意：在實現了 插入的功能后，其實一切都簡單了起來，比如頭插等等，只需要幾行代碼就能完成操作，而下面的刪除操作的實現對于頭刪等等都是僅需要幾行代碼就能實現，因此，我們如果要快速的寫完一個單鏈表或者其他鏈表，最好是從插入和刪除開始寫！o.o
? ? ? ? 5、刪除節(jié)點（基于查找功能）
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->_prev;
ListNode* posNext = pos->_next;
posPrev->_next = posNext;
posNext->_prev = posPrev;
free(pos);
}
? ? ? ? 6、尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
//ListInsert(pHead, x);//此為簡化，如要簡化代碼，此段帶碼后的代碼可都不要
ListNode* newnode = BuyNode(x);
pHead->_prev->_next = newnode;
newnode->_prev=pHead->_prev;
newnode->_next = pHead;
pHead->_prev = newnode;
}
? ? ? ? 7、尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
//ListErase(pHead->_prev);//此為簡化，如要簡化代碼，此段帶碼后的代碼可都不要
if (pHead->_prev != pHead)
{
ListNode* tmp = pHead->_prev;
pHead->_prev = tmp->_prev;
tmp->_prev->_next = pHead;
free(tmp);
tmp = NULL;
}
}
? ? ? ? 8、頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
//ListInsert(pHead->_next, x);//此為簡化，如要簡化代碼，此段帶碼后的代碼可都不要
ListNode* newnode = BuyNode(x);
newnode->_next=pHead->_next;
newnode->_prev = pHead;
pHead->_next->_prev = newnode;
pHead->_next = newnode;
}? ? ? ? 9、頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
//ListErase(pHead->_next);//此為簡化，如要簡化代碼，此段帶碼后的代碼可都不要
if (pHead->_next != pHead)
{
ListNode* node = pHead->_next;
node->_next->_prev = pHead;
pHead->_next = node->_next;
free(node);
node = NULL;
}
}????????10、打印
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->_next;
printf("pHead<=>");
while (cur != pHead)
{
printf("%d<=>", cur->_data);
cur = cur->_next;
}
printf("\n");
}四、總體代碼
1、頭文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實現
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
// 創(chuàng)建返回鏈表的頭結點.
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos);2、主體函數文件
#include"list.h"
ListNode* BuyNode(LTDataType x)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->_data = x;
node->_next = NULL;
node->_prev = NULL;
return node;
}
ListNode* ListCreate()
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (!node)
{
perror("malloc fail:");
exit(-1);
}
node->_next = node;
node->_prev = node;
return node;
}
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* tmp = cur->_next;
free(cur);
cur = tmp;
}
free(pHead);
}
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->_next;
printf("pHead<=>");
while (cur != pHead)
{
printf("%d<=>", cur->_data);
cur = cur->_next;
}
printf("\n");
}
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
//ListInsert(pHead, x);
ListNode* newnode = BuyNode(x);
pHead->_prev->_next = newnode;
newnode->_prev=pHead->_prev;
newnode->_next = pHead;
pHead->_prev = newnode;
}
void ListPopBack(ListNode* pHead)
{
assert(pHead);
//ListErase(pHead->_prev);
if (pHead->_prev != pHead)
{
ListNode* tmp = pHead->_prev;
pHead->_prev = tmp->_prev;
tmp->_prev->_next = pHead;
free(tmp);
tmp = NULL;
}
}
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
//ListInsert(pHead->_next, x);
ListNode* newnode = BuyNode(x);
newnode->_next=pHead->_next;
newnode->_prev = pHead;
pHead->_next->_prev = newnode;
pHead->_next = newnode;
}
void ListPopFront(ListNode* pHead)
{
assert(pHead);
//ListErase(pHead->_next);
if (pHead->_next != pHead)
{
ListNode* node = pHead->_next;
node->_next->_prev = pHead;
pHead->_next = node->_next;
free(node);
node = NULL;
}
}
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
return cur;
cur = cur->_next;
}
return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyNode(x);
ListNode* dist = pos->_prev;
dist->_next = newnode;
newnode->_prev = dist;
newnode->_next = pos;
pos->_prev = newnode;
}
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* posPrev = pos->_prev;
ListNode* posNext = pos->_next;
posPrev->_next = posNext;
posNext->_prev = posPrev;
free(pos);
}
3、測試用例
#include"list.h"
void text()
{
ListNode* phead = ListCreate();
ListPushBack(phead, 1);
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPrint(phead);
ListPopBack(phead);
ListPrint(phead);
ListPushFront(phead, 10);
ListPushFront(phead, 20);
ListPushFront(phead, 30);
ListPrint(phead);
ListPopFront(phead);
ListPrint(phead);
ListNode* pos = ListFind(phead, 20);
if (pos)
{
ListInsert(pos, 300);
}
ListPrint(phead);
ListErase(pos);
ListPrint(phead);
ListDestory(phead);
}
int main()
{
text();
return 0;
}? ? ? ? 測試結果：
????????????????????感謝你耐心的看到這里?( ′???` )比心，如有哪里有錯誤請?zhí)咭荒_作者o(╥﹏╥)o！?
???????????????????????????????????????? ? ? ?
文章來源：http://www.zghlxwxcb.cn/news/detail-641178.html
?????????????????????????????????????????????????????????????????????????給個三連再走嘛~??文章來源地址http://www.zghlxwxcb.cn/news/detail-641178.html
到了這里，關于【數據結構】—C語言實現雙向鏈表（超詳細!）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
