雙向鏈表 -- 詳細理解和實現

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?歡迎光顧我的homepage??????????????????????????????????????????????????????????????

前言

????????雙向鏈表是一種帶頭雙向循環的鏈表。在雙向鏈表中，首先存在著一個頭結點；其次每個節點有指向下一個節點的指針next 和指向上一個節點的指針prev ；最后，雙向鏈表的頭結點中存放上一個節點的指針指向鏈表的尾節點，尾節點中存放下一個節點的指針指向鏈表的頭結點，形成一個閉環。這樣雙向鏈表既可以從前遍歷，也可以從后遍歷，直到回到起點。

一、鏈表的分類

? ? ? ? 鏈表的結構多種多樣，鏈表呢可以是帶頭（不帶頭）、雙向（單向）、循環（不循環）的，我們之前實現的單鏈表其實就是不帶頭，單向，不循環的鏈表。

而這些有什么區別呢？

????????帶頭和不帶頭

這里帶頭和不帶頭指的是有沒有頭結點，這單鏈表的實現過程中，是直接創建一個指針變量指向鏈表的第一個節點（這是沒有頭結點的情況），而存在頭結點呢，就是一個哨兵位，里面沒有存放數據，存放了指向第一個節點的指針。

? ? ? ? 可以看到，帶頭的鏈表多了一個節點（head），這個節點中沒有存放任何數據，這樣做可以方便對鏈表的節點進行統一操作。

? ? ? ? 單向和雙向

????單向是可以通過一個節點找到它的后一個節點，而雙向是可以通過一個節點找到它前后的節點。

? ? ? ? 循環和不循環

? ? 這實現單鏈表的時候，我們將鏈表的最后一個節點next指針置位了空指針（NULL），而循環的鏈表中，我們會將最后一個節點的next指針指向鏈表的頭結點，對于雙向鏈表，將頭節點的prev(上一個節點）指針指向鏈表的尾節點。

二、雙向鏈表的實現

這里實現的雙向鏈表，先來看一下雙向鏈表的節點結構

雙向鏈表節點

typedef int LTDataType;
//雙向鏈表
typedef struct ListNode
{struct ListNode* prev;  //指向上一個節點struct ListNode* next;  //指向下一個節點LTDataType data;
}LTNode;

雙向鏈表的功能預覽

//初始化并創建頭結點
void LTInit(LTNode** phead);
//LTNode* LTInit();
//輸出
void LTPrint(LTNode* phead);
//創建新的節點
LTNode* LTBuyNode(LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//頭刪
void LTPopFront(LTNode* phead);
//尾刪
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos節點之后插入數據
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos節點之前插入數據
void LTPush(LTNode* pos, LTDataType x);
//刪除pos節點
void LTPop(LTNode* pos);
//鏈表銷毀
void LTDesTroy(LTNode* phead);

2.1、創建新的節點

? ? ? ? 創建節點，和單鏈表一樣，都是動態開辟的空間。

//創建新的節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));if (ptail == NULL){perror("LTBuyNode--malloc filed!");exit(1);}ptail->data = x;ptail->prev = ptail->next = NULL;return ptail;
}

2.2、雙向鏈表初始化并創建頭結點

? ? ? ? 鏈表初始化，其實就是創建一個頭節點（也叫哨兵位）；因為這里是雙向鏈表，創建完頭節點之后，讓頭節點的prev和next指針都指向它自己。

//初始化并創建頭結點
void LTInit(LTNode** phead)
{*phead = LTBuyNode(-1);(*phead)->prev = (*phead)->next = *phead;
}

2.3、輸出鏈表

? ? ? ? 遍歷鏈表并輸出有效數據，這里雙向鏈表可以從前開始遍歷也可以從后開始遍歷。

//輸出
void LTPrint(LTNode* phead)
{LTNode* ptail = phead->next;//遍歷雙向鏈表 -- 從前開始遍歷while (ptail != phead){printf("%d -> ", ptail->data);ptail = ptail->next;}printf("\n");
}

2.4、雙向鏈表頭插數據

? ? ? ? 從鏈表的頭部插入數據，創建新的節點，然后將新的節點prev指針指向頭節點，將next指針指向頭節點的下一個節點；然后修改頭節點的next指針和頭節點下一個節點的prev指針即可。

//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//修改前后節點的指針指向phead->next->prev = newnode;phead->next = newnode;
}

2.5、雙向鏈表尾插數據

? ? ? ? 從鏈表尾部插入到尾節點的后面，創建新的節點，將新節點的prev指針指向頭節點的上一個節點，將next指針指向頭節點，然后修改尾節點的next指針和頭節點的prev指針即可。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;//修改前后節點指針指向phead->prev->next = newnode;phead->prev = newnode;
}

2.6、雙向鏈表頭刪數據

