前言

數(shù)據(jù)結(jié)構(gòu)入門 — 單鏈表詳解*
博客主頁鏈接：https://blog.csdn.net/m0_74014525
關(guān)注博主，后期持續(xù)更新系列文章
文章末尾有源碼
*****感謝觀看，希望對你有所幫助*****

---

系列文章

第一篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_單鏈表
第二篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表
第三篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_循環(huán)鏈表

---

---

一、鏈表

1. 鏈表是什么

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點組成，在每個節(jié)點中存儲數(shù)據(jù)和指向下一個節(jié)點的指針。每個節(jié)點只包含指向下一個節(jié)點的指針，不像數(shù)組那樣有預(yù)定義的大小。鏈表可以動態(tài)地增長和縮小，并且非常靈活，可以在任何位置插入或刪除節(jié)點。鏈表主要分為單向鏈表、雙向鏈表和循環(huán)鏈表等不同類型。

2. 優(yōu)缺點

鏈表的優(yōu)點：

1. 靈活性：由于鏈表中每個節(jié)點都有指向下一個節(jié)點的指針，因此鏈表可以在任何位置添加或移除元素，使得鏈表非常靈活。
2. 動態(tài)性：由于鏈表的大小不是固定的，當需要增加或刪除元素時，內(nèi)存中不需要重新分配空間，而是在鏈表中增加或刪除一個結(jié)點。
3. 無需占用連續(xù)的內(nèi)存空間：相較于數(shù)組等數(shù)據(jù)結(jié)構(gòu)，鏈表的每個元素之間并沒有關(guān)聯(lián)性，每個節(jié)點可以在內(nèi)存中的任意位置，不需要占用連續(xù)的內(nèi)存空間。

鏈表的缺點：

1. 沒有隨機訪問的能力：鏈表中的元素之間沒有關(guān)聯(lián)性，無法像數(shù)組那樣通過下標直接訪問某個元素，需要從頭開始遍歷整個鏈表才能找到需要的元素，這會導(dǎo)致鏈表的查找效率比數(shù)組低。
2. 內(nèi)存空間的額外開銷：由于需要在每個節(jié)點中存儲指向下一個節(jié)點的指針，鏈表內(nèi)每個元素需要占用比其存儲內(nèi)容更多的內(nèi)存空間，這會導(dǎo)致鏈表沒有數(shù)組那么節(jié)省內(nèi)存。
3. 不支持常量時間內(nèi)的隨機訪問：鏈表只能在頭尾節(jié)點進行快速的插入和刪除操作，但在其他位置插入和刪除節(jié)點較為困難，需要先遍歷找到要操作的位置，這會導(dǎo)致鏈表操作的時間復(fù)雜度較高。

---

二、概念及結(jié)構(gòu)

1. 概念

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的。

2. 結(jié)構(gòu)

在現(xiàn)實的數(shù)據(jù)結(jié)構(gòu)中，鏈表的結(jié)構(gòu)

注意:

1. 從上圖可看出，鏈式結(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)
2. 現(xiàn)實中的結(jié)點一般都是從堆上申請出來的
3. 從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續(xù)，也可能不連續(xù)

---

三、 鏈表的分類

1. 鏈表結(jié)構(gòu)類型

鏈表可以分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。

類型	介紹
單鏈表	節(jié)點只包含一個指向后繼節(jié)點的指針，每個節(jié)點只知道下一個節(jié)點的位置。
雙向鏈表	節(jié)點包含一個指向前驅(qū)節(jié)點和一個指向后繼節(jié)點的指針，每個節(jié)點都知道前面和后面的節(jié)點位置。
循環(huán)鏈表	鏈表的最后一個節(jié)點指向第一個節(jié)點，形成一個環(huán)形結(jié)構(gòu)。

除了這三種基本類型，還有一些派生的鏈表結(jié)構(gòu)，如帶有頭節(jié)點的鏈表、帶有尾指針的鏈表、帶有哨兵節(jié)點的鏈表等。如下圖有8種鏈表結(jié)構(gòu)
1. 單向或者雙向

2. 帶頭或者不帶頭（哨兵位）

3. 循環(huán)或者不循環(huán)

2. 常用的兩種鏈表結(jié)構(gòu)

無頭單向非循環(huán)鏈表：

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都
是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶
來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

---

四、單鏈表接口實現(xiàn)（代碼演示）

無頭+單向+非循環(huán)鏈表增刪查改實現(xiàn)

1. 動態(tài)申請一個結(jié)點

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuySListNode");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

2. 單鏈表打印

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while(cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

3. 單鏈表增刪查改

頭插：

//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾插：

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{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;}
}

頭刪：

//頭刪
void SLTPopFront(SLTNode** pphead)
{//空assert(pphead);assert(*pphead);//非空SLTNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;}

尾刪：

//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);assert(pphead);//一個節(jié)點if((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* tailPrev = NULL;while(tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tail = NULL;tailPrev->next = NULL;}
}

查找：

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos之前插入x：

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}

在pos以后插入x：

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}

刪除pos位置：

// 刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* tail = *pphead;while (tail->next != pos){tail = tail->next;}tail->next = pos->next;free(pos);pos = NULL;}
}

刪除pos的后一個位置：

// 刪除pos的后一個位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;pos->next = posNext->next;free(posNext);posNext = NULL;}

4. 單鏈表銷毀

void Destory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* del = cur->next;free(cur);cur = del;}* pphead == NULL;
}

---

五、所有文件代碼

1. Gitee鏈接

***查看所有代碼***
點擊右邊藍色文字 DuckBro Gitee 代碼倉庫

---

總結(jié)

單鏈表的重點包括：

1. 定義：單鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。
2. 插入操作：單鏈表的插入操作需要先找到要插入位置的前一個節(jié)點，然后將新節(jié)點插入到其后。
3. 刪除操作：單鏈表的刪除操作需要先找到要刪除的節(jié)點的前一個節(jié)點，然后將其指針指向下一個節(jié)點即可。
4. 遍歷操作：單鏈表需要從頭節(jié)點開始依次遍歷各個節(jié)點，獲取其中存儲的數(shù)據(jù)。
5. 鏈表反轉(zhuǎn)：單鏈表的反轉(zhuǎn)操作是將鏈表中的節(jié)點從后往前連接，最后將原來的頭節(jié)點變?yōu)槲补?jié)點。
6. 快慢指針：快慢指針是單鏈表中常用的技巧，可以用于查找鏈表中的中間節(jié)點、判斷是否有環(huán)等操作。
7. 環(huán)形鏈表：有些單鏈表可能存在環(huán)形結(jié)構(gòu)，即某個節(jié)點的指針指向之前的某個節(jié)點，使用快慢指針可以判斷鏈表是否為環(huán)形。
8. 鏈表排序：單鏈表可以使用排序算法進行排序，如冒泡排序、快速排序等。
9. 鏈表的應(yīng)用：單鏈表廣泛應(yīng)用于各種數(shù)據(jù)結(jié)構(gòu)和算法中，如哈希表、圖等。

---

如這篇博客對大家有幫助的話，希望 三連 支持一下 ！！！ 如果有錯誤感謝大佬的斧正 如有 其他見解發(fā)到評論區(qū)，一起學(xué)習(xí) 一起進步。