目錄
引言
一、雙鏈表基礎
1.1、什么是雙鏈表？
1.2、雙鏈表節點的結構定義
二、雙鏈表的基本操作
2.1、雙鏈表的初始化
2.2、尾插法
2.3、頭插
2.4、判斷雙鏈表是否為空
2.5、尾刪法
2.6、頭刪法
2.7、查找
2.8、雙鏈表在指定位置之前插入
2.9、雙鏈表刪除指定節點
2.10、雙鏈表的銷毀
三、總結
結語
引言
在程序設計中，數據結構扮演著至關重要的角色。鏈表作為一種基礎且強大的數據結構，廣泛應用于需要動態內存管理和高效插入刪除的場景。而雙鏈表作為鏈表的一種拓展，具有雙向遍歷的能力，為我們的算法設計提供了更大的靈活性。本篇博客將帶你深入了解C語言中的雙鏈表，包括其定義、基本操作以及實際應用，讓你在掌握數據結構的同時，提高編程的效率與能力
一、雙鏈表基礎
1.1、什么是雙鏈表？
雙鏈表同單鏈表一樣，是一種線性結構的數據結構，與單鏈表不同的是，雙鏈表的每個節點有兩個指針，分別指向下一個節點和上一個節點。這使得雙鏈表既可以向前遍歷，也可以向后遍歷，極大的節省了時間，但代價就是每個節點所占用的空間變大了。
1.2、雙鏈表節點的結構定義
typedef int DLElemType;
typedef struct DListNode
{DLElemType data; //節點的數據域struct DListNode* next; //指向下一個節點struct DListNode* prev; //指向上一個節點
}DListNode;二、雙鏈表的基本操作
2.1、雙鏈表的初始化
void DLInit(DListNode** pphead)
{*pphead = (DListNode*)malloc(sizeof(DListNode));if (*pphead == NULL){perror("malloc fail!");exit(1);}(*pphead)->data = 0;(*pphead)->next = (*pphead)->prev = *pphead;
}這里要注意的是，為了與其他類型的鏈表區分，雙鏈表的初始化讓兩個指針都指向自己
2.2、尾插法
void DLPushBack(DListNode* phead , DLElemType x)
{assert(phead);DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}在單鏈表中，我們要進行尾差就必須遍歷找到最后一個節點，但是在雙鏈表中，我們只需要找到頭結點的prev指向就可以了，非常的方便
2.3、頭插
在此之前，我們需要編寫一個函數來實現新節點的創建，一次來提高效率：
//創建一個新的雙鏈表節點
DListNode* BuyDListNode(DLElemType x)
{DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode;
}接下來就是頭插法的實現了
//頭插
void DLTPushFront(DListNode* phead, DLElemType x)
{assert(phead);DListNode* newnode = BuyDListNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}2.4、判斷雙鏈表是否為空
//判斷雙鏈表是否為空
bool DLTEmpty(DListNode* phead)
{assert(phead);return phead->next == phead;
}2.5、尾刪法
void DLTPopBack(DListNode* phead)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->prev;pcur->prev->next = phead;phead->prev = pcur->prev;free(pcur);pcur = NULL;
}2.6、頭刪法
void DLTPopFront(DListNode* phead)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->next;phead->next = pcur->next;pcur->next->prev = phead;free(pcur);pcur = NULL;
}2.7、查找
DListNode* DLTFind(DListNode* phead, DLElemType x)
{assert(phead && !DLTEmpty(phead));DListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}2.8、雙鏈表在指定位置之前插入
void DLTInsert(DListNode* pos, DLElemType x)
{assert(pos);DListNode* newnode = BuyDListNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}2.9、雙鏈表刪除指定節點
void DLTErase(DListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}2.10、雙鏈表的銷毀
void DLTDestory(DListNode** pphead)
{assert(pphead && *pphead);DListNode* pcur = (*pphead)->next;while (pcur != *pphead){DListNode* tmd = pcur->next;free(pcur);pcur = tmd;}free(*pphead);*pphead = NULL;
}三、總結
掌握了單鏈表，那么掌握雙鏈表也是分分鐘的事，本篇以有哨兵位，循環的雙鏈表為目的編寫的代碼。雙鏈表的實際應用廣泛，例如播放器的歌曲上一首下一首 ，以及網頁的進一步退一步等。雙鏈表非常好掌握，這里就不多贅述了
結語
通過對雙鏈表的系統講解與實踐操作，相信你已經對其核心思想與實現細節有了更深的理解。雙鏈表不僅是數據存儲的利器，更是算法設計中不可或缺的基礎結構。在今后的學習與開發中，靈活運用雙鏈表，將會讓你的代碼更加高效、優雅。希望這篇文章能為你打開鏈式結構世界的大門，助你在編程之路上越走越遠！
)
