第C++超詳細(xì)講解單鏈表的實(shí)現(xiàn)目錄單鏈表的實(shí)現(xiàn)(從入門(mén)到熟練)概念和結(jié)構(gòu)鏈表的實(shí)現(xiàn)增刪查改接口節(jié)點(diǎn)結(jié)構(gòu)體創(chuàng)建節(jié)點(diǎn)開(kāi)辟數(shù)據(jù)打印鏈表尾插數(shù)據(jù)頭刪鏈表數(shù)據(jù)查找鏈表pos位置前插數(shù)據(jù)鏈表pos位置后插數(shù)據(jù)鏈表pos位置數(shù)據(jù)刪除鏈表節(jié)點(diǎn)釋放鏈表與順序表區(qū)別鏈表的優(yōu)缺點(diǎn)順序表的優(yōu)缺點(diǎn)

單鏈表的實(shí)現(xiàn)(從入門(mén)到熟練)

概念和結(jié)構(gòu)

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的

圖示：

注意：

鏈表結(jié)構(gòu)在邏輯上為連續(xù)的，但是物理上（內(nèi)存中）不一定連續(xù)

鏈表節(jié)點(diǎn)都是在堆上申請(qǐng)出來(lái)的，申請(qǐng)空間按一定策略分配

結(jié)構(gòu)種類(lèi)

鏈表具有多種結(jié)構(gòu)：?jiǎn)蜗騖雙向，帶頭\不帶頭，循環(huán)\非循環(huán)

實(shí)際上最常用的是：無(wú)頭單向非循環(huán)鏈表，帶頭雙向循環(huán)鏈表

鏈表的實(shí)現(xiàn)

注意：這里實(shí)現(xiàn)的是無(wú)頭單向非循環(huán)鏈表

增刪查改接口

//動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)

SListNode*BuySListNode(SLTDateTypex);

//單鏈表打印

voidSListPrint(SListNode*plist);

//單鏈表尾插

voidSListPushBack(SListNode**pplist,SLTDateTypex);

//單鏈表的頭插

voidSListPushFront(SListNode**pplist,SLTDateTypex);

//單鏈表的尾刪

voidSListPopBack(SListNode**pplist);

//單鏈表頭刪

voidSListPopFront(SListNode**pplist);

//單鏈表查找

SListNode*SListFind(SListNode*plist,SLTDateTypex);

//單鏈表在pos位置之后插入x

voidSListInsertAfter(SListNode*pos,SLTDateTypex);

//單鏈表刪除pos位置之后的值

voidSListEraseAfter(SListNode*pos);

節(jié)點(diǎn)結(jié)構(gòu)體創(chuàng)建

typedefintSLTDateType;

typedefstructSListNode

SLTDateTypedata;

structSListNode*next;

}SListNode;

節(jié)點(diǎn)開(kāi)辟

對(duì)于鏈表來(lái)說(shuō)，每需要空間就需要進(jìn)行開(kāi)辟，這里我們將之封裝成一個(gè)函數(shù)，便于后續(xù)調(diào)用直接使用（開(kāi)辟的同時(shí)進(jìn)行賦值）

參考代碼：

//鏈表節(jié)點(diǎn)開(kāi)辟

SLTNode*BuySListNode(SLTDateTypex)

//動(dòng)態(tài)分配一個(gè)節(jié)點(diǎn)

SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));

if(newnode==NULL)

//分配失敗則打印錯(cuò)誤信息并結(jié)束進(jìn)程

perror("newnodefail:");

exit(-1);

//成功則進(jìn)行賦值

newnode-data=x;

newnode-next=NULL;

//返回節(jié)點(diǎn)地址，以便后續(xù)操作

returnnewnode;

數(shù)據(jù)打印

注意：

1.對(duì)于不帶頭的鏈表來(lái)說(shuō)，打印數(shù)據(jù)不需要修改鏈表首節(jié)點(diǎn)地址（故只要傳鏈表指針）

2.用循環(huán)遍歷鏈表，每打印數(shù)據(jù)，需要指向下一個(gè)節(jié)點(diǎn)

3.依靠尾節(jié)點(diǎn)的址域?yàn)镹ULL來(lái)結(jié)束循環(huán)

代碼：

//鏈表數(shù)據(jù)打印

voidSListPrint(SLTNode*phead)//一級(jí)指針接收一級(jí)指針（打印不需改變指針本身內(nèi)容）

