數(shù)據(jù)結(jié)構(gòu)—-鏈表詳解

目錄

鏈表的定義

前面我們介紹的順序表，在邏輯結(jié)構(gòu)和物理結(jié)構(gòu)上都是線性、連續(xù)的關(guān)系，那么我們?cè)谄驳臅r(shí)候也提到了是否有一種順序表，無(wú)需在物理結(jié)構(gòu)上連續(xù)，從而達(dá)到更好存取的目的呢？今天它來(lái)了。

鏈表（LinkList）屬于線性表的一種，以下是百度百科關(guān)于鏈表的定義：

總結(jié)下來(lái)，我們可以看出：

在結(jié)構(gòu)上，鏈表并不是像順序表那樣底層結(jié)構(gòu)是數(shù)組，而是包含兩個(gè)區(qū)域：數(shù)據(jù)域、指針域。我們可以類比成火車，火車每一節(jié)車廂實(shí)際上是獨(dú)立的，也就好比數(shù)據(jù)域，存儲(chǔ)著各自的數(shù)據(jù)；但每一節(jié)車廂之間都會(huì)由一條鏈連接在一起，從而形成整個(gè)火車，鏈也就好比指針域，起到連接該車廂和指向下一車廂的作用。而實(shí)際上這樣的存儲(chǔ)結(jié)構(gòu)也就是為什么鏈表的物理結(jié)構(gòu)可以不連續(xù)，而邏輯結(jié)構(gòu)依舊是連續(xù)的。

這樣的好處就是當(dāng)我們需要對(duì)指定元素進(jìn)行移動(dòng)、替換、存取等操作的時(shí)候，我們可以一步到位，無(wú)需挪動(dòng)數(shù)據(jù)，無(wú)需擴(kuò)容，不會(huì)造成空間上的浪費(fèi)——好比你火車更換車廂，總不可能讓整個(gè)火車都為你而改動(dòng)吧。

所以，如果要用一句話概括鏈表是什么，我們可以說(shuō)：鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，由結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素也就是數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的指針也就是指針域。（叫法：結(jié)點(diǎn)或者節(jié)點(diǎn)都行）

聯(lián)想：指針域的作用

實(shí)際上，在后續(xù)的數(shù)據(jù)結(jié)構(gòu)中，還有很多類型的數(shù)據(jù)結(jié)構(gòu)會(huì)使用到指針域這個(gè)概念，或者可以說(shuō)是結(jié)點(diǎn)的概念。結(jié)點(diǎn)指地是組成數(shù)據(jù)元素的存儲(chǔ)映像，往往指針就是指向結(jié)點(diǎn)的，鑒于它不受物理空間限制的優(yōu)點(diǎn)，往往都會(huì)使用指針和結(jié)點(diǎn)來(lái)更高效率地實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。

鏈表的構(gòu)成

數(shù)據(jù)域（data）：存放實(shí)際數(shù)據(jù)

指針域（next）：存放下一節(jié)點(diǎn)的首地址

結(jié)點(diǎn)：由數(shù)據(jù)域和指針域兩部分信息組成的數(shù)據(jù)元素的存儲(chǔ)映像

鏈表的分類

我們平常使用的最多的就是單鏈表——不帶頭單向不循環(huán)鏈表

既然有不帶頭，那么必然就有帶頭；既然有單向，那么必然就有雙向；既然有不循環(huán)，那么必然就有循環(huán)。

接下來(lái)針對(duì)這三個(gè)方向進(jìn)行介紹。

雙向和單向

單向鏈表：每個(gè)節(jié)點(diǎn)包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。單向鏈表只能從頭節(jié)點(diǎn)開(kāi)始遍歷，無(wú)法從尾節(jié)點(diǎn)向前遍歷。
雙向鏈表：每個(gè)節(jié)點(diǎn)包含一個(gè)指向下一個(gè)節(jié)點(diǎn)和一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針。雙向鏈表可以從頭節(jié)點(diǎn)或尾節(jié)點(diǎn)開(kāi)始遍歷，可以方便地在鏈表中間插入或刪除節(jié)點(diǎn)。（向的描述與指針域的描述是一致的，單向只有一個(gè)指針域，而雙向有兩個(gè)）

