前言?

? ? ? ? 帶頭雙向循環(huán)鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，它的結(jié)構(gòu)是很完美的，它彌補了單鏈表的許多不足，讓我們一起來了解一下它是如何實現(xiàn)的吧！

1.節(jié)點的結(jié)構(gòu)

? ? ? ? 它的節(jié)點中存儲著數(shù)據(jù)和兩個指針，一個指針_prev用來記錄前一個節(jié)點的地址，另一個指針_next 用來記錄后一個節(jié)點的地址。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;

2.尾部的插入和刪除的實現(xiàn)

? ? ? ? 由于這是帶頭循環(huán)的雙向鏈表，所以尾插只需要在它的頭結(jié)點的_prev?處進(jìn)行插入，然后重新鏈接就可以了。如圖：?

? ? ? ? 如果只有一個頭結(jié)點，插入也是一樣的。

void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode = BuyListNode(data);//申請新節(jié)點ListNode* tail = phead->_prev;//找尾結(jié)點//鏈接新節(jié)點和尾結(jié)點tail->_next = newNode;newNode->_prev = tail;//與頭結(jié)點進(jìn)行鏈接phead->_prev = newNode;newNode->_next = phead;
}

? ? ? ? ?尾部的刪除，首先需要找到鏈表的尾和尾的前一個節(jié)點，刪除尾結(jié)點之后，將前一個節(jié)點進(jìn)與頭結(jié)點進(jìn)行鏈接，如圖：

void ListPopBack(ListNode* phead)//尾刪除
{//確保指針不為空assert(phead);assert(phead->_next != phead);//保留頭結(jié)點//找尾ListNode* tail = phead->_prev;ListNode* newTail = tail->_prev;//找到新的尾結(jié)點//刪除舊的尾結(jié)點free(tail);//重新鏈接頭尾節(jié)點newTail->_next = phead;phead->_prev = newTail;
}

3.頭部插入和刪除的實現(xiàn)

? ? ? ? 頭部的插入，刪除和尾部的插入，刪除類似，需要注意的是刪除的不是?頭結(jié)點，是存儲有效數(shù)據(jù)的第一個節(jié)點，插入數(shù)據(jù)也是在第一個有效數(shù)據(jù)節(jié)點和頭結(jié)點之間插入。如圖：

?

void ListPushFront(ListNode* phead, LTDataType data)//頭插
{//確保指針不為空assert(phead);//申請新的節(jié)點ListNode* newNode = BuyListNode(data);//進(jìn)行鏈接ListNode* realHead = phead->_next;realHead->_prev = newNode;newNode->_next = realHead;phead->_next = newNode;newNode->_prev = phead;
}
void ListPopFront(ListNode* phead)//頭刪插
{//指針存在assert(phead);//并且確保不能刪除頭結(jié)點assert(phead->_next != phead);//找到真正的頭ListNode* realHead = phead->_next;ListNode* realHeadNext = realHead->_next;//刪除頭節(jié)點free(realHead);//重新鏈接phead->_next = realHeadNext;realHeadNext->_prev = phead;
}

4.任意位置的插入和刪除?

? ? ? ? 在任意位置進(jìn)行插入和刪除，需要知道節(jié)點的指針，插入或者刪除節(jié)點之后需要?更新節(jié)點的鏈接關(guān)系。如圖：

?

void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//確保指針有效ListNode* newNode = BuyListNode(data);//申請節(jié)點//進(jìn)行鏈接ListNode* prev = pos->_prev;ListNode* next = pos;prev->_next = newNode;newNode->_prev = prev;newNode->_next = next;next->_prev = newNode;
}
void ListErase(ListNode* pos)//pos位置的刪除
{//確保指針有效assert(pos);ListNode* next = pos->_next;ListNode* prev = pos->_prev;//刪除pos所指向的節(jié)點free(pos);//進(jìn)行重新鏈接prev->_next = next;next->_prev = prev;
}

? ? ? ? ?對任意位置的插入和刪除進(jìn)行測試時，可以通過復(fù)用接口來實現(xiàn)，頭插尾插，頭刪尾刪都可以調(diào)用這兩個接口來實現(xiàn)，如下：

void ListPushBack(ListNode* phead, LTDataType data)//尾插
{ListInsert(phead, data);
}
void ListPopBack(ListNode* phead)//尾刪除
{ListErase(phead->_prev);
}
void ListPushFront(ListNode* phead, LTDataType data)//頭插
{ListInsert(phead->_next,data);
}
void ListPopFront(ListNode* phead)//頭刪插
{ListErase(phead->_next);
}

5.鏈表的初始化和刪除

? ? ? ? 帶頭的雙向循環(huán)鏈表初始化的時候就需要申請內(nèi)存給頭節(jié)點。?

ListNode* BuyListNode(LTDataType data)//申請節(jié)點
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL){printf("申請空間失敗\n");exit(-1);}newNode->_data = data;return newNode;
}
void ListInit(ListNode** pphead)//初始化鏈表
{*pphead = BuyListNode(0);//申請頭結(jié)點//并且初始化(*pphead)->_next = *pphead;(*pphead)->_prev = *pphead;
}
//清理鏈表
void ListClear(ListNode* phead)
{assert(phead);//確保鏈表不為空assert(phead->_next != phead);//除了確保不清理頭結(jié)點ListNode* cur = phead->_next;while (cur != phead){ListNode* clearNode = cur;cur = cur->_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毀鏈表
{assert(*ppHead);//確保指針不為空ListClear(*ppHead);free(*ppHead);//釋放頭結(jié)點
}

6.查找并修改鏈表的節(jié)點的數(shù)據(jù)

? ? ? ? 查找和修改是一起的，實現(xiàn)查找就可以實現(xiàn)?修改鏈表的值。

ListNode* ListFind(ListNode* phead, LTDataType data)//查找鏈表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){if (cur->_data == data)return cur;cur = cur->_next;}return NULL;//找不到返回NULL
}