//創(chuàng)建一個(gè)尋址指針

SLTNode*cur=phead;

while(cur!=NULL)//后續(xù)還有節(jié)點(diǎn)

//打印數(shù)據(jù)并指向下一個(gè)節(jié)點(diǎn)

printf("%d-",cur-data);

cur=cur-next;

//最后打印空指針

printf("NULL\n");

return;

鏈表尾插數(shù)據(jù)

要尾插數(shù)據(jù)則需要遍歷找到鏈表的尾節(jié)點(diǎn)

對(duì)于不帶頭鏈表，尾插數(shù)據(jù)也可能是插在鏈表首元素的地址（當(dāng)鏈表為空），需要修改鏈表指針的內(nèi)容（故需要傳入鏈表指針的地址）

插入數(shù)據(jù)要開(kāi)辟節(jié)點(diǎn)

代碼：

//鏈表尾插數(shù)據(jù)

voidSListPushBack(SLTNode**pphead,SLTDateTypex)//二級(jí)指針接收一級(jí)指針（尾插存在需改變鏈表指針本身內(nèi)容）

//避免傳入錯(cuò)誤(直接報(bào)錯(cuò)便于找到錯(cuò)誤位置)

assert(pphead);

//接收新節(jié)點(diǎn)的地址

SLTNode*newnode=BuySListNode(x);

//頭節(jié)點(diǎn)為空

if(*pphead==NULL)

*pphead=newnode;

else

//找尾節(jié)點(diǎn)

SLTNode*tail=*pphead;//創(chuàng)建尋址節(jié)點(diǎn)

//兩個(gè)及以上節(jié)點(diǎn)的情況

while(tail-next!=NULL)

//指向下一個(gè)節(jié)點(diǎn)

tail=tail-next;

//找到了

tail-next=newnode;

return;

注意代碼中的assert的作用：

正確傳入鏈表指針的地址是不會(huì)為空的

但是對(duì)于非正常傳入鏈表指針（不是鏈表指針的地址）且此時(shí)鏈表指針為空則會(huì)發(fā)生報(bào)錯(cuò)（assert報(bào)錯(cuò)會(huì)告訴錯(cuò)誤位置），告訴程序員應(yīng)該傳入鏈表指針的地址

頭刪

注意：

刪除前需要保存當(dāng)前節(jié)點(diǎn)的址域（即保存下個(gè)節(jié)點(diǎn)的空間地址，以防丟失）

前刪數(shù)據(jù)即刪除當(dāng)前鏈表首節(jié)點(diǎn)，即需修改鏈表指針的內(nèi)容（故需傳入鏈表指針的地址）

刪除后修改鏈表指針內(nèi)容，指向新的首節(jié)點(diǎn)

如果鏈表為空時(shí)無(wú)法刪除（保存下個(gè)節(jié)點(diǎn)地址會(huì)造成非法訪問(wèn)）

代碼：

//鏈表前刪數(shù)據(jù)

voidSListPopFront(SLTNode**pphead)

//避免傳入錯(cuò)誤(直接報(bào)錯(cuò)便于找到錯(cuò)誤位置)

assert(pphead);

//鏈表為空的情況

if(*pphead==NULL)

return;

//創(chuàng)建指針保存第二個(gè)節(jié)點(diǎn)地址

SLTNode*next=(*pphead)-next;

//釋放當(dāng)前頭結(jié)點(diǎn)空間

free(*pphead);

//更新頭結(jié)點(diǎn)數(shù)據(jù)

*pphead=next;

return;

鏈表數(shù)據(jù)查找

注意：

查找時(shí)用循環(huán)遍歷鏈表

對(duì)于查找數(shù)據(jù)不用修改鏈表指針的內(nèi)容，故只需傳入鏈表指針就行了

查找到時(shí)則返回節(jié)點(diǎn)地址，否則返回NULL

代碼：

//鏈表數(shù)據(jù)查找

SLTNode*SListFind(SLTNode*phead,SLTDateTypex)

//創(chuàng)建尋址指針

SLTNode*cur=phead;

while(cur!=NULL)

if(cur-data==x)//找到數(shù)據(jù)符合節(jié)點(diǎn)

returncur;//返回節(jié)點(diǎn)地址（好處：以便后續(xù)再尋找或修改）

else

//找下一個(gè)節(jié)點(diǎn)

cur=cur-next;

//未找到數(shù)據(jù)符合節(jié)點(diǎn)

returnNULL;