可以通俗地理解為，單向?yàn)閱涡械?#xff0c;只能從頭走到尾；雙向?yàn)殡p行道，既可退又可進(jìn)。

帶頭和不帶頭

帶頭鏈表：指第一個(gè)結(jié)點(diǎn)叫做頭結(jié)點(diǎn)，不存儲(chǔ)有效數(shù)據(jù)，只作為指引結(jié)點(diǎn)
不帶頭鏈表：指第一個(gè)結(jié)點(diǎn)不叫做頭結(jié)點(diǎn)，就是第一個(gè)結(jié)點(diǎn)，存儲(chǔ)有效數(shù)據(jù)

注意這里指的帶頭就是帶有頭結(jié)點(diǎn)的意思，頭結(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)，它僅僅用于指向第一個(gè)結(jié)點(diǎn)。優(yōu)點(diǎn)是操作鏈表時(shí)統(tǒng)一處理，不需要特殊處理第一個(gè)節(jié)點(diǎn)，代碼更加簡(jiǎn)潔清晰。缺點(diǎn)是需要額外的頭節(jié)點(diǎn)，占用額外的空間。

循環(huán)和不循環(huán)

循環(huán)鏈表：最后一個(gè)節(jié)點(diǎn)的指針指向第一個(gè)節(jié)點(diǎn)，形成一個(gè)環(huán)狀結(jié)構(gòu)。循環(huán)鏈表可以從任意節(jié)點(diǎn)開(kāi)始遍歷，但需要注意避免出現(xiàn)死循環(huán)的情況。
不循環(huán)鏈表：最后一個(gè)節(jié)點(diǎn)的指針直接指向空，僅僅作為線性結(jié)構(gòu)。

雖然鏈表種類之多，例如還有帶有尾結(jié)點(diǎn)的鏈表等等，但在實(shí)際應(yīng)用中只有兩種：**單鏈表（不帶頭單向不循環(huán)鏈表）和雙向鏈表（帶頭雙向循環(huán)鏈表）**使用得最多，因?yàn)樗鼈儍蓚€(gè)的特性加起來(lái)即為所有特性，而其他類型的鏈表也就不難創(chuàng)建了。

鏈表的命名

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next; 
}SLTNode

單鏈表

SLTDataType、ElemType、LinklistType等等（根據(jù)自己的偏好設(shè)定），以下都命名為SLTDataType

數(shù)據(jù)域

SLTDataType data; //保存結(jié)點(diǎn)數(shù)據(jù)

指針域（*

struct SListNode* next;//保存下一結(jié)點(diǎn)地址

操作

SLTPushBack//針對(duì)操作的命名一般在操作前綴添加SLT等代表其為鏈表的大寫字母縮寫

基本操作的實(shí)現(xiàn)

有關(guān)鏈表的操作，下方是一些舉例

//鏈表的頭插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);//鏈表的頭刪、尾刪
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SListDesTroy(SLTNode** pphead);
//打印
void SLTPrint(SLTNode* phead);

接下來(lái)針對(duì)上述操作進(jìn)行詳細(xì)介紹。

初始化

即構(gòu)造一個(gè)空鏈表

void SlistTest01() {//一般不會(huì)這樣去創(chuàng)建鏈表，這里只是為了給大家展示鏈表的打印SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;
//當(dāng)我們定義好了數(shù)據(jù)域之后，指針域應(yīng)該如何定義呢？node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
//像這樣，讓指針域指向該節(jié)點(diǎn)的下一節(jié)點(diǎn)，達(dá)到鏈接的目的

SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {//如果開(kāi)辟失敗的情況perror("malloc fail!");exit(1);}newnode->data = x;//開(kāi)辟數(shù)據(jù)域newnode->next = NULL;//開(kāi)辟指針域return newnode;
}

打印

在接下來(lái)承擔(dān)顯示的作用，將鏈表的結(jié)構(gòu)可視化

void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;//使用next指針指向下一節(jié)點(diǎn)}printf("NULL\n");
}

