學習完單鏈表,現在繼續學習雙鏈表
一、雙鏈表結構
帶頭雙向循環鏈表(簡稱:雙鏈表)
注意:這?的“帶頭”跟前面我們說的“頭節點”是兩個概念,實際前面的在單鏈表階段稱呼不嚴謹,但是為了同學們更好的理解就直接稱為單鏈表的頭節點。
帶頭鏈表里的頭節點,實際為“哨兵位”,哨兵位節點不存儲任何有效元素,只是站在這?“放哨 的” “哨兵位”存在的意義: 遍歷循環鏈表避免死循環。
二、雙鏈表的實現
定義雙鏈表節點結構
與單鏈表相比,雙鏈表由于是雙向的,因此它多了一個前驅指針
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//保存指向前一個節點的指針struct ListNode* next;//指向下一個節點的指針
}LTNode;
說明
雙鏈表是帶頭鏈表,即它的頭節點(哨兵節點)是不可變的,它作用是站崗放哨,為后續的有效節點標明位置,因此,與單鏈表不同的是,雙鏈表在函數傳參的過程中傳的是一級指針,不再是二級指針(保證哨兵節點不可改變)
在接下來的雙鏈表實現中,為保持接口一致性,全部傳一級指針
雙鏈表初始化 InitList
單鏈表為空的意思就是空鏈表,鏈表內無任何節點,而雙鏈表為空時,此時鏈表中只剩下一個頭節點(哨兵節點),無有效節點,代表雙鏈表為空的意思
因此,在插入數據之前,雙鏈表必須初始化到只有一個頭結點的情況
創建一個函數LTBuyNode,表示申請節點,在初始化時給鏈表申請一個哨兵節點
思考一下,是否可以將哨兵節點的prev指針和next指針初始化為NULL?顯然是不可以的
雙鏈表是循環鏈表,它的首尾相連的,因此,鏈表的prev指針和next指針應該在初始化時指向哨兵節點本身
//申請節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if(node == NULL){perror("LTBuyNode-malloc");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化 - 傳一級指針的寫法
LTNode* InitList()
{LTNode* phead = LTBuyNode(-1);//也可以傳其他數字,表示初始化哨兵節點為某一個值return phead;
}//初始化 - 傳二級指針的寫法
void InitList(LTNode** pphead)
{//給雙鏈表創建一個哨兵節點*pphead = LTBuyNode(-1);
}
測試:
//初始化
LTNode* plist = InitList();//LTNode* plist = NULL;
//InitList(&plist);
打印鏈表 LTPrint
打印鏈表的步驟基本上和單鏈表相同,但是要注意,打印雙鏈表的節點時,哨兵節點并不需要打印出來,是從鏈表的第一個有效節點開始打印(即哨兵節點的后一個節點);
在while循環條件部分不同:雙鏈表頭尾相連,如果按照單鏈表的循環條件pcur進行打印,會陷入無限循環,因此,我們要在尾節點的next指針為頭節點時,停止打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while(pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}
尾部插入/頭部插入
尾插 LTPushBack
我們知道,鏈表的尾節點的next指針就是頭節點phead(尾節點->next=phead),頭節點phead的prev指針就是尾節點(即phead->prev=尾節點)【首尾相連】,我們要做的就是將創建的新節點newnode尾插到原鏈表的尾部作為新的尾節點并與頭節點首尾相連。
首先要做的是將newnode尾插到原鏈表中,將newnode的prev指針指向phead->prev(原尾節點),然后將newnode的next指針指向頭節點phead,這樣就將newnode節點插入到了原鏈表中
接著更新新的尾節點與頭節點頭尾相連,將原鏈表的尾節點phead->prev的next指針指向newnode,然后newnode成為新的尾節點 phead->prev
void LTPushBack(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//1.先在尾部插入新節點newnode->prev = phead->prev;newnode->next = phead;//2.更新新的尾節點與頭節點進行首尾相連phead->prev->next = newnode;phead->prev = newnode;
}
頭插 LTPushFront
要注意,我們所說的頭插是頭插到第一個有效節點的前面,即頭節點(哨兵節點)的后面
(將新節點插入到哨兵節點前面,就是尾插)
首先還是將新節點newnode插入到原鏈表中,將newnode插入到頭節點phead和第一個有效節點phead->next之間,然后更新newnode為新的第一個有效節點:
將phead->next(原第一個有效節點)的prev指針指向newnode,再將newnode的prev指針指向phead,或者先將newnode的prev指針指向phead,再通過newnode找到原第一個有效節點(newnode->next),將newnode->next的prev指針指向newnode
void LTPushFront(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//1.先在頭節點和第一個有效節點之間插入一個新節點,表示頭插newnode->next = phead->next;newnode->prev = phead;//2.更新新的節點為新的第一個有效節點phead->next->prev = newnode;phead->next = newnode;//phead->next = newnode;//newnode->next->prev = newnode;
}
尾部刪除/頭部刪除
尾刪 LTPopBack
能夠進行尾刪的條件:鏈表有效且鏈表不能為空(只有一個哨兵節點)
要將尾節點(phead->prev)刪除,將它的前一個節點phead->prev->prev變成新的尾節點:將phead->prev->prev的next指針指向phead,將phead的prev指針指向phead->prev->prev,然后將原尾節點釋放掉
但是,要注意,此時已經找不到原尾節點的位置了,無法進行釋放操作,因此,在進行以上操作前,先將原尾節點phead->prev存放在一個指針變量del中
void LTPopBack(LTNode* phead)
{//鏈表必須有效且鏈表不能為空(只有一個哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//刪除del節點free(del);del = NULL;
}
頭刪 LTPopFront
能夠進行頭刪的條件:鏈表有效且鏈表不能為空
頭刪是刪除鏈表的第一個有效節點,使第二個有效節點成為新的第一個有效節點
首先先將要刪除的phead->next節點存放在指針del中,然后將phead的next指針改為del->next(第二個有效節點),再將del->next的prev指針指向phead,然后將del釋放掉
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
查找鏈表 LTFind
通過遍歷鏈表找到想要找的節點數據,如果找到了,返回這個節點的指針,如果沒有找到,返回NULL
LTNode* LTFind(LTNode* phead,LTDataType x)
{LTNode* pcur = phead->next;while(pcur != phead){if(pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到return NULL;
}
在pos位置之后插入數據 LTInsert
需要將新節點newnode插入在pos和pos->next之間,即先將newnode的prev指針指向pos,newnode的next指針指向pos->next,然后將newnode節點變成新的pos->next節點
注意有一種情況:當pos的位置是尾節點時,就是要在phead->prev和phead之間插入數據,即尾插
但是我們在對該函數傳參時,并不需要用到phead(在pos位置之后插入節點只需知道pos和pos->next,以及要插入的數據即可),因此,不能直接調用尾插函數。不過我們并不需要調用尾插函數也可以做到,因為將newnode插入pos和pos->next之間的做法也適用于尾插的情況
這里不再畫圖講解
void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}
在pos位置之前插入數據 LTInsertBefort
需要將newnode節點插入在pos->prev與pos之間,先將newnode的prev指針指向pos->prev,再將newnode的next指針指向pos,表示插入新節點成功,當然,這也有一種情況:當pos的圍位置是第一個有效節點時,就是頭插的方法,不過我們也不需要調用函數使用,因為以上的操作已經覆蓋了頭插做法
void LTInsertBefort(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}
刪除pos節點
刪除pos節點,直接修改pos->next的prev指針為pos->prev,pos->prev的next指針為pos->next,然后將pos節點釋放掉即可
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
銷毀鏈表?LTDestroy
在遍歷銷毀鏈表之前,應該保存一下下一個節點的指針,避免后續找不到位置
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此時pcur指向phead,而phead還沒有被銷毀free(phead);phead = NULL;
}
注意
LTErase 和 LTDestroy 函數參數理論上要傳二級指針,因為我們需要讓形參的改變影響到實參,但為了保持接口一致性傳一級指針,傳一級指針存在的問題:當形參phead置為NULL后,實參plist不會被修改為NULL,因此解決辦法:調用完方法后手動將實參置為NULL
//測試刪除pos節點
LTErase(find);
find = NULL;
LTPrint(plist);//銷毀鏈表
LTDestroy(plist);
plist = NULL;
三、完整代碼
List.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;
//定義雙向鏈表節點的結構
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//聲明雙向鏈表中提供的方法
//初始化
//void InitList(LTNode** pphead);
LTNode* InitList();//打印鏈表
void LTPrint(LTNode* phead);//在插入數據之前,鏈表必須初始化到只有一個頭結點的情況
//不改變哨兵位的地址,因此傳一級指針即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x);//刪除pos節點
void LTErase(LTNode* pos);//銷毀鏈表
void LTDestroy(LTNode* phead);
List.c#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//申請節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化
//void InitList(LTNode** pphead)
//{
// //給雙鏈表申請一個哨兵位
// *pphead = LTBuyNode(-1);
//}
LTNode* InitList()
{LTNode* phead = LTBuyNode(-1);return phead;
}
//打印鏈表
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x) //將新節點插入到頭節點的前面,即尾插
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnode//1.先在尾部插入新節點newnode->prev = phead->prev;newnode->next = phead;//2.更新新的尾節點與頭節點進行首尾相連phead->prev->next = newnode;phead->prev = newnode;
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x) //頭插,要往頭節點后面插入
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next//1.先在頭節點和第一個有效節點之間插入一個新節點,表示頭插newnode->next = phead->next;newnode->prev = phead;//2.更新新的節點為新的第一個有效節點phead->next->prev = newnode;phead->next = newnode;//也可以這樣寫/*phead->next = newnode;newnode->next->prev = newnode;*/
}
//尾刪
void LTPopBack(LTNode* phead)
{//鏈表必須有效且鏈表不能為空(只有一個哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//刪除del節點free(del);del = NULL;
}
//頭刪
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//刪除del節點free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到return NULL;
}
//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}
//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos->prev newnode posnewnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}
//刪除pos節點
void LTErase(LTNode* pos)
{//pos理論上來說不能為phead,但是沒有參數phead,無法增加校驗assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//銷毀鏈表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此時pcur指向phead,而phead還沒有被銷毀free(phead);phead = NULL;
}
test.c#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"void ListTest01()
{//初始化/*LTNode* plist = NULL;InitList(&plist);*/LTNode* plist = InitList();//測試尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//測試頭插/*LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);*///測試尾刪/*LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);*///測試頭刪/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);*///測試查找鏈表LTNode* find = LTFind(plist, 2);/*if (find == NULL){printf("找不到\n");}else{printf("找到了\n");}*///測試在pos位置之后插入數據/*LTInsert(find, 66);LTPrint(plist);*///測試在pos位置之前插入數據/*LTInsertFront(find, 88);LTPrint(plist);*///測試刪除pos節點LTErase(find);find = NULL; //LTErase 和 LTDestroy 函數參數理論上要傳二級指針,因為我們需要讓形參的改變影響到實參,但為了保持接口一致性傳LTPrint(plist); //一級指針,傳一級指針存在的問題:當形參phead置為NULL后,實參plist不會被修改為NULL,因此解決辦法:調用完方法后//手動將實參置為NULL//銷毀鏈表LTDestroy(plist);plist = NULL;
}
int main()
{ListTest01();return 0;
}