特點(diǎn)：

• 結(jié)構(gòu)：指向前一結(jié)點(diǎn)指針+數(shù)據(jù)+指向后一結(jié)點(diǎn)指針
• 由于循環(huán)，尾結(jié)點(diǎn)的下一結(jié)點(diǎn)next指向頭結(jié)點(diǎn)（哨兵結(jié)點(diǎn)）
• 空的雙向鏈表只有自循環(huán)的哨兵結(jié)點(diǎn)（頭結(jié)點(diǎn)）?

模擬實(shí)現(xiàn)雙向鏈表

LIST.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//定義雙向鏈表結(jié)構(gòu)
typedef int LTDataType;//鏈表數(shù)據(jù)類型
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化
void LTInit(LTNode** pphead);
LTNode* LTInit2();//銷毀    鏈表的銷毀是整個(gè)都銷毀的
void LTDesTory(LTNode** pphead);
void LTDesTory2(LTNode* phead);//傳一級我們需要手動(dòng)將plist置為NULL//打印鏈表
void LTPrint(LTNode* phead);//尾插數(shù)據(jù)
//第一個(gè)參數(shù)傳一級還是二級，，要看pphead指向的節(jié)點(diǎn)會(huì)不會(huì)發(fā)生改變
//如果發(fā)生改變，那么pphead的改變要影響實(shí)參，傳二級
//如果不發(fā)生改變，pphead不會(huì)影響實(shí)參，傳一級
//我們通過傳遞的一級指針來找到頭結(jié)點(diǎn)，就可以找到之后的節(jié)點(diǎn)了//那么我們在插入新節(jié)點(diǎn)的時(shí)候，受到影響的節(jié)點(diǎn)有之前的尾節(jié)點(diǎn)和哨兵位以及新節(jié)點(diǎn)
void LTPushBack(LTNode* phead, LTDataType x);//頭插數(shù)據(jù)
void LTPushFront(LTNode* phead, LTDataType x);//尾刪數(shù)據(jù)
void LTPopBack(LTNode* phead);//頭刪數(shù)據(jù)
void LTPopFront(LTNode* phead);//判斷鏈表是否為空
bool LTEmpty(LTNode* phead);//查找數(shù)據(jù)
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入節(jié)點(diǎn)
void LTInsert(LTNode* pos, LTDataType x);//刪除指定位置的節(jié)點(diǎn)
void LTIErase(LTNode* pos);