取值

與順序表的取值不一樣，因?yàn)殒湵砦锢斫Y(jié)構(gòu)是不連續(xù)的，所以在鏈表中進(jìn)行訪問(wèn)的時(shí)候不能直接隨機(jī)訪問(wèn)，只能從首元素出發(fā)遍歷進(jìn)行訪問(wèn)。

Status SLTGet(LinkList L, int i, ElemType& e)//獲取線性表L中的耨個(gè)數(shù)據(jù)元素的內(nèi)容，通過(guò)變量e返回
{ p = L->next;                    //初始化，p指向首元結(jié)點(diǎn)，j = 1;                          //初始化，j為計(jì)數(shù)器while (p&&j < i)                //向后掃描，直到p指向的第i個(gè)元素或p為空{p = p->next;                //p指向下一個(gè)結(jié)點(diǎn)++j;}if (!p || j > i)                //第i個(gè)元素不存在，拋出異常return NULL;   e = p->data;                    //取第i個(gè)元素return OK;
}

查找

查找操作同順序表類似，都是哦才能夠首元結(jié)點(diǎn)開(kāi)始，依次將元素與給定值進(jìn)行比較。

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍歷鏈表SLTNode* pcur = *pphead;while (pcur) //等價(jià)于pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//沒(méi)有找到return NULL;
}

插入

插入分為尾插、頭插、指定位置插入，而指定位置插入又分為指定位置之前和之后。

尾插

//尾插
void SLTPushBack(SLTNode** pphead/*為什么是**二級(jí)指針？因?yàn)?pphead這個(gè)指針在傳參時(shí)實(shí)際上還是傳值而不是傳地址，需要傳這個(gè)指針的地址也就是使用二級(jí)指針*/, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//鏈表為空，新節(jié)點(diǎn)作為pheadif (*pphead == NULL) {*pphead = newnode;return;}//鏈表不為空，找尾節(jié)點(diǎn)SLTNode* ptail = *pphead;while (ptail->next)//并非ptial不能為空，而是ptail->next不能指向空{ptail = ptail->next;}//ptail就是尾節(jié)點(diǎn)ptail->next = newnode;
}

頭插

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

指定位置插入

之前

//在指定位置之前插入數(shù)據(jù)
//關(guān)鍵：找到前驅(qū)節(jié)點(diǎn)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上鏈表不能為空，如果鏈表都空了，必然找不到前驅(qū)節(jié)點(diǎn)assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos剛好是頭結(jié)點(diǎn)if (pos == *pphead) {//頭插SLTPushFront(pphead, x);return;}//pos不是頭結(jié)點(diǎn)的情況（如果不分情況討論，那么prev就永遠(yuǎn)找不到pos）SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}

之后

//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);//錯(cuò)誤操作：（順序錯(cuò)誤，導(dǎo)致pos->next不再指向下一節(jié)點(diǎn)//pos->next=newnode //newnode->next=pos->next//正確操作：newnode->next = pos->next;pos->next = newnode;
}

刪除

刪除又分為尾刪、頭刪、指定結(jié)點(diǎn)刪除以及指定位置后續(xù)結(jié)點(diǎn)刪除

尾刪

//尾刪
void SLTPopBack(SLTNode** pphead) {assert(pphead);//第一個(gè)節(jié)點(diǎn)不能為空//鏈表不能為空assert(*pphead);//鏈表不為空if ((*pphead)->next == NULL)//如果只有一個(gè)節(jié)點(diǎn) {free(*pphead);//直接釋放*pphead = NULL;//置空return;}//如果有多個(gè)節(jié)點(diǎn)SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next)//不能指向空{prev = ptail;ptail = ptail->next;}prev->next = NULL;//銷毀尾結(jié)點(diǎn)free(ptail);ptail = NULL;
}

