數據結構——帶頭雙向循環鏈表（c語言實現）

1.單鏈表和雙向鏈表對比

2.雙向鏈表實現

2.1 創建新節點

2.2 鏈表初始化?

2.3 尾插?

2.4 頭插?

2.5 尾刪?

2.6 頭刪?

2.7 查找?

2.8 指定位置后插入數據?

2.9 刪除指定節點?

2.10 銷毀鏈表

2.11?打印鏈表?

?前言：

? ? ?我們在前幾期詳細地講解了不帶頭單向不循環鏈表（單鏈表），使用它的底層代碼實現了一個簡單的通訊錄項目，也介紹了鏈表分為八種，但是其中最常用的只有兩種：（1）不帶頭單向不循環鏈表，（2）帶頭雙向循環鏈表，今天我們要講解的就是第二種帶頭雙向循環鏈表

1.單鏈表和雙向鏈表對比

在介紹雙向鏈表之前，我們先來對比一下單鏈表和雙向鏈表的區別。

這是單鏈表：

這是雙向鏈表：

? ? ? ? 雙向鏈表的特點是每相鄰兩個節點都相互連接，每個節點都有三個部分，包括data，next，prev，其中data負責存放數據，next負責存放后一個節點的地址，prev負責存放前一個節點的地址，最后一個節點和頭節點（哨兵位）相互連接，形成了一個循環雙向鏈表，那么什么是哨兵位呢，哨兵位就是雙向鏈表的頭節點，它不存放有效數據，只存放第一個有序數據的節點的地址和最后一個有序數據節點的地址。?

? ? ? ?那么它們的區別是什么呢？

1. 無頭單向非循環鏈表： 結構簡單 ，一般不會單獨用來存數據。實際中更多是作為 其他數據結構的子結 構，如哈希桶、圖的鄰接表等等。另外這種結構在 筆試面試 中出現很多。

2. 帶頭雙向循環鏈表： 結構最復雜 ，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了。

2.雙向鏈表實現

? 介紹完了雙向鏈表的區別我們接下來就要著手開始用代碼實現雙向鏈表了。由于代碼可能較多，我們將雙向鏈表的代碼分成了三個文件，分別是List.h,List.c和tste.c文件：

在list.h文件中，我們要包含我們會用到的頭文件，其他文件只要包含List.h文件就可以使用這些頭文件了：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

雙向鏈表的實現也是在此文件中，由于我們不知道將來使用鏈表會存放什么樣的數據，所以我們使用typedef對這個數據的類型改名，我們實現鏈表使用的是int類型，所以我們對int改名：

typedef int ListNodeData;

鏈表中的next和prev鏈表是用來存放節點地址的，所以它們為指針類型，而為了方便使用，我們將鏈表使用typedf改名，下面是雙向鏈表實現：

typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;

2.1 創建新節點

創建新節點我們使用malloc從堆申請一塊LTNode類型大小的內存，它的data類型用來存放將來要插入的數據，prev和next指針在創建這個節點時先讓它指向自己，如果要創建新節點，就調用這個函數，它會返回一個指向這塊空間的指針：

LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//創建一個新節點

2.2 鏈表初始化?

在最初創建一個鏈表時，它的內部為空，什么也沒有，我們初始化應該此鏈表讓它至少有一個哨兵位：

void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化

2.3 尾插?

尾插操作應該先創建一個新節點，插入順序為：先讓新節點的prev指針指向最后一個節點，然后讓新節點的next指針指向哨兵位實現循環，以上的兩步都不會影響舊節點，接下來就是讓最后一個節點的next指針指向這個新節點，然后讓哨兵位的prev指針指向新節點完成尾插：

具體實現代碼為：

