特點：

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

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

LIST.h

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

LIST.c

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