前言

各位小伙伴大家好，即上回的單向鏈表之后，雙向鏈表來了，他和單向鏈表的主要區別就是，他有兩個指針，同時指向前面一個節點，和后面一個節點，簡直是完美，幾乎解決的單向鏈表的大多數難題

1、初步認識雙向鏈表

1.1 定義：

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向前面一個節點和后面一個節點。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。

1.2 結構

這是帶頭的雙向循環鏈表。

1.3 節點的存儲

typedef int DLDataType;typedef struct LinkNode
{DLDataType data;struct LinkNode* next;struct LinkNode* prv;
}LNode;

2、雙向鏈表的接口函數

2.1 鏈表的節點的動態申請

LTNode* LTFound(DLDataType x)
{LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL){perror("LTInit()::malloc()");return;}newNode->next = newNode->prv = newNode;newNode->data = x;return newNode;
}

2.2 鏈表的初始化

// 法一：
LTNode* LTInit()
{LTNode* newhead = LTFound(-1);return newhead;
}
法二：
void LTInit(LTNode** pphead)
{LTNode* newhead = LTFound(-1);*phead = newhead;
}

2.3 尾插

void LTPushBack(LTNode* phead, DLDataType x)
{assert(phead);LTNode* cmp = LTFound(x);// phead phead->prv cmpcmp->next = phead;cmp->prv = phead->prv;phead->prv->next = cmp;phead->prv = cmp;
}

尾插這個節點不管是插入在頭節點的前面還是尾節點后面都是一樣的

2.4 頭插

//頭插
void LTPushFront(LTNode* phead, DLDataType x)
{assert(phead);LTNode* tmp = LTFound(x);// phead tmp phead->nexttmp->next = phead->next;tmp->prv = phead;phead->next = tmp;phead->next->prv = tmp;
}

頭插必須插入在頭節點的后面才是頭插，頭節點就是哨兵衛，鏈表進行操作的時候不能操作哨兵衛，否則就不帶頭了。

2.5 頭刪

//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* cur = phead->next;// phead  cur cur->nextphead->next = cur->next;cur->next = phead;free(cur);cur = NULL;
}

2.5 尾刪

//尾刪
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* cur = phead->prv;// phead cur->prv curphead->prv = cur->prv;cur->prv->next = phead;free(cur);cur = NULL;
}

2.6 在pos節點后面添加數據

//在pos位置之后插入數據
void LTInsert(LTNode* pos, DLDataType x)
{assert(pos);LTNode* cur = LTCreate(x);// pos cur pos->nextcur->next = pos->next;cur->prv = pos;pos->next = cur;pos->next->prv = cur;}

2.6 刪除pos節點

//刪除pos節點
void LTErase(LTNode* pos)
{assert(pos);// pos->prv pos pos->nextpos->prv->next = pos->next;pos->next->prv = pos->prv;free(pos);pos = NULL;
}

3、雙向鏈表的實現：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>typedef int DLDataType;typedef struct LinkNode
{DLDataType data;struct LinkNode* next;struct LinkNode* prv;
}LTNode;//雙鏈表的節點創建
LTNode* LTCreate(DLDataType x)
{LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL){perror("LTInit()::malloc()");exit(-1);}newNode->next = newNode;newNode->prv = newNode;newNode->data = x;return newNode;
}//初始化
//void LTInit(LTNode** pphead)
//{
//	LTNode* newhead = LTFound(-1);
//}LTNode* LTInit()
{LTNode* newhead = LTCreate(-1);return newhead;
}//銷毀鏈表
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}//鏈表的打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//查找pos節點
LTNode* LTFind(LTNode* phead, DLDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//插入數據之前，鏈表必須初始化到只有一個頭結點的情況
//不改變哨兵位的地址，因此傳一級即可
//尾插
void LTPushBack(LTNode* phead, DLDataType x)
{assert(phead);LTNode* cmp = LTCreate(x);// phead phead->prv cmpcmp->next = phead;cmp->prv = phead->prv;phead->prv->next = cmp;phead->prv = cmp;
}//頭插
void LTPushFront(LTNode* phead, DLDataType x)
{assert(phead);LTNode* tmp = LTCreate(x);// phead tmp phead->nexttmp->next = phead->next;tmp->prv = phead;phead->next = tmp;phead->next->prv = tmp;
}//尾刪
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* cur = phead->prv;// phead cur->prv curphead->prv = cur->prv;cur->prv->next = phead;free(cur);cur = NULL;
}//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* cur = phead->next;// phead  cur cur->nextphead->next = cur->next;cur->next = phead;free(cur);cur = NULL;
}//在pos位置之后插入數據
void LTInsert(LTNode* pos, DLDataType x)
{assert(pos);LTNode* cur = LTCreate(x);// pos cur pos->nextcur->next = pos->next;cur->prv = pos;pos->next = cur;pos->next->prv = cur;}//刪除pos節點
void LTErase(LTNode* pos)
{assert(pos);// pos->prv pos pos->nextpos->prv->next = pos->next;pos->next->prv = pos->prv;free(pos);pos = NULL;
}void DLinkListText()
{LTNode* phead = LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPrint(phead);LTPushFront(phead, 0);LTPushFront(phead, 999);LTPrint(phead);// LTPopFront(phead);// LTPrint(phead);LTPopBack(phead);LTPrint(phead);LTDesTroy(phead);
}int main()
{DLinkListText();return 0;
}