void LTPushBack(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//尾插

2.4 頭插?

? ? ?頭插操作并不是將新節點放在哨兵位之前，而是將新節點放在第一個有效數據節點之前，所以我們應該將新節點放在哨兵位的后面。先創建一個新節點，讓新節點的prev指針指向哨兵位，讓它的next指針指向哨兵位的next指向的節點，以上兩步不會影響任何節點，做完這兩步后，先讓哨兵位后面那個節點的prev指針指向新節點，然后讓哨兵位的next指針指向新節點，這兩步不能調換順序，否則會找不到哨兵位后面那個節點，下面是代碼實現：

void LTPushFront(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}//頭插

2.5 尾刪?

? ?執行刪除操作之前我們應該先判斷這個鏈表除哨兵位之外有沒有其他節點，如果沒有，就無法刪除，而尾刪操作也比較簡單，只需要讓尾節點的前一個節點的next指針指向哨兵位，然后讓哨兵位的prev指針指向位尾節點，以上過程需要創建一個新變量，否則無法找到我們要刪除的節點，接著釋放掉尾節點后置空就可以了：

void LTPopBack(LTNode* phead)
{assert(phead&&phead->next);LTNode* del = phead->prev;del->prev->next = del->next;del->next->prev = del->prev;free(del);del = NULL;}//尾刪

畫圖演示：

2.6 頭刪?

? 頭刪操作與尾刪類似，如果沒有兩個及以上節點的話無法執行刪除操作，頭刪要刪除的是哨兵位后面那個節點，所以我們先創建一個指針存放我們要刪除節點的地址，將哨兵位的next指針指向我們要刪除節點的下一個節點，然后將我們要刪除節點的下一個節點的prev指針指向哨兵位，完成這些操作后釋放我們要刪除的節點然后置空：

void LTPopFront(LTNode* phead)
{assert(phead && phead->next);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//頭刪

2.7 查找?

如果我們要查找一個節點，應該先判斷鏈表是否為空，然后將我們要查找的節點的數據與鏈表中節點的數據一一對比，如果數據內容相同，說明找到了，將這個節點返回，如果循環一圈還沒有找到，說明鏈表中不存在這樣的節點，返回應一個空指針：

LTNode* LTFind(LTNode* phead, ListNodeData x)
{assert(phead && phead->next);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函數

2.8 指定位置后插入數據?

我們可以先調用查找函數，然后調用它返回的節點，試著在它的后面插入數據，而它的操作與頭插非常相像，只是將哨兵位改成了我們指定的節點：

void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定節點后插入數據

2.9 刪除指定節點?

刪除節點我們需要先判斷鏈表中是否有兩個及以上節點，否則無法刪除，刪除指定節操作我們先將指定節點的前一個節點的next指向我們指定節點的下一個節點，然后將指定節點的下一個節點的prev指針指向指定節點的前一個節點，這個過程不需要創建中間變量，因為我們有指定節點的地址：

void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定刪除節點

2.10 銷毀鏈表

我們鏈表的每一個節點都是使用malloc函數手動在堆上申請的，需要我們手動釋放：

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}}//銷毀鏈表

2.11?打印鏈表?

指行這么多插入刪除操作我們如果測試的話就使用這個函數打印出來，而打印函數只需要循環打印這個鏈表一次就可以了：

void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//打印

接下來我們使用這個函數來測試一下我們的方法：

可以看到我們的方法都沒有問題，那么這期的雙向鏈表就到此結束啦，我將代碼放在下面，感興趣的小伙伴可以試試哦。

List.h :

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ListNodeData;
typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;LTNode* LTFind(LTNode* phead, ListNodeData x);//查找void LTInit(LTNode** pphead);//初始化void LTPushBack(LTNode* phead, ListNodeData x);
//尾插void LTPrint(LTNode* phead);//打印鏈表void LTPushFront(LTNode* phead, ListNodeData x);
//頭插void LTPopBack(LTNode* phead);//尾刪void LTPopFront(LTNode* phead);//頭刪void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x);
//指定節點后刪除void LTErase(LTNode* phead, LTNode* pop);
//指定位置刪除void LTDestroy(LTNode* phead);
//銷毀鏈表

List.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//創建一個新節點LTNode* LTFind(LTNode* phead, ListNodeData x)
{assert(phead && phead->next);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函數void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化void LTPushBack(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//尾插void LTPushFront(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}//頭插void LTPopBack(LTNode* phead)
{assert(phead&&phead->next);LTNode* del = phead->prev;del->prev->next = del->next;del->next->prev = del->prev;free(del);del = NULL;}//尾刪void LTPopFront(LTNode* phead)
{assert(phead && phead->next);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//頭刪void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定節點后插入數據void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定刪除節點void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//打印void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}}//銷毀鏈表

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test01()
{LTNode* plist = NULL;LTInit(&plist);printf("尾插\n");LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);printf("頭插\n");LTPushFront(plist, 0);LTPrint(plist);/*printf("尾刪\n");LTPopBack(plist);LTPopBack(plist);LTPrint(plist);*/printf("頭刪\n");LTPopFront(plist);LTPopFront(plist);LTPrint(plist);printf("在3后面插入數據:\n");LTNode* Find = LTFind(plist, 3);/*if (Find == NULL){printf("找不到！\n");}else{printf("找到了\n");}*/LTInsertAfter(plist, Find, 56);LTPrint(plist);printf("刪除指定節點3：\n");LTErase(plist, Find);LTPrint(plist);printf("銷毀鏈表\n");LTDestroy(plist);plist = NULL;}int main()
{test01();return 0;
}