前言?

? ? ? ? 帶頭雙向循環鏈表是一種重要的數據結構，它的結構是很完美的，它彌補了單鏈表的許多不足，讓我們一起來了解一下它是如何實現的吧！

1.節點的結構

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

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

2.尾部的插入和刪除的實現

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

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

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

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

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

3.頭部插入和刪除的實現

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

?

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

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

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

?

void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//確保指針有效ListNode* newNode = BuyListNode(data);//申請節點//進行鏈接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所指向的節點free(pos);//進行重新鏈接prev->_next = next;next->_prev = prev;
}

? ? ? ? ?對任意位置的插入和刪除進行測試時，可以通過復用接口來實現，頭插尾插，頭刪尾刪都可以調用這兩個接口來實現，如下：

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.鏈表的初始化和刪除

? ? ? ? 帶頭的雙向循環鏈表初始化的時候就需要申請內存給頭節點。?

ListNode* BuyListNode(LTDataType data)//申請節點
{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);//申請頭結點//并且初始化(*pphead)->_next = *pphead;(*pphead)->_prev = *pphead;
}
//清理鏈表
void ListClear(ListNode* phead)
{assert(phead);//確保鏈表不為空assert(phead->_next != phead);//除了確保不清理頭結點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);//釋放頭結點
}

6.查找并修改鏈表的節點的數據

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

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);//申請節點
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);//申請新節點ListNode* tail = phead->_prev;//找尾結點//鏈接新節點和尾結點tail->_next = newNode;newNode->_prev = tail;//與頭結點進行鏈接phead->_prev = newNode;newNode->_next = phead;
}
void ListPopBack(ListNode* phead)//尾刪除
{//確保指針不為空assert(phead);assert(phead->_next != phead);//保留頭結點//找尾ListNode* tail = phead->_prev;ListNode* newTail = tail->_prev;//找到新的尾結點//刪除舊的尾結點free(tail);//重新鏈接頭尾節點newTail->_next = phead;phead->_prev = newTail;
}
void ListPushFront(ListNode* phead, LTDataType data)//頭插
{//確保指針不為空assert(phead);//申請新的節點ListNode* newNode = BuyListNode(data);//進行鏈接ListNode* realHead = phead->_next;realHead->_prev = newNode;newNode->_next = realHead;phead->_next = newNode;newNode->_prev = phead;
}
void ListPopFront(ListNode* phead)//頭刪插
{//指針存在assert(phead);//并且確保不能刪除頭結點assert(phead->_next != phead);//找到真正的頭ListNode* realHead = phead->_next;ListNode* realHeadNext = realHead->_next;//刪除頭節點free(realHead);//重新鏈接phead->_next = realHeadNext;realHeadNext->_prev = phead;
}
ListNode* BuyListNode(LTDataType data)//申請節點
{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);//申請頭結點//并且初始化(*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);//申請節點//進行鏈接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所指向的節點free(pos);//進行重新鏈接prev->_next = next;next->_prev = prev;
}
//清理鏈表
void ListClear(ListNode* phead)
{assert(phead);//確保鏈表不為空assert(phead->_next != phead);//除了確保不清理頭結點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);//釋放頭結點
}
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);
}

?