頭刪

//頭刪
void SLTPopFront(SLTNode** pphead) {assert(pphead);//鏈表不能為空assert(*pphead);//讓第二個(gè)節(jié)點(diǎn)成為新的頭//把舊的頭結(jié)點(diǎn)釋放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

刪除

刪除又分為刪除指定結(jié)點(diǎn)、刪除指定結(jié)點(diǎn)之后的所有結(jié)點(diǎn)

刪除pos結(jié)點(diǎn)

//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos剛好是頭結(jié)點(diǎn)，沒(méi)有前驅(qū)節(jié)點(diǎn)，執(zhí)行頭刪if (*pphead == pos) {//頭刪SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev以及pos pos->next//先改變指向prev->next = pos->next;//再釋放節(jié)點(diǎn)free(pos);pos = NULL;
}

刪除pos之后的結(jié)點(diǎn)

//刪除pos之后的節(jié)點(diǎn)，也就是pos->next->next
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能為空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;//pos->next = pos->next->next;free(del);del = NULL;
}

銷毀

//銷毀鏈表
//注意鏈表的空間是不連續(xù)的，所以不能一次性銷毀所有元素，只能使用循環(huán)一個(gè)元素一個(gè)元素銷毀
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

…

以上操作都基于單鏈表

部分其他鏈表的代碼實(shí)現(xiàn)

循環(huán)鏈表

在介紹鏈表的分類的時(shí)候，已經(jīng)介紹了循環(huán)鏈表的基本定義，也就是鏈表的最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，這樣就形成了一個(gè)循環(huán)鏈表，如果用圖像來(lái)表示關(guān)系的話，如下：

那么針對(duì)其代碼的實(shí)現(xiàn)，實(shí)際上只需要讓最后一個(gè)結(jié)點(diǎn)的指針域不指向空，而是指向第一個(gè)結(jié)點(diǎn)即可。

//關(guān)鍵代碼
p=B->next->next;
B->next=A->next;
A->next=p;//指向頭結(jié)點(diǎn)

循環(huán)鏈表的作用以及使用場(chǎng)景

1. 約瑟夫問(wèn)題：約瑟夫問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，即有n個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到m的人出列，然后從出列的下一個(gè)人開(kāi)始重新報(bào)數(shù)，直到所有人都出列。循環(huán)鏈表可以很好地模擬這個(gè)問(wèn)題。
2. 環(huán)形隊(duì)列：循環(huán)鏈表可以用來(lái)實(shí)現(xiàn)環(huán)形隊(duì)列，即隊(duì)列的尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)，可以很方便地實(shí)現(xiàn)循環(huán)入隊(duì)和出隊(duì)操作。
3. 循環(huán)播放列表：循環(huán)鏈表可以用來(lái)實(shí)現(xiàn)循環(huán)播放音樂(lè)列表或視頻列表等功能。實(shí)際上循環(huán)這個(gè)概念，在生活中許多部分都有被使用到，而當(dāng)它需要使用代碼實(shí)現(xiàn)的時(shí)候，那么循環(huán)鏈表是較為容易實(shí)現(xiàn)的方案。

雙向鏈表

雙向鏈表的每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，一個(gè)指向后一個(gè)節(jié)點(diǎn)。鑒于這個(gè)特點(diǎn)，它與單向鏈表不同的是，雙向鏈表可以從頭到尾或從尾到頭遍歷鏈表。

在雙向鏈表中，通常有一個(gè)頭節(jié)點(diǎn)和一個(gè)尾節(jié)點(diǎn)，它們分別指向鏈表的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)，可以方便地在頭部或尾部進(jìn)行插入或刪除操作。

