? ? ? ? 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)正是所謂的單鏈表，何謂單鏈表？通過地址將每一個(gè)數(shù)據(jù)元素串起來，進(jìn)行使用，這可以彌補(bǔ)順序表在進(jìn)行任意位置的插入和刪除需要進(jìn)行大量的數(shù)據(jù)元素移動(dòng)的缺點(diǎn)，只需要修改指針的指向即可；單鏈表的種類又可劃分為很多種，本篇博客詳細(xì)介紹帶頭結(jié)點(diǎn)單鏈表的設(shè)計(jì)與實(shí)現(xiàn)，掌握單鏈表的關(guān)鍵是要進(jìn)行畫圖分析；單鏈表同時(shí)也是筆試和面試的必考點(diǎn)，因此，掌握好該章節(jié)非常重要！
一、單鏈表的基本概念和結(jié)構(gòu)
? ? ? ?線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)正是所謂的單鏈表，那么什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
1.1 帶頭結(jié)點(diǎn)單鏈表的概念
? ? ? 單鏈表的整體結(jié)構(gòu)由一個(gè)個(gè)的結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)類型包括兩個(gè)部分：存儲(chǔ)的數(shù)據(jù)元素(數(shù)據(jù)域)和存放下一個(gè)結(jié)點(diǎn)地址的指針域(它是一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針，存儲(chǔ)的是下一個(gè)結(jié)點(diǎn)的地址)，所謂帶頭結(jié)點(diǎn)，是因?yàn)樗嬖谝粋€(gè)標(biāo)記結(jié)點(diǎn)，它的數(shù)據(jù)域可以不指定，它的指針域存儲(chǔ)的是第一個(gè)有效結(jié)點(diǎn)的地址，通過指針域便可以訪問每一個(gè)結(jié)點(diǎn)，尾結(jié)點(diǎn)是最后一個(gè)數(shù)據(jù)元素，因此它的指針域?yàn)?NULL；
? ? ? ?帶頭結(jié)點(diǎn)的單鏈表主要包括兩部分：指向頭結(jié)點(diǎn)的指針，即頭指針和存儲(chǔ)單鏈表有效數(shù)據(jù)元素個(gè)數(shù)的size變量，請(qǐng)注意，與順序表不同，單鏈表的結(jié)點(diǎn)是按需向堆區(qū)動(dòng)態(tài)申請(qǐng)，而不是直接進(jìn)行擴(kuò)容，用一個(gè)結(jié)點(diǎn)，向堆區(qū)申請(qǐng)一個(gè)結(jié)點(diǎn)，因此，它不需要來記錄鏈表總?cè)萘康腸apacity變量。
頭結(jié)點(diǎn)與頭指針的異同：
?
1.2 帶頭結(jié)點(diǎn)的單向鏈表的結(jié)構(gòu)
? 如上所示，清晰的展示了帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)，需要注意的是：單鏈表的每一個(gè)結(jié)點(diǎn)是在堆區(qū)進(jìn)行申請(qǐng)的，而單鏈表的頭指針和有效數(shù)據(jù)元素個(gè)數(shù)變量是在棧區(qū)開辟的！
二、單鏈表的分類
? ? ?實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
2.1. 單向或者雙向
2.2 帶頭或者不帶頭
2.3 循環(huán)或者非循環(huán)
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：
1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。?
三、帶頭結(jié)點(diǎn)的單向鏈表接口實(shí)現(xiàn)（增刪改查函數(shù)實(shí)現(xiàn)）及算法效率分析
? ? ? 引入的頭文件：
#include "SeqList.h"
#include<assert.h>
#include<stdlib.h>? ? ? ?單鏈表的主要操作為增刪改查，這里詳細(xì)展示這些基本操作的實(shí)現(xiàn)思想和畫圖分析以及代碼實(shí)現(xiàn)和算法效率分析，主要接口函數(shù)如下所示：
注意：單鏈表與順序表不同，由于它是按需索取，因此，不需要進(jìn)行判滿和擴(kuò)容操作；
//代碼實(shí)現(xiàn) -- 算法效率分析
//1.初始化鏈表
void InitList(PList plist);
//2.清空鏈表 --- 釋放有效結(jié)點(diǎn)(頭結(jié)點(diǎn)未釋放)
void ClearList(PList plist);
//3.銷毀鏈表 -- 釋放所有結(jié)點(diǎn)
void DestoryList(PList plist);
//4.獲取鏈表的數(shù)據(jù)元素個(gè)數(shù)
int GetSize(const PList plist);
//5.鏈表判空
bool IsEmpty(const PList plist);
//6.頭插數(shù)據(jù)元素
void Push_Front(PList plist, ElemType val);
//7.尾插數(shù)據(jù)元素
void Push_Back(PList plist, ElemType val);
//按位置插入 插入的第幾個(gè)有效結(jié)點(diǎn)
bool Insert_Pos(PList plist, int pos, ElemType val);
//8.在指定結(jié)點(diǎn)之前插入數(shù)據(jù)元素
bool Insert_Prev(PList plist, Node* ptr, ElemType val);
//9.在指定結(jié)點(diǎn)之后插入數(shù)據(jù)元素
bool Insert_Next(PList plist, Node* ptr, ElemType val);
//10.頭刪
bool Pop_Front(PList plist);
//11.尾刪
void Pop_Back(PList plist);
//按位置刪除
bool Delete_Pos(PList plist, int pos, ElemType val);
//12.刪除指定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
bool Erase_Prev(PList plist, Node* ptr);
//13.刪除指定結(jié)點(diǎn)的后繼結(jié)點(diǎn)
bool Erase_Next(PList plist, Node* ptr);
//14.刪除與val值相等的所有數(shù)據(jù)結(jié)點(diǎn)
void Remove_All(PList plist, ElemType val);
//15.打印鏈表中的數(shù)據(jù)元素
void PrintList(const PList plist);
//查找操作,按值查找
//16.返回與val值相等的結(jié)點(diǎn)
Node* FindValue(const PList plist, ElemType val);
//17.返回與val值相等的前驅(qū)結(jié)點(diǎn)
Node* FindValue_Prev(const PList plist, ElemType val);
//18.返回與val值相等的后繼結(jié)點(diǎn)
Node* FindValue_Next(const PList plist, ElemType val);
//查找操作,按位置查找
//19.返回pos位置的結(jié)點(diǎn)
Node* FindPos(const PList plist, int pos);
//20.返回pos位置的前驅(qū)結(jié)點(diǎn)
Node* FindPos_Prev(const List plist, int pos);
//21.返回pos位置的后繼結(jié)點(diǎn)
Node* FindPos_Next(const List plist, int pos);3.1 結(jié)點(diǎn)設(shè)計(jì)
? ? ? ?每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)域和指針域（指向下一個(gè)結(jié)點(diǎn)/存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針）構(gòu)成。因此設(shè)計(jì)結(jié)點(diǎn)主要設(shè)計(jì)這兩個(gè)成員變量。
? ? ? ?強(qiáng)調(diào)結(jié)構(gòu)體自身引用（自己嵌套自己必須使用struct，即使使用typedef關(guān)鍵字進(jìn)行重命名）結(jié)構(gòu)體內(nèi)部不可以定義自身的結(jié)構(gòu)體變量，但是可以定義自身結(jié)構(gòu)體指針變量，因?yàn)橹羔樑c類型無關(guān)，占用內(nèi)存空間就是4個(gè)字節(jié)！
typedef int ElemType;
typedef struct Node
{
ElemType data; //數(shù)據(jù)域
struct Node* next; //指針域，保存下一個(gè)結(jié)點(diǎn)的地址（指向下一個(gè)結(jié)點(diǎn)）結(jié)點(diǎn)類型的指針
}Node;3.2 帶頭結(jié)點(diǎn)單鏈表設(shè)計(jì)
? ? ? 帶頭結(jié)點(diǎn)的單鏈表主要包括兩個(gè)部分：一個(gè)指向頭結(jié)點(diǎn)的頭指針，另一個(gè)是記錄單鏈表有效數(shù)據(jù)個(gè)數(shù)的變量。
typedef struct SingleLink
{
Node* head; //頭指針，指向頭結(jié)點(diǎn)的指針
int cursize; //有效結(jié)點(diǎn)個(gè)數(shù)
}List, * PList;3.3? 單鏈表的初始化
? ? ? 單鏈表的初始化主要是申請(qǐng)一個(gè)頭結(jié)點(diǎn)和對(duì)有效數(shù)據(jù)個(gè)數(shù)進(jìn)行初始化賦值，為方便后續(xù)操作，把申請(qǐng)一個(gè)結(jié)點(diǎn)封裝成函數(shù)，后續(xù)直接調(diào)用。
//申請(qǐng)結(jié)點(diǎn)封裝成函數(shù)，方便后續(xù)代碼復(fù)用
static Node* BuyNode(ElemType data, Node* next)
{
Node* p = (Node*)malloc(sizeof(Node));
assert(p!=NULL);
{
p->data = data;
p->next = next;
}
return p;
}
//1.初始化鏈表
void InitList(PList plist)
{
assert(plist != NULL);
plist->head = BuyNode(0, NULL); //頭部標(biāo)記結(jié)點(diǎn)
assert(plist->head != NULL);
plist->cursize = 0;
}3.4? 清空鏈表（只保留頭結(jié)點(diǎn)）
思想：文章來源：http://www.zghlxwxcb.cn/news/detail-826357.html
? ? 空鏈表的標(biāo)志是：頭結(jié)點(diǎn)的指針域?yàn)镹ULL，依次進(jìn)行指針域貫穿，刪除有效結(jié)點(diǎn)即可；
注意事項(xiàng)：
? ? 使用連續(xù)指向符，需要進(jìn)行防止空指針解引用崩潰，邊界進(jìn)行判斷，如鏈表為空，鏈表只有一個(gè)有效結(jié)點(diǎn)等；
//2.清空鏈表 --- 釋放有效結(jié)點(diǎn)(頭結(jié)點(diǎn)未釋放)
void ClearList(PList plist)
{
assert(plist != NULL);
while (plist->head->next != NULL) //依次刪除有效結(jié)點(diǎn)
{
//1.結(jié)點(diǎn)指針保存待刪除結(jié)點(diǎn)的地址
Node* p = plist->head->next;
//2.進(jìn)行貫穿
plist->head->next = p->next;
//3.釋放待刪結(jié)點(diǎn)
free(p);
plist->cursize--;
}
}3.5? 銷毀單鏈表（頭結(jié)點(diǎn)+有效結(jié)點(diǎn)全部銷毀）
思想：
? ? ? 直接調(diào)用清空函數(shù)，再銷毀頭結(jié)點(diǎn)即可；??
void DestoryList(PList plist)
{
assert(plist != NULL);
if (plist->head == NULL)
return;
ClearList(plist);
free(plist->head); //防止野指針
}3.6? 獲取鏈表有效數(shù)據(jù)元素個(gè)數(shù)
思想：
? ? 第一種：直接返回記錄鏈表的有效數(shù)據(jù)元素個(gè)數(shù)的變量
? ? 第二種：計(jì)數(shù)器思想，遍歷鏈表，直到遍歷到尾結(jié)點(diǎn)的指針域?yàn)镹ULL；
//4.獲取鏈表的數(shù)據(jù)元素個(gè)數(shù)
第一種：直接返回
int GetSize(const PList plist)
{
assert(plist != NULL);
return plist->cursize;
}
第二種：遍歷鏈表計(jì)數(shù)器思想
int GetSize(const PList plist)
{
assert(plist != NULL);
int count=0;
for(Node*p=plist->head->next;p->next!=NULL;p=p->next)
{
count++;
}
return count;
}3.7? 鏈表判空
思想：
第一種：比較記錄的有效數(shù)據(jù)元素個(gè)數(shù)是否為0
第二種：判斷頭結(jié)點(diǎn)的指針域是否為空，如果為空代表沒有有效結(jié)點(diǎn)
//5.鏈表判空
bool IsEmpty(const PList plist)
{
assert(plist!=NULL);
return plist->head->next == NULL;
//return plist->cursize == 0;
}3.8? 頭插數(shù)據(jù)
思想：
? ? ? 申請(qǐng)一個(gè)結(jié)點(diǎn)，把他插入到第一個(gè)有效數(shù)據(jù)結(jié)點(diǎn)的前面；?
注意事項(xiàng)：
? ? ?先牽右手再牽左手?。?！防止內(nèi)存泄漏
?
//6.頭插數(shù)據(jù)元素
void Push_Front(PList plist, ElemType val)
{
assert(plist != NULL);
Node* p = BuyNode(val, NULL);
assert(p != NULL);
//先牽右手
p->next = plist->head->next;
//再牽左手
plist->head->next = p;
plist->cursize++;
}3.9? 尾插數(shù)據(jù)
思想：
? ? ? 先申請(qǐng)一個(gè)結(jié)點(diǎn)，然后找到尾巴結(jié)點(diǎn)，最后把這個(gè)結(jié)點(diǎn)通過指針域連接起來
//7.尾插數(shù)據(jù)元素
void Push_Back(PList plist, ElemType val)
{
assert(plist != NULL);
Node* newnode = BuyNode(val, NULL);
assert(newnode != NULL);
Node* p = plist->head;
while (p->next != NULL)
{
p = p->next;
}
p->next = newnode;
plist->cursize++;
}3.10 任意位置插入數(shù)據(jù)
思想：
? ? ? 先申請(qǐng)一個(gè)結(jié)點(diǎn)，再找到插入位置的前一個(gè)結(jié)點(diǎn)，將這個(gè)申請(qǐng)結(jié)點(diǎn)插進(jìn)去
//按位置插入 插入的第幾個(gè)有效結(jié)點(diǎn)
bool Insert_Pos(PList plist, int pos, ElemType val)
{
assert(plist != NULL);
if(pos<1||pos>plist->size+1)
return false;
Node* newnode = BuyNode(val, NULL);
assert(newnode != NULL);
Node* p = plist->head;
for (int i = 0; i < pos - 1; i++)
{
p = p->next;
}
newnode->next = p->next;
p->next = newnode;
plist->cursize++;
return true;
}?3.11?在指定結(jié)點(diǎn)之前插入數(shù)據(jù)元素
思想：
??
注意事項(xiàng)：
?3.12? 在指定結(jié)點(diǎn)之后插入數(shù)據(jù)元素
思想：
??
注意事項(xiàng)：
3.13 頭刪數(shù)據(jù)
思想：
? ? ? ?只需要?jiǎng)h除第一個(gè)有效結(jié)點(diǎn)，貫穿即可！
注意事項(xiàng)：
? ? ? 頭刪數(shù)據(jù)前需要進(jìn)行判空，或者直接對(duì)空鏈表單獨(dú)判斷
//10.頭刪
bool Pop_Front(PList plist)
{
assert(plist != NULL);
if (plist->cursize == 0) //空鏈表需要進(jìn)行單獨(dú)判斷，防止出現(xiàn)指針崩潰
return false;
//1.結(jié)點(diǎn)指針保存待刪除結(jié)點(diǎn)的地址
Node* p = plist->head->next;
//2.進(jìn)行貫穿
plist->head->next = p->next;
//3.釋放待刪結(jié)點(diǎn)
free(p);
plist->cursize--;
return true;
}?3.14 尾刪數(shù)據(jù)
思想：
??
注意事項(xiàng)：
3.15 任意位置刪除數(shù)據(jù)?
思想：
??
注意事項(xiàng)：
?3.16? 刪除指定結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
3.17? 刪除指定結(jié)點(diǎn)的后繼結(jié)點(diǎn)
3.18? 刪除與val值相等的所有數(shù)據(jù)結(jié)點(diǎn)
?3.19?打印鏈表元素
思想：
? ? ?打印鏈表元素有兩種，初始位置從頭結(jié)點(diǎn)開始或者從第一個(gè)有效結(jié)點(diǎn)開始，選其一。文章來源地址http://www.zghlxwxcb.cn/news/detail-826357.html
//15.打印鏈表中的數(shù)據(jù)元素
//第一種
void PrintList(const PList plist)
{
assert(plist != NULL);
for (Node* p = plist->head; p->next != NULL; p = p->next)
{
printf("%5d", p->next->data);
}
}
//第二種
void PrintList(const PList plist)
{
assert(plist != NULL);
for (Node* p = plist->head->next; p!= NULL; p = p->next)
{
printf("%5d", p->data);
}
}3.20?.返回與val值相等的結(jié)點(diǎn) ?
3.21?返回與val值相等的前驅(qū)結(jié)點(diǎn) ?
3.22?返回與val值相等的后繼結(jié)點(diǎn) ?
3.23? 返回pos位置的結(jié)點(diǎn) ?
3.24? 返回pos位置的前驅(qū)結(jié)點(diǎn) ?
3.25? 返回pos位置的后繼結(jié)點(diǎn) ?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)三：線性表之單鏈表(帶頭結(jié)點(diǎn)單向)的設(shè)計(jì)與實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]鏈表之單鏈表（詳解）](https://imgs.yssmx.com/Uploads/2024/01/400368-1.png)
