第C++超詳細講解單鏈表的實現目錄單鏈表的實現(從入門到熟練)概念和結構鏈表的實現增刪查改接口節點結構體創建節點開辟數據打印鏈表尾插數據頭刪鏈表數據查找鏈表pos位置前插數據鏈表pos位置后插數據鏈表pos位置數據刪除鏈表節點釋放鏈表與順序表區別鏈表的優缺點順序表的優缺點

單鏈表的實現(從入門到熟練)

概念和結構

概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構

數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的

圖示：

注意：

鏈表結構在邏輯上為連續的，但是物理上（內存中）不一定連續

鏈表節點都是在堆上申請出來的，申請空間按一定策略分配

結構種類

鏈表具有多種結構：單向\雙向，帶頭\不帶頭，循環\非循環

實際上最常用的是：無頭單向非循環鏈表，帶頭雙向循環鏈表

鏈表的實現

注意：這里實現的是無頭單向非循環鏈表

增刪查改接口

//動態申請一個節點

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);

節點結構體創建

typedefintSLTDateType;

typedefstructSListNode

SLTDateTypedata;

structSListNode*next;

}SListNode;

節點開辟

對于鏈表來說，每需要空間就需要進行開辟，這里我們將之封裝成一個函數，便于后續調用直接使用（開辟的同時進行賦值）

參考代碼：

//鏈表節點開辟

SLTNode*BuySListNode(SLTDateTypex)

//動態分配一個節點

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

if(newnode==NULL)

//分配失敗則打印錯誤信息并結束進程

perror("newnodefail:");

exit(-1);

//成功則進行賦值

newnode-data=x;

newnode-next=NULL;

//返回節點地址，以便后續操作

returnnewnode;

數據打印

注意：

1.對于不帶頭的鏈表來說，打印數據不需要修改鏈表首節點地址（故只要傳鏈表指針）

2.用循環遍歷鏈表，每打印數據，需要指向下一個節點

3.依靠尾節點的址域為NULL來結束循環

代碼：

//鏈表數據打印

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

//創建一個尋址指針

SLTNode*cur=phead;

while(cur!=NULL)//后續還有節點

//打印數據并指向下一個節點

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

cur=cur-next;

//最后打印空指針

printf("NULL\n");

return;

鏈表尾插數據

要尾插數據則需要遍歷找到鏈表的尾節點

對于不帶頭鏈表，尾插數據也可能是插在鏈表首元素的地址（當鏈表為空），需要修改鏈表指針的內容（故需要傳入鏈表指針的地址）

插入數據要開辟節點

代碼：

//鏈表尾插數據

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

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//接收新節點的地址

SLTNode*newnode=BuySListNode(x);

//頭節點為空

if(*pphead==NULL)

*pphead=newnode;

else

//找尾節點

SLTNode*tail=*pphead;//創建尋址節點

//兩個及以上節點的情況

while(tail-next!=NULL)

//指向下一個節點

tail=tail-next;

//找到了

tail-next=newnode;

return;

注意代碼中的assert的作用：

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

但是對于非正常傳入鏈表指針（不是鏈表指針的地址）且此時鏈表指針為空則會發生報錯（assert報錯會告訴錯誤位置），告訴程序員應該傳入鏈表指針的地址

頭刪

注意：

刪除前需要保存當前節點的址域（即保存下個節點的空間地址，以防丟失）

前刪數據即刪除當前鏈表首節點，即需修改鏈表指針的內容（故需傳入鏈表指針的地址）

刪除后修改鏈表指針內容，指向新的首節點

如果鏈表為空時無法刪除（保存下個節點地址會造成非法訪問）

代碼：

//鏈表前刪數據

voidSListPopFront(SLTNode**pphead)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//鏈表為空的情況

if(*pphead==NULL)

return;

//創建指針保存第二個節點地址

SLTNode*next=(*pphead)-next;

//釋放當前頭結點空間

free(*pphead);

//更新頭結點數據

*pphead=next;

return;

鏈表數據查找

注意：

查找時用循環遍歷鏈表

對于查找數據不用修改鏈表指針的內容，故只需傳入鏈表指針就行了

查找到時則返回節點地址，否則返回NULL

代碼：

//鏈表數據查找

SLTNode*SListFind(SLTNode*phead,SLTDateTypex)

//創建尋址指針

SLTNode*cur=phead;

while(cur!=NULL)

if(cur-data==x)//找到數據符合節點

returncur;//返回節點地址（好處：以便后續再尋找或修改）

else

//找下一個節點

cur=cur-next;

//未找到數據符合節點

returnNULL;

鏈表pos位置前插數據

注意：

想要pos位置前插數據，不僅需要找到pos位置，還需要記錄pos的前一個節點位置

傳入的pos為NULL則報錯

進行修改前節點的址域成新節點，并讓新節點的址域修改成pos，這才是一個成功的pos位置前插數據

循環遍歷鏈表查找pos位置，沒有找到pos位置則什么也不干

代碼：

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

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

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

assert(pos);

SLTNode*newnode=BuySListNode(x);

//首結點符合的情況

if(*pphead==pos)

newnode-next=*pphead;

*pphead=newnode;

else

//創建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節點

else//找到對應空間

cur-next=newnode;

newnode-next=pos;

return;//結束尋找（否則會一直插入，造成死循環）

//未找到則什么也不干

return;

鏈表pos位置后插數據

注意：

后插則不用關注是否為首節點

也不用找到遍歷找到前節點的位置

后插則先將新節點址域改成pos后節點地址再將pos的址域改成新節點地址

ps:一定要注意修改鏈接節點址域的先后，避免地址的丟失

代碼：

//鏈表pos位置往后插入

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

SLTNode*newnode=BuySListNode(x);

newnode-next=pos-next;

pos-next=newnode;

return;

鏈表pos位置數據刪除

注意：

考慮刪除首節點的情況，可能修改鏈表指針的內容，故需要傳入鏈表指針的地址

對于刪除節點，需要先保存pos位置下一個節點地址，將pos位置釋放，再將pos位置前節點的址域改成pos位置后節點的地址，這才是成功的刪除pos位置節點

循環找pos位置，沒找到則什么也不干

參考代碼:

//鏈表pos位置刪除

voidSListErase(SLTNode**pphead,SLTNode*pos)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

assert(pos);

//頭結點符合的情況

if(*pphead==pos)

*pphead=(*pphead)-next;

free(pos);

else

//創建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節點

else//找到對應空間

SLTNode*next=cur-next-next;

free(cur-next);

cur-next=next;

return;//結束尋找

//未找到則什么也不干

return;

鏈表節點釋放

注意:

對于動態開辟的內存空間，在使用后一定要記得的進行釋放（避免造成內存泄漏）

因為鏈表節點是一個個開辟的，同樣的釋放也需要一個個進行釋放

循環遍歷釋放當前節點前需保存后一個節點的地址，避免地址丟失無法釋放

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

參考代碼:

//鏈表節點釋放

voidSListDestory(SLTNode**pphead)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//遍歷釋放

SLTNode*cur=*pphead;

while(cur)

//保存下一個地址

SLTNode*next=cur