雙向鏈表的操作普遍上比單向鏈表簡(jiǎn)單，因?yàn)樗嗔艘粋€(gè)指針域所以操作的靈活性大大提高。

雙向鏈表的作用以及使用場(chǎng)景

1. 需要頻繁在鏈表中間插入或刪除節(jié)點(diǎn)的情況：雙向鏈表可以在O(1)的時(shí)間復(fù)雜度內(nèi)完成插入或刪除操作，因此適合在需要頻繁插入或刪除節(jié)點(diǎn)的場(chǎng)景中使用。
2. 需要雙向遍歷鏈表的情況：雙向鏈表可以方便地從頭到尾或從尾到頭遍歷鏈表，因此適合在需要雙向遍歷鏈表的場(chǎng)景中使用。
3. 需要實(shí)現(xiàn)?；蜿?duì)列的情況：雙向鏈表可以方便地在兩端進(jìn)行插入或刪除操作，因此適合用來(lái)實(shí)現(xiàn)?；蜿?duì)列。
4. 需要實(shí)現(xiàn)LRU緩存淘汰算法的情況：LRU緩存淘汰算法中經(jīng)常需要?jiǎng)h除最近最少使用的節(jié)點(diǎn)，雙向鏈表可以方便地刪除尾節(jié)點(diǎn)，因此適合用來(lái)實(shí)現(xiàn)LRU緩存淘汰算法。

優(yōu)點(diǎn)/缺點(diǎn)（對(duì)比順序表）

優(yōu)點(diǎn)

1.存儲(chǔ)空間充足，對(duì)內(nèi)存利用率高

鏈表無(wú)需像順序表那樣預(yù)先分配空間，只要內(nèi)存空間允許，鏈表中的元素個(gè)數(shù)就沒(méi)有限制，那么這也可以反向說(shuō)明鏈表對(duì)內(nèi)存的利用率較高。

2.插入和刪除的效率高

不像順序表那樣，在進(jìn)行插入和刪除的時(shí)候需要移動(dòng)整個(gè)表，鏈表可以直接對(duì)單個(gè)元素進(jìn)行插入和刪除操作。

3.動(dòng)態(tài)性和靈活性

鏈表的大小可以動(dòng)態(tài)地調(diào)整，可以根據(jù)需要?jiǎng)討B(tài)地插入或刪除元素，不需要提前指定大小。

4.可以實(shí)現(xiàn)高級(jí)數(shù)據(jù)結(jié)構(gòu)

實(shí)際上，在后續(xù)更高階的數(shù)據(jù)結(jié)構(gòu)中，許多結(jié)構(gòu)都是基于鏈表的。鏈表可以實(shí)現(xiàn)棧、隊(duì)列、哈希表等高級(jí)數(shù)據(jù)結(jié)構(gòu)，具有很高的靈活性和擴(kuò)展性。

缺點(diǎn)

1.存儲(chǔ)密度小，單個(gè)結(jié)點(diǎn)有效數(shù)據(jù)占用空間小

我們發(fā)現(xiàn)，鏈表中的一個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域，但是實(shí)際上真正存儲(chǔ)了有效元素的只有數(shù)據(jù)域一部分，那么這就說(shuō)明了其存儲(chǔ)密度小（存儲(chǔ)密度=數(shù)據(jù)元素本身占用的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)占用的存儲(chǔ)量）

2.存取元素的效率低

鏈表不像順序表那樣，是隨機(jī)存取結(jié)構(gòu)，可以隨時(shí)存取該位置上的元素；它屬于順序存取結(jié)構(gòu)，只能通過(guò)遍歷來(lái)實(shí)現(xiàn)存取元素操作。

3.每存一個(gè)數(shù)據(jù)都要開(kāi)辟動(dòng)態(tài)空間，增加了內(nèi)存分配的開(kāi)銷，并可能導(dǎo)致內(nèi)存碎片化。所以說(shuō)，動(dòng)態(tài)化既有利也有弊。