LIST.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"LIST.h"//創(chuàng)建結(jié)點(diǎn)
LTNode* buyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode*));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;//初步實(shí)現(xiàn)雙頭自循環(huán)的空鏈表return newnode;
}
//初始化1 傳參初始化
void LTInit(LTNode** pphead) {//創(chuàng)建一個(gè)哨兵結(jié)點(diǎn)（頭結(jié)點(diǎn)）*pphead = buyNode(-1);
}
//初始化2 返回值初始化
LTNode* LTInit2() {LTNode* phead = buyNode(-1);return phead;
}//銷毀    鏈表的銷毀是整個(gè)都銷毀的
void LTDesTory(LTNode** pphead) {//哨兵位不能先銷毀！assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;//從哨兵位的下一結(jié)點(diǎn)開始遍歷銷毀while (pcur != (*pphead)) {LTNode* Next = pcur->next;//創(chuàng)建pcur下一結(jié)點(diǎn)，方便遍歷銷毀free(pcur);pcur = Next;}//跳出循環(huán)，說明哨兵位之后的全銷毀了//現(xiàn)在釋放銷毀哨兵位free(*pphead);*pphead = pcur = NULL;
}//初次錯(cuò)誤示范！！
void LTDesToryError(LTNode** pphead) {LTNode* pcur = (*pphead)->next;LTNode* Next = pcur->next;while (pcur!=*pphead) {free(pcur);pcur = Next;Next = Next->next;}pcur = Next = NULL;
}//void LTDesTory2(LTNode* phead);//傳一級我們需要手動(dòng)將plist置為NULL//打印鏈表
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;//記住第一個(gè)結(jié)點(diǎn)！！是哨兵位下一個(gè)結(jié)點(diǎn)！while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾插數(shù)據(jù)
//第一個(gè)參數(shù)傳一級還是二級，，要看pphead指向的節(jié)點(diǎn)會(huì)不會(huì)發(fā)生改變
//如果發(fā)生改變，那么pphead的改變要影響實(shí)參，傳二級
//如果不發(fā)生改變，pphead不會(huì)影響實(shí)參，傳一級
//我們通過傳遞的一級指針來找到頭結(jié)點(diǎn)，就可以找到之后的節(jié)點(diǎn)了//那么我們在插入新節(jié)點(diǎn)的時(shí)候，受到影響的節(jié)點(diǎn)有之前的尾節(jié)點(diǎn)和哨兵位以及新節(jié)點(diǎn)
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//哨兵位 phead 新結(jié)點(diǎn) newnode 尾結(jié)點(diǎn)pcur(phead->prev)LTNode* pcur = phead->prev;LTNode* newnode = buyNode(x);//newnode的指針修改，prev指向上個(gè)尾節(jié)點(diǎn)，next指向哨兵位newnode->prev = pcur;newnode->next = phead;//原先的尾節(jié)點(diǎn)next指針->哨兵位，現(xiàn)在next->newnode//哨兵位的prev原本->尾節(jié)點(diǎn),現(xiàn)在讓prev->newnodepcur->next = newnode;phead->prev = newnode;
}//頭插數(shù)據(jù)
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//哨兵位phead 新結(jié)點(diǎn)newnode 第一個(gè)結(jié)點(diǎn) pcur(phead->next)LTNode* newnode = buyNode(x);LTNode* pcur = phead->next;//插入newnode，prev指向哨兵位，next指向pcurnewnode->prev = phead;newnode->next = pcur;//哨兵位的next，原頭結(jié)點(diǎn)的prev，分別指向newnodephead->next = newnode;pcur->prev = newnode;
}
//————————ERROR！！注意！！！刪除要檢查鏈表是否為空！！——————————
//判斷鏈表是否為空
bool LTEmpty(LTNode* phead) {assert(phead);//error!!! return phead == NULL;不是判斷哨兵位phead！！第一個(gè)結(jié)點(diǎn)是哨兵位下一結(jié)點(diǎn)！phead->next!return phead->next == phead;//如果哨兵位next指向自己，說明是自循環(huán)的只有哨兵位的空鏈表！
}//鏈表為空，返回true
//尾刪數(shù)據(jù)
void LTPopBack(LTNode* phead) {assert(phead);//哨兵位不得為空assert(!LTEmpty(phead));//鏈表不得為空//哨兵位phead 尾結(jié)點(diǎn) del(phead->prev) 尾結(jié)點(diǎn)前一結(jié)點(diǎn) del->prevLTNode* del = phead->next;//刪除尾結(jié)點(diǎn) 哨兵位的prev指向del->prev, 尾結(jié)點(diǎn)的前一結(jié)點(diǎn)的next->哨兵位del->prev->next = phead;//注意這倆行代碼不可調(diào)換！phead->prev = del->prev;//先改了頭結(jié)點(diǎn)的指向 del也會(huì)跟著改！//刪除完之后釋放delfree(del);del = NULL;
}//頭刪數(shù)據(jù)
void LTPopFront(LTNode* phead) {assert(phead);assert(!LTEmpty(phead));//哨兵位phead 要?jiǎng)h除的第一個(gè)結(jié)點(diǎn)del(phead->next) 新的第一結(jié)點(diǎn)del->nextLTNode* del = phead->next;//刪除結(jié)點(diǎn) 哨兵位的next指向新第一結(jié)點(diǎn) 新的第一結(jié)點(diǎn)的prev指向哨兵位del->next->prev = phead;phead->next = del->next;//釋放delfree(del);del = NULL;
}//查找數(shù)據(jù)
//遍歷鏈表，直至再次遇到哨兵位（找一圈了沒找到就是沒有）
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur = phead->next;//記住從第一個(gè)結(jié)點(diǎn)！不是phead！while (pcur != phead) {//找到了if (pcur->data == x) {return pcur;}pcur = pcur->next;}//遍歷循環(huán)找了一圈，沒找到return NULL;
}
//在pos位置之后插入節(jié)點(diǎn)
void LTInsert(LTNode* pos, LTDataType x) {//創(chuàng)建一個(gè)新結(jié)點(diǎn)LTNode* newnode = buyNode(x);//pos newnode pos->next//先安newnodenewnode->next = pos->next;newnode->prev = pos;//先連接pos后面的，再連pospos->next->prev = newnode;pos->next = newnode;
}//刪除指定位置的節(jié)點(diǎn)
void LTIErase(LTNode* pos) {assert(pos);//傳過來的位置不為空/*pos前面的節(jié)點(diǎn)pos->prevpos后面的節(jié)點(diǎn)pos->next刪除pos影響這兩個(gè)節(jié)點(diǎn)pos前面指針的節(jié)點(diǎn)的next指針->Pos后面的節(jié)點(diǎn)pos后面的節(jié)點(diǎn)的prev指針就->pos前面的節(jié)點(diǎn)*///pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}