🔥個人主頁:@草莓熊Lotso
🎬作者簡介:C++研發方向學習者
📖個人專欄:?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》
??人生格言:生活是默默的堅持,毅力是永久的享受。???
前言:在上篇博客中我們進行了雙向鏈表概念的理解以及哨兵位頭節點的初始化,那么我們這次將會繼續來實現雙向鏈表中的其它接口,還是一樣,分布實現后再把所有的代碼展示出來?
目錄
?一.雙向鏈表的尾插
二.雙向鏈表的頭插?
三.?雙向鏈表的尾刪
四.雙向鏈表的頭刪?
五.雙向鏈表查找
六.雙向鏈表在指定位置之后插入
七.雙向鏈表指定位置刪除
八.雙向鏈表的銷毀以及初始化部分的優化
九.代碼展現
List.h:
List.c:
test.c:
?一.雙向鏈表的尾插
--實現尾插之前,我們需要先實現一個申請新節點的操作,方便后續的使用,具體操作如下:
ListNode* LTBuyNode(LTDataType x)
{ListNode* newcode = (ListNode*)malloc(sizeof(ListNode));newcode->data = x;newcode->next = newcode;newcode->prev = newcode;return newcode;
}
--利用這個我們還可以優化前面的頭節點初始化,大家可以自己先嘗試一下,接下來我們還是回到尾插的實現
List.c:
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//申請一個新節點ListNode* newcode = LTBuyNode(x);//phead->prev newcode phead//先連newcodenewcode->prev = phead->prev;newcode->next = phead;//再把phead->prev的先處理掉phead->prev->next = newcode;phead->prev = newcode;
}
重點提示:?
我們先申請一個新節點,再把新節點的前驅指針和后繼指針先對應的連上,再處理受到影戲的兩個節點,因為要通過頭節點找d3,所以我們先處理phead->prev,最后再處理phead
--在測試之前,我們還需要定義一個打印的接口,便于我們觀察?
//打印
void LTPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}
--這里的pucr是從第一個節點開始的,也就是哨兵位的下一個節點,直達回到哨兵位結束,哨兵位不打印出來
test.c:
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);
}
int main()
{test1();return 0;
}
?--測試完成,打印沒有問題,退出碼為0
二.雙向鏈表的頭插?
?--雙向鏈表的頭插實現起來也不會很難,但注意這里的頭插可不是插入在哨兵位節點的前面哈,而是第一個節點的前面,一定不要搞錯了
List.c:
//頭插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newcode = LTBuyNode(x);//phead newcode phead->nextnewcode->prev = phead;newcode->next = phead->next;phead->next->prev = newcode;phead->next = newcode;
}
重點提示:?
這里的大體思路和尾插一樣,找到和申請的新節點有關的兩個節點,先把newcode的前驅指針和后繼指針指向對應位置,再處理需要用phead尋找的phead->next,最后再把phead需要處理的連上就可以了
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);
}
int main()
{test1();return 0;
}
--測試完成,打印沒有問題,頭插了一個5,退出碼為0
三.?雙向鏈表的尾刪
--實現尾刪之前,我們需要先實現一個判空的接口,如果鏈表為空則不能繼續刪除了,具體操作如下:
//判空
bool LTEmpty(ListNode* phead)
{assert(phead);return phead->next == NULL;
}
List.c:
//尾刪
void LTPopBack(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->prev;//del->prev del pheaddel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
重點提示:
我們先進行一下判空,如果鏈表不為空繼續后面的操作,首先我們需要刪除的節點通過phead->prev找到,我們定義一個del,然后尾刪操作受到影響的其它兩個節點一個為del->prev,一個為head,把它們兩個需要連的連上,再釋放掉del指針就可以了
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);
}
int main()
{test1();return 0;
}
--測試完成,打印沒有問題,刪掉了尾部的4,退出碼為0
四.雙向鏈表的頭刪?
List.c:
//頭刪
void LTPopFront(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
重點提示:?
頭刪操作的思路和尾刪相似,先還是判空,然后后續需要通過del記錄下phead->next這個我們要刪除的節點,再找到兩個受到影響的節點,對應連上,最后釋放掉del就可以了
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);//頭刪LTPopFront(plist);LTPrint(plist);
}
int main()
{test1();return 0;
}
--測試完成,打印沒有問題,頭刪掉了5,退出碼為0
五.雙向鏈表查找
--在實現指定位置之前插入以及刪除之前,我們需要實現一個查找的接口
List.c:
//查找
ListNode* LTFind(ListNode* phead,LTDataType x)
{assert(!LTEmpty(phead));ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}
重點提示:?
遍歷的方法和打印是一樣的,如果在遍歷過程中找到了我們需要查找的數據就返回當前位置的節點,沒有就返回空
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);//頭刪LTPopFront(plist);LTPrint(plist);//查找ListNode*pos=LTFind(plist, 2);if (pos)printf("找到了\n");elseprintf("沒找到\n");
}
int main()
{test1();return 0;
}
--測試完成,能夠找到,退出碼為0
六.雙向鏈表在指定位置之后插入
--我們在這里先實現一下在指定位置之后的插入操作,大家后續可以自己再嘗試一下在指定位置之前插入
List.c:
//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newcode = LTBuyNode(x);//pos newcode pos->nextnewcode->prev = pos;newcode->next = pos->next;pos->next->prev = newcode;pos->next = newcode;}
重點提示:?
--在指定位置之后的插入操作其實也沒有很難,還是先斷言,后續就是先申請一個新節點,跟頭插尾插一樣,先處理newcode的前驅指針和后繼指針,然后再是受到影響的兩個節點里面先處理需要通過pos節點找到的pos->next節點,最后再處理pos
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);//頭刪LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);//指定位置之后插入LTInsert(pos, 100);LTPrint(plist);}
int main()
{test1();return 0;
}
--測試完成,打印沒有問題,在2后插入了100,退出碼為0
七.雙向鏈表指定位置刪除
List.c:
//指定位置刪除
void LTErase(ListNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
重點提示:?
先斷言,后續操作思路和頭刪尾刪也很像,這里是通過pos指針找到兩個受到影響的節點,我們直接處理好這兩個節點之前的關系就可以了,最后再直接釋放掉pos
test.c:?
#include"List.h"void test1()
{//初始化,明天優化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);//頭刪LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);//指定位置之后插入LTInsert(pos, 100);LTPrint(plist);//指定位置刪除LTErase(pos);LTPrint(plist);
}
int main()
{test1();return 0;
}
--測試完成,打印沒有問題,退出碼為0
八.雙向鏈表的銷毀以及初始化部分的優化
--在這里我們先來實現一下雙向鏈表的銷毀,具體的遍歷操作和之前一樣,我們在遍歷過程中每次銷毀一個節點之前先把它的下一個節點存下來,最后銷毀完后利用存下來的使它來到下一個位置,具體操作代碼如下
//銷毀
void LTDestory(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}
?--大家需要注意的是我們這里其實按道理來說是要用二級指針的,但是前面其它接口都用的一級,這里和初始化部分也需要統一比較好點,我們可以在測試文件中最后銷毀完手動將頭節點置為空,那么我們的初始化操作的優化我也直接給大家展示為代碼了,其實就是改變了一下函數的返回類型,測試文件中也有所修改,在最后的代碼展現的時候大家可以看看
//頭節點初始化的優化
ListNode* LTInit()
{ListNode* phead = LTBuyNode(-1);return phead;
}
九.代碼展現
List.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//前驅指針,指向前一個指針struct ListNode* prev;//后繼指針,指向后一個指針struct ListNode* next;
}ListNode;//初始化頭節點
void LTInit(ListNode** pphead);
//ListNode* LTInit();
//打印
void LTPrint(ListNode* phead);
//銷毀
void LTDestory(ListNode* phead);
//尾插
void LTPushBack(ListNode* phead, LTDataType x);
//頭插
void LTPushFront(ListNode* phead, LTDataType x);
//尾刪
void LTPopBack(ListNode* phead);
//頭刪
void LTPopFront(ListNode* phead);
//查找
ListNode* LTFind(ListNode* phead,LTDataType x);
//判空
bool LTEmpty(ListNode* phead);
//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x);
//指定位置刪除
void LTErase(ListNode* pos);
List.c:
#include"List.h"//頭節點初始化
void LTInit(ListNode** pphead)
{ListNode* ph = (ListNode*)malloc(sizeof(ListNode));if (ph==NULL){perror("malloc fail!");exit(1);}*pphead = ph;(*pphead)->data = -1;//隨便給個不用的就行(*pphead)->prev = *pphead;(*pphead)->next = *pphead;
}//頭節點初始化的優化
//ListNode* LTInit()
//{
// ListNode* phead = LTBuyNode(-1);
// phead->prev = phead;
// phead->next = phead;
// return phead;
//}//打印
void LTPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//銷毀
void LTDestory(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead =NULL;
}
//判空
bool LTEmpty(ListNode* phead)
{assert(phead);return phead->next == NULL;
}ListNode* LTBuyNode(LTDataType x)
{ListNode* newcode = (ListNode*)malloc(sizeof(ListNode));newcode->data = x;newcode->next =newcode;newcode->prev =newcode;return newcode;
}
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//申請一個新節點ListNode* newcode = LTBuyNode(x);//phead->prev newcode phead//先連newcodenewcode->prev = phead->prev;newcode->next = phead;//再把phead->prev的先處理掉phead->prev->next = newcode;phead->prev = newcode;
}//頭插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newcode = LTBuyNode(x);//phead newcode phead->nextnewcode->prev = phead;newcode->next = phead->next;phead->next->prev = newcode;phead->next = newcode;
}//尾刪
void LTPopBack(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->prev;//del->prev del pheaddel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//頭刪
void LTPopFront(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//查找
ListNode* LTFind(ListNode* phead,LTDataType x)
{assert(!LTEmpty(phead));ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newcode = LTBuyNode(x);//pos newcode pos->nextnewcode->prev = pos;newcode->next = pos->next;pos->next->prev = newcode;pos->next = newcode;}//指定位置刪除
void LTErase(ListNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
test.c:
#include"List.h"void test1()
{//初始化ListNode* plist = NULL;LTInit(&plist);////優化//ListNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//頭插LTPushFront(plist, 5);LTPrint(plist);//尾刪LTPopBack(plist);LTPrint(plist);//頭刪LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);/*if (pos)printf("找到了\n");elseprintf("沒找到\n");*///指定位置之后插入LTInsert(pos, 100);LTPrint(plist);//指定位置刪除LTErase(pos);LTPrint(plist);//銷毀LTDestory(plist);plist == NULL;
}
int main()
{test1();return 0;
}
特別補充--順序表和單鏈表的對比
往期回顧:
【數據結構初階】--單鏈表(一)
【數據結構初階】--單鏈表(二)
【數據結構初階】--雙向鏈表(一)
結語: 在這篇博客中我們實現了雙向鏈表的所有接口,大家下來也可以自己去嘗試實現以下,可以通過畫圖輔助,如果文章對你有幫助的話,歡迎評論,點贊,收藏加關注,感謝大家的支持。