C++雙向鏈表的增刪查改操作方法講解
更新時(shí)間：2023年03月25日 08:27:31 作者：lllrx_
相較單鏈表，雙向鏈表除了data與next域，還多了一個(gè)pre域用于表示每個(gè)節(jié)點(diǎn)的前一個(gè)元素。這樣做給雙向鏈表帶來了很多優(yōu)勢(shì)。本文主要介紹了雙向鏈表的實(shí)現(xiàn)，需要的可以參考一下
一、什么是雙鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種，它是單鏈表的升級(jí)版，與單鏈表不同的是，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。而單鏈表只有一個(gè)指針，指向后繼。
雙鏈表示意圖
首先創(chuàng)立一個(gè)結(jié)構(gòu)體，其中包含一個(gè)prev指針，一個(gè)val值以及一個(gè)next指針。如圖可以看出其中prev指針指向的是上一個(gè)結(jié)構(gòu)體，而next指針指向的是下一個(gè)結(jié)構(gòu)體。結(jié)構(gòu)體代碼
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
二、雙鏈表功能函數(shù)
1、創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate()
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
if (guard == NULL)
{
perror("ListCreate");
exit(-1);
}
guard->_next = guard;
guard->_prev = guard;
return guard;
}
2、雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead;
while (cur->_next != pHead)
{
cur = cur->_next;
printf("%d->", cur->_data);
}
printf("NULL\n");
return;
}
3、雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("ListPushBack");
exit(-1);
}
newnode->_data = x;
ListNode* cur = pHead->_prev;
newnode->_next = pHead;
newnode->_prev = cur;
cur->_next = newnode;
pHead->_prev = newnode;
return;
}
4、雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
ListNode* pre = pHead->_prev->_prev;
free(pHead->_prev);
pre->_next = pHead;
pHead->_prev = pre;
return;
}
5、雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("ListPushFront");
exit(-1);
}
newnode->_data = x;
newnode->_next = pHead->_next;
newnode->_prev = pHead;
pHead->_next = newnode;
newnode->_next->_prev = newnode;
return;
}
6、雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next->_next;
free(pHead->_next);
pHead->_next = cur;
cur->_prev = pHead;
return;
}
7、雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead;
while (cur->_next != pHead)
{
cur = cur->_next;
if (cur->_data == x)
return cur;
}
printf("Can't find.\n");
return NULL;
}
8、雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("ListPushFront");
exit(-1);
}
ListNode* cur = pos->_prev;
newnode->_next = pos;
newnode->_prev = cur;
pos->_prev = newnode;
cur->_next = newnode;
return;
}
9、雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos)
{
ListNode* front = pos->_prev;
ListNode* behind = pos->_next;
free(pos);
front->_next = behind;
behind->_prev = front;
return;
}
10、雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
while (pHead->_next != pHead)
{
pHead->_next = pHead->_next->_next;
free(pHead->_next->_prev);
pHead->_next->_prev = pHead;
}
return;
}
到此這篇關(guān)于C++雙向鏈表的增刪查改操作方法講解的文章就介紹到這了,更多相關(guān)C++雙向鏈表的增刪查改內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
反調(diào)試技術(shù)，惡意代碼會(huì)用它識(shí)別自身是否被調(diào)試，或者讓調(diào)試器失效，給反病毒工程師們制造麻煩，拉長(zhǎng)提取特征碼的時(shí)間線，本章將具體總結(jié)常見的反調(diào)試基礎(chǔ)的實(shí)現(xiàn)原理以及如何過掉這些反調(diào)試手段，從而讓我們能夠繼續(xù)分析惡意代碼2021-06-06
本文主要聊一聊如何使用互斥鎖以及都有哪幾種方式實(shí)現(xiàn)互斥鎖。實(shí)現(xiàn)互斥，可以有以下幾種方式：互斥量（Mutex）、遞歸互斥量（Recursive Mutex）、讀寫鎖（Read-Write Lock）、條件變量（Condition Variable）。感興趣的同學(xué)可以參考一下2023-04-04
C語言表達(dá)式求值中類型轉(zhuǎn)換和優(yōu)先級(jí)等問題詳解
表達(dá)式求值是一個(gè)常見的問題,可以用C語言實(shí)現(xiàn),下面這篇文章主要給大家介紹了關(guān)于C語言表達(dá)式求值中類型轉(zhuǎn)換和優(yōu)先級(jí)等問題的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-05-05
這篇文章主要介紹了C++中cin的返回值問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細(xì)介紹了如何利用QPainter實(shí)現(xiàn)三維餅狀圖的繪制，由于Qt中沒有三維餅狀圖的繪制組件，因此只能自行繪制，感興趣的可以動(dòng)手嘗試一下2022-06-06
C++利用循環(huán)和棧實(shí)現(xiàn)走迷宮
這篇文章主要為大家詳細(xì)介紹了C++利用循環(huán)和棧實(shí)現(xiàn)走迷宮，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
C++修煉之構(gòu)造函數(shù)與析構(gòu)函數(shù)
本章節(jié)我們將學(xué)習(xí)類的6個(gè)默認(rèn)成員函數(shù)中的構(gòu)造函數(shù)與析構(gòu)函數(shù)，并對(duì)比C語言階段的內(nèi)容來學(xué)習(xí)它們的各自的特性，感興趣的同學(xué)可以參考閱讀2023-03-03
這篇文章主要給大家總結(jié)介紹了C語言中一些“不受限制”的字符串函數(shù)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
本文主要介紹了C/C++函數(shù)的調(diào)用約定的使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
C語言實(shí)現(xiàn)將字符串轉(zhuǎn)換為數(shù)字的方法
這篇文章主要介紹了C語言實(shí)現(xiàn)將字符串轉(zhuǎn)換為數(shù)字的方法,涉及系統(tǒng)函數(shù)atoi()函數(shù)的使用技巧,需要的朋友可以參考下2014-12-12