---

1 雙向鏈表的結構

帶頭鏈表的頭結點,實際是"哨兵位",哨兵位節點不存儲任何有效元素,只是站在這里"放哨的".
哨兵位的意義:遍歷循環鏈表避免死循環.

2 雙向鏈表的實現

筆者在刪除,插入數據時,畫好圖后,也好了代碼,但是在調試中多次出現代碼位置出錯,導致寫的代碼的含義不符合預期.
所以說思路一定要清晰,多多檢查調試

2.1 定義雙向鏈表的數據結構

typedef int ListDataType;typedef struct ListNode
{ListDataType data;		//整型數據struct ListNode* next;	//前驅指針struct ListNode* pre;	//后驅指針}ListNode;

2.2 打印鏈表

鏈表的第一個數據是phead->next,哨兵位不存儲數據
循環鏈表中,遍歷一遍,碰到phead為止

void ListPrint(ListNode* phead)
{ListNode* cur = phead->next;	//頭結點,哨兵位的下一位while (cur != phead)//雙向循環鏈表,循環到哨兵位為止{printf("%d-> ", cur->data);cur = cur->next;}
}

2.3 初始化鏈表

定義一個雙向循環鏈表后,初始化鏈表,此時只有一個phead(哨兵位),前驅指針和后驅指針都指向phead自己
哨兵位的數據(data)在應用中不使用,就設置成-1了,與筆者之后使用的正整數形成差異

ListNode* ListInit()
{ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL){perror("malloc error");return;}phead->data = -1;phead->next = phead->pre = phead;return phead;
}

調試中發現,phead,phead->next,phead->pre地址相同,data都是筆者設置的-1.

2.4 銷毀鏈表

遍歷一遍鏈表進行銷毀,cur碰到phead哨兵位為止
釋放cur前,記錄下cur->next,釋放cur后,把cur->next賦值給cur,以此避免銷毀cur后,cur->next不能指向下一個節點的情況
最后再把哨兵位釋放,置空.

void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;	//頭結點,哨兵位的下一位while (cur!=phead){//釋放cur前,記錄下cur->next,釋放cur后,把cur->next賦值給curListNode* NEXT = cur->next;free(cur);cur = NEXT;}//釋放哨兵位free(phead);phead = NULL;
}

2.5 尾插,頭插

先寫一個創建內存空間的函數,創建node后,畫圖示意頭插和尾插
一定注意編寫代碼的順序,看看筆者注釋所說的