? ? ? ? 頭刪是刪除頭節點的后一個節點，因為是動態開辟的內存，需要內存釋放；刪除后，讓頭節點的next指針指向下一個數據的節點。

//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead != phead->next); //鏈表為空的話就不能進行刪除LTNode* del = phead->next;  phead->next->next->prev = phead;phead->next = phead->next->next;free(del);del = NULL;
}

2.7、雙向鏈表尾刪數據

? ? ? ? 尾插是刪除鏈表的尾節點，釋放內存之后，讓尾節點的上一個節點next指針指向頭節點，頭節點的prev指針指向刪除節點的上一個節點。

//尾刪
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead); //鏈表為空不能進行刪除LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.8、雙向鏈表查找數據

? ? ? ? 這里如果找到了，就返回該節點的指針，如果沒有就返回NULL；方便對其進行前后插入數據和刪除。

//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead) //遍歷鏈表{if (ptail->data == find) {return ptail;}ptail = ptail->next;}return NULL;
}

2.9、在指定節點pos之前插入數據

? ? ? ? 根據我們查找到的節點，在其之前插入數據，首先創建新節點，將新節點的prev指針指向pos的前一個節點，新節點的next指針指向pos；再修改pos的上一個節點的next指針指向和pos的prev指針指向即可；

//在pos節點之前插入數據
void LTPush(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;//修改pos前后節點指針的指向pos->prev->next = newnode;pos->prev = newnode;
}

? ? ? ? 這里就可以發現雙向鏈表的一個好處，不用像單向鏈表那樣遍歷鏈表來尋找pos的上一個節點。

2.10、在指定節點pos之后插入數據

? ? ? ? 根據查找到的節點，在其之后插入數據；首先創建節點，將新節點的prev指針指向pos，新節點的next指針指向pos的下一個節點；然后修改pos的next指針指向和pos下一個節點的prev指針指向即可。

//在pos節點之后插入數據
void LTPushAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;//修改pos前后節點指針的指向pos->next->prev = newnode;pos->next = newnode;
}

2.11、刪除指定節點pos

? ? ? ? 根據查找到的節點，然后將其刪除，這里需要修改pos前后節點的指針指向。

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

2.12、雙向鏈表的銷毀

? ? ? ? 及時對動態開辟的內存進行釋放，養成好習慣

? ? ? ? 現在，動態開辟的鏈表需要進行銷毀（也就是動態內存釋放），這里就需要遍歷鏈表了。

//鏈表銷毀
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead){LTNode* del = ptail->next;free(ptail);ptail = del;}free(ptail);ptail = NULL;
}

代碼總覽

List.h

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//雙向鏈表
typedef struct ListNode
{struct ListNode* prev;  //指向上一個節點struct ListNode* next;  //指向下一個節點LTDataType data;
}LTNode;//初始化并創建頭結點
void LTInit(LTNode** phead);
//LTNode* LTInit();
//輸出
void LTPrint(LTNode* phead);
//創建新的節點
LTNode* LTBuyNode(LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//頭刪
void LTPopFront(LTNode* phead);
//尾刪
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos節點之后插入數據
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos節點之前插入數據
void LTPush(LTNode* pos, LTDataType x);
//刪除pos節點
void LTPop(LTNode* pos);
//鏈表銷毀
void LTDesTroy(LTNode* phead);

List.c

#include"List.h"//創建新的節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));if (ptail == NULL){perror("malloc filed!");exit(1);}ptail->data = x;ptail->prev = ptail->next = NULL;return ptail;
}
//初始化并創建頭結點
void LTInit(LTNode** phead)
{*phead = LTBuyNode(-1);(*phead)->prev = (*phead)->next = *phead;
}
//輸出
void LTPrint(LTNode* phead)
{LTNode* ptail = phead->next;//遍歷雙向鏈表 -- 從前開始遍歷while (ptail != phead){printf("%d -> ", ptail->data);ptail = ptail->next;}printf("\n");
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//修改前后節點的指針指向phead->next->prev = newnode;phead->next = newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;//修改前后節點指針指向phead->prev->next = newnode;phead->prev = newnode;
}
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead != phead->next); //鏈表為空的話就不能進行刪除LTNode* del = phead->next;  phead->next->next->prev = phead;phead->next = phead->next->next;free(del);del = NULL;
}
//尾刪
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead); //鏈表為空不能進行刪除LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead) //遍歷鏈表{if (ptail->data == find) {return ptail;}ptail = ptail->next;}return NULL;
}
//在pos節點之前插入數據
void LTPush(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;//修改pos前后節點指針的指向pos->prev->next = newnode;pos->prev = newnode;
}
//在pos節點之后插入數據
void LTPushAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;//修改pos前后節點指針的指向pos->next->prev = newnode;pos->next = newnode;
}

感謝各位大佬支持并指出問題，

????????????????如果本篇內容對你有幫助，可以一鍵三連支持以下，感謝支持！！！