void ListTest4()
{//查找和修改的測試ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListNode* node = ListFind(pHead, 3);//在鏈表中查找if (node){//修改鏈表的值node->_data = 90;}ListPrint(pHead);ListDestory(&pHead);
}

7.全部代碼

//List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;void ListPushBack(ListNode* phead, LTDataType data);//尾插void ListPopBack(ListNode* phead);//尾刪除
void ListPushFront(ListNode* phead,LTDataType data);//頭插
void ListPopFront(ListNode* phead);//頭刪插
ListNode* BuyListNode(LTDataType data);//申請節(jié)點
void ListInit(ListNode** pphead);//初始化鏈表void ListInsert(ListNode* pos, LTDataType data);//pos位置之前的插入void ListErase(ListNode* pos);//pos位置的刪除
//清理鏈表
void ListClear(ListNode* phead);void ListDestory(ListNode** ppHead);//摧毀鏈表void ListPrint(ListNode* phead);//打印鏈表
ListNode* ListFind(ListNode* phead, LTDataType data);//查找鏈表

?//List.c

#include"List.h"
void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode = BuyListNode(data);//申請新節(jié)點ListNode* tail = phead->_prev;//找尾結(jié)點//鏈接新節(jié)點和尾結(jié)點tail->_next = newNode;newNode->_prev = tail;//與頭結(jié)點進(jìn)行鏈接phead->_prev = newNode;newNode->_next = phead;
}
void ListPopBack(ListNode* phead)//尾刪除
{//確保指針不為空assert(phead);assert(phead->_next != phead);//保留頭結(jié)點//找尾ListNode* tail = phead->_prev;ListNode* newTail = tail->_prev;//找到新的尾結(jié)點//刪除舊的尾結(jié)點free(tail);//重新鏈接頭尾節(jié)點newTail->_next = phead;phead->_prev = newTail;
}
void ListPushFront(ListNode* phead, LTDataType data)//頭插
{//確保指針不為空assert(phead);//申請新的節(jié)點ListNode* newNode = BuyListNode(data);//進(jìn)行鏈接ListNode* realHead = phead->_next;realHead->_prev = newNode;newNode->_next = realHead;phead->_next = newNode;newNode->_prev = phead;
}
void ListPopFront(ListNode* phead)//頭刪插
{//指針存在assert(phead);//并且確保不能刪除頭結(jié)點assert(phead->_next != phead);//找到真正的頭ListNode* realHead = phead->_next;ListNode* realHeadNext = realHead->_next;//刪除頭節(jié)點free(realHead);//重新鏈接phead->_next = realHeadNext;realHeadNext->_prev = phead;
}
ListNode* BuyListNode(LTDataType data)//申請節(jié)點
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL){printf("申請空間失敗\n");exit(-1);}newNode->_data = data;return newNode;
}
void ListInit(ListNode** pphead)//初始化鏈表
{*pphead = BuyListNode(0);//申請頭結(jié)點//并且初始化(*pphead)->_next = *pphead;(*pphead)->_prev = *pphead;
}
void ListPrint(ListNode* phead)//打印鏈表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){printf("%d ", cur->_data);cur = cur->_next;}printf("\n");
}
void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//確保指針有效ListNode* newNode = BuyListNode(data);//申請節(jié)點//進(jìn)行鏈接ListNode* prev = pos->_prev;ListNode* next = pos;prev->_next = newNode;newNode->_prev = prev;newNode->_next = next;next->_prev = newNode;
}
void ListErase(ListNode* pos)//pos位置的刪除
{//確保指針有效assert(pos);ListNode* next = pos->_next;ListNode* prev = pos->_prev;//刪除pos所指向的節(jié)點free(pos);//進(jìn)行重新鏈接prev->_next = next;next->_prev = prev;
}
//清理鏈表
void ListClear(ListNode* phead)
{assert(phead);//確保鏈表不為空assert(phead->_next != phead);//除了確保不清理頭結(jié)點ListNode* cur = phead->_next;while (cur != phead){ListNode* clearNode = cur;cur = cur->_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毀鏈表
{assert(*ppHead);//確保指針不為空ListClear(*ppHead);free(*ppHead);//釋放頭結(jié)點
}
ListNode* ListFind(ListNode* phead, LTDataType data)//查找鏈表
{assert(phead);ListNode* cur = phead->_next;while (cur != phead){if (cur->_data == data)return cur;cur = cur->_next;}return NULL;//找不到返回NULL
}

//test.c

#include"List.h"
void ListTest1()
{//尾插尾刪的測試代碼ListNode* pHead = NULL;ListInit(&pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//頭插頭刪的測試ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的測試ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(&pHead);
}
int main()
{ListTest3();return 0;
}

?

8.測試代碼

void ListTest1()
{//尾插尾刪的測試代碼ListNode* pHead = NULL;ListInit(&pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//頭插頭刪的測試ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的測試ListNode* pHead = NULL;ListInit(&pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(&pHead);
}

?