//插入數據前創建內存空間
ListNode* ListBuyNode(ListDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->data = x;node->next = node->pre = NULL;return node;
}void ListPushBack(ListNode* phead, ListDataType x)
{assert(phead);ListNode* node = ListBuyNode(x);//先處理新節點前驅指針和后驅指針node->pre = phead->pre;node->next = phead;//再處理原鏈表最后一個節點和pheadphead->pre->next = node;phead->pre = node;
}void ListPushFront(ListNode* phead, ListDataType x)
{assert(phead);ListNode* node = ListBuyNode(x);//先處理新節點前驅指針和后驅指針node->pre = phead;node->next = phead->next;//再處理phead和原鏈表第一個節點(phead->next)phead->next->pre = node;phead->next = node;}

初始化成功,我們插入一個數據"1",成功插入

2.6 尾刪,頭刪

刪除鏈表至少有除哨兵位的一個數據,換句話說,鏈表不能只有一個哨兵位

void ListPopBack(ListNode* phead)
{assert(phead);//鏈表不能只有一個哨兵位assert(phead->next != phead);ListNode* del = phead->pre;//刪除節點的前驅指針del->pre->next = phead;//phead的前驅指針phead->pre = del->pre;
}void ListPopFront(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->pre = phead;phead->next = del->next;free(del);del = NULL;}

2.7 根據頭次出現數據找下標

這個Find()函數在筆者的多篇博客都有提到缺點,但是我們主要實現功能,筆者在力扣題寫過找多個相同元素,刪多個相同元素的題

ListNode* ListFind(ListNode* phead, ListDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.8 定點前插入

void ListInsert(ListNode* pos, ListDataType x)
{assert(pos);ListNode* node= ListBuyNode(x);//先處理nodenode->next = pos;node->pre = pos->pre;//在處理pos->pre和pospos->pre->next= node;node->next->pre = node;}

2.9 刪除pos位置

void ListErase(ListNode* pos)
{assert(pos);pos->next->pre = pos->pre;pos->pre->next = pos->next;free(pos);pos = NULL;
}

2.10 定點后插入

void ListInsertAfter(ListNode* pos, ListDataType x)
{assert(pos);ListNode* node = ListBuyNode(x);//node的prev 和 nextnode->next = pos->next;node->pre = pos;//pos的next 和 pos->next的prevpos->next = node;node->next->pre = node;
}

3 完整代碼

3.1 List.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdbool.h>
#include<stddef.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//0 定義雙向循環鏈表節點結構
typedef int ListDataType;typedef struct ListNode
{ListDataType data;struct ListNode* next;	//前驅指針struct ListNode* pre;	//后驅指針}ListNode;//0 打印鏈表
void ListPrint(ListNode* phead);//1 初始化鏈表
ListNode* ListInit();//2 銷毀鏈表
void ListDestory(ListNode* phead);//3 尾插,頭插
void ListPushBack(ListNode* phead, ListDataType x);
void ListPushFront(ListNode* phead, ListDataType x);//4 尾刪,頭刪
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);//5 根據數找到第一次出現的下標
ListNode* ListFind(ListNode* phead, ListDataType x);//6 定點前插入
void ListInsert(ListNode* pos, ListDataType x);//7 刪除pos位置
void ListErase(ListNode* pos);//8 定點后插入
void ListInsertAfter(ListNode* pos, ListDataType x);

3.2 Lish.c

#include "List.h"void ListPrint(ListNode* phead)
{ListNode* cur = phead->next;while (cur != phead)//雙向循環鏈表,循環到哨兵位為止{printf("%d-> ", cur->data);cur = cur->next;}
}ListNode* ListInit()
{ListNode* phead = (ListNode*)malloc(sizeof(ListNode));if (phead == NULL){perror("malloc error");return;}phead->data = -1;phead->next = phead->pre = phead;return phead;
}void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;	//頭結點,哨兵位的下一位while (cur!=phead){//釋放cur前提前記錄下cur->next,釋放cur后,把cur->next賦值給curListNode* NEXT = cur->next;free(cur);cur = NEXT;}//釋放哨兵位free(phead);phead = NULL;
}//插入數據前創建內存空間
ListNode* ListBuyNode(ListDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->data = x;node->next = node->pre = NULL;return node;
}void ListPushBack(ListNode* phead, ListDataType x)
{assert(phead);ListNode* node = ListBuyNode(x);//先處理新節點前驅指針和后驅指針node->pre = phead->pre;node->next = phead;//再處理原鏈表最后一個節點和pheadphead->pre->next = node;phead->pre = node;
}void ListPushFront(ListNode* phead, ListDataType x)
{assert(phead);ListNode* node = ListBuyNode(x);//先處理新節點前驅指針和后驅指針node->pre = phead;node->next = phead->next;//再處理phead和原鏈表第一個節點(phead->next)phead->next->pre = node;phead->next = node;}void ListPopBack(ListNode* phead)
{assert(phead);//鏈表不能只有一個哨兵位assert(phead->next != phead);ListNode* del = phead->pre;//刪除節點的前驅指針del->pre->next = phead;//phead的前驅指針phead->pre = del->pre;
}void ListPopFront(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->pre = phead;phead->next = del->next;free(del);del = NULL;}ListNode* ListFind(ListNode* phead, ListDataType 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, ListDataType x)
{assert(pos);ListNode* node= ListBuyNode(x);//先處理nodenode->next = pos;node->pre = pos->pre;//在處理pos->pre和pospos->pre->next= node;node->next->pre = node;}void ListErase(ListNode* pos)
{assert(pos);pos->next->pre = pos->pre;pos->pre->next = pos->next;free(pos);pos = NULL;
}void ListInsertAfter(ListNode* pos, ListDataType x)
{assert(pos);ListNode* node = ListBuyNode(x);//node的prev 和 nextnode->next = pos->next;node->pre = pos;//pos的next 和 pos->next的prevpos->next = node;node->next->pre = node;
}

3.3 test.c

#include"List.h"void test1()
{ListNode* plist = ListInit();
}void test2()
{ListNode* plist = ListInit();;ListPushBack(plist, 1);ListPushBack(plist, 4);ListPushBack(plist, 7);ListPrint(plist);  //1->4->7->ListDestory(plist);
}void test3()
{ListNode* plist = ListInit();;ListPushFront(plist, 1);ListPushFront(plist, 4);ListPushFront(plist, 7);ListPrint(plist);//7->4->1->ListDestory(plist);
}void test4()
{ListNode* plist = ListInit();;ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPushBack(plist, 6);ListPushBack(plist, 7);ListPushBack(plist, 8);ListPushBack(plist, 9);ListPrint(plist);printf("\n");ListPopBack(plist);ListPopBack(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);ListDestory(plist);
}void test5()
{ListNode* plist = ListInit();;ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);printf("\n");//測試指定位置ListNode* Find1 = ListFind(plist, 2);ListNode* Find2 = ListFind(plist, 4);ListInsert(Find1, 10);ListInsertAfter(Find2, 20);ListPrint(plist);printf("\n");ListErase(Find1);ListPrint(plist);ListDestory(plist);
}int main()
{//test1();//test2();//test3();//test4();test5();return 0;
}

筆者在刪除,插入數據時,畫好圖后,也好了代碼,但是在調試中多次出現代碼位置出錯,導致寫的代碼的含義不符合預期.
所以說思路一定要清晰,多多檢查調試