鏈表pos位置前插數(shù)據(jù)

注意：

想要pos位置前插數(shù)據(jù)，不僅需要找到pos位置，還需要記錄pos的前一個(gè)節(jié)點(diǎn)位置

傳入的pos為NULL則報(bào)錯(cuò)

進(jìn)行修改前節(jié)點(diǎn)的址域成新節(jié)點(diǎn)，并讓新節(jié)點(diǎn)的址域修改成pos，這才是一個(gè)成功的pos位置前插數(shù)據(jù)

循環(huán)遍歷鏈表查找pos位置，沒(méi)有找到pos位置則什么也不干

代碼：

//鏈表pos位置往前插入(較難)（還有在pos位置之后插入，簡(jiǎn)單點(diǎn)）

voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDateTypex)

//避免傳入錯(cuò)誤(直接報(bào)錯(cuò)便于找到錯(cuò)誤位置)

assert(pphead);

assert(pos);

SLTNode*newnode=BuySListNode(x);

//首結(jié)點(diǎn)符合的情況

if(*pphead==pos)

newnode-next=*pphead;

*pphead=newnode;

else

//創(chuàng)建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節(jié)點(diǎn)

else//找到對(duì)應(yīng)空間

cur-next=newnode;

newnode-next=pos;

return;//結(jié)束尋找（否則會(huì)一直插入，造成死循環(huán)）

//未找到則什么也不干

return;

鏈表pos位置后插數(shù)據(jù)

注意：

后插則不用關(guān)注是否為首節(jié)點(diǎn)

也不用找到遍歷找到前節(jié)點(diǎn)的位置

后插則先將新節(jié)點(diǎn)址域改成pos后節(jié)點(diǎn)地址再將pos的址域改成新節(jié)點(diǎn)地址

ps:一定要注意修改鏈接節(jié)點(diǎn)址域的先后，避免地址的丟失

代碼：

//鏈表pos位置往后插入

voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDateTypex)

SLTNode*newnode=BuySListNode(x);

newnode-next=pos-next;

pos-next=newnode;

return;

鏈表pos位置數(shù)據(jù)刪除

注意：

考慮刪除首節(jié)點(diǎn)的情況，可能修改鏈表指針的內(nèi)容，故需要傳入鏈表指針的地址

對(duì)于刪除節(jié)點(diǎn)，需要先保存pos位置下一個(gè)節(jié)點(diǎn)地址，將pos位置釋放，再將pos位置前節(jié)點(diǎn)的址域改成pos位置后節(jié)點(diǎn)的地址，這才是成功的刪除pos位置節(jié)點(diǎn)

循環(huán)找pos位置，沒(méi)找到則什么也不干

參考代碼:

//鏈表pos位置刪除

voidSListErase(SLTNode**pphead,SLTNode*pos)

//避免傳入錯(cuò)誤(直接報(bào)錯(cuò)便于找到錯(cuò)誤位置)

assert(pphead);

assert(pos);

//頭結(jié)點(diǎn)符合的情況

if(*pphead==pos)

*pphead=(*pphead)-next;

free(pos);

else

//創(chuàng)建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節(jié)點(diǎn)

else//找到對(duì)應(yīng)空間

SLTNode*next=cur-next-next;

free(cur-next);

cur-next=next;

return;//結(jié)束尋找

//未找到則什么也不干

return;

鏈表節(jié)點(diǎn)釋放

注意:

對(duì)于動(dòng)態(tài)開(kāi)辟的內(nèi)存空間，在使用后一定要記得的進(jìn)行釋放（避免造成內(nèi)存泄漏）

因?yàn)殒湵砉?jié)點(diǎn)是一個(gè)個(gè)開(kāi)辟的，同樣的釋放也需要一個(gè)個(gè)進(jìn)行釋放

循環(huán)遍歷釋放當(dāng)前節(jié)點(diǎn)前需保存后一個(gè)節(jié)點(diǎn)的地址，避免地址丟失無(wú)法釋放

釋放完后，還需將鏈表指針給置空（避免使用野指針）

參考代碼:

//鏈表節(jié)點(diǎn)釋放

voidSListDestory(SLTNode**pphead)

//避免傳入錯(cuò)誤(直接報(bào)錯(cuò)便于找到錯(cuò)誤位置)

assert(pphead);

//遍歷釋放

SLTNode*cur=*pphead;

while(cur)

//保存下一個(gè)地址

SLTNode*next=cur