一.鏈表的概念以及結(jié)構(gòu)

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

鏈表的結(jié)構(gòu)與火車是類似的，一節(jié)一節(jié)的，數(shù)據(jù)就像乘客一樣在車廂中一樣。

與順序表不同的是，鏈表里的每節(jié)"車廂"都是獨(dú)立申請(qǐng)的空間，我們將這樣的空間稱為節(jié)點(diǎn)或者結(jié)點(diǎn)

?既然鏈表是一節(jié)一節(jié)的結(jié)點(diǎn)構(gòu)成的，那么這樣的結(jié)點(diǎn)是怎么連接的呢？

鏈表中的節(jié)點(diǎn)一般是通過結(jié)構(gòu)體來實(shí)現(xiàn)的，結(jié)構(gòu)體中的存儲(chǔ)著數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的地址，這樣我們就可以訪問下一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)了。

節(jié)點(diǎn)：

typedef struct SListNode
{SLTDataType val;struct SListNode* next;
}SLTNode;

為了使用方便我們可以對(duì)其重命名。

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

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; //節(jié)點(diǎn)數(shù)據(jù)struct SListNode* next; //指針保存下?個(gè)節(jié)點(diǎn)的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//頭部插?刪除/尾部插?刪除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插?數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插?數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos);
//銷毀鏈表
void SListDesTroy(SLTNode** pphead);

首先我們來思考如何打印數(shù)據(jù)呢？

void SLTPrint(SLTNode* phead);

這個(gè)參數(shù)是指向第一個(gè)頭節(jié)點(diǎn)的指針，為什么要使用指針呢？

通過指針我們可以訪問這個(gè)結(jié)構(gòu)體中的元素，如果我們不使用指針，形參是實(shí)參的一份臨時(shí)拷貝，如果數(shù)據(jù)過大，這樣會(huì)很浪費(fèi)空間（我們這里存儲(chǔ)的數(shù)據(jù)是整形，為了泛用性，我們還是要使用一級(jí)指針），直接使用會(huì)降低程序性能。

phead->data就可以訪問到數(shù)據(jù)了，那么下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)呢？

這時(shí)候就會(huì)用到我們?cè)诮Y(jié)構(gòu)體中存儲(chǔ)的指針了，這個(gè)指針指向下一個(gè)結(jié)構(gòu)體，所以再通過下一個(gè)結(jié)構(gòu)體我們就可以訪問下一個(gè)結(jié)構(gòu)體的數(shù)據(jù)，同理，下下個(gè)結(jié)構(gòu)體的指針同理。

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

通常習(xí)慣上，我們是不會(huì)改變直接傳過來的參數(shù)的，所以我們要使用的話，就再使用一個(gè)變量來進(jìn)行接收。

這里pcur不為NULL時(shí)，代表我們的指針并沒有走到結(jié)構(gòu)體的末尾，我們就可以以它作為限制條件，每經(jīng)過一個(gè)節(jié)點(diǎn)，就打印一次數(shù)據(jù)，直到遇到空指針停止。?

然后就是要完成指定位置之前插入數(shù)據(jù)了。

假設(shè)有一個(gè)鏈表1->>2->>3->>5->>NULL.

我們要在數(shù)據(jù)5的前面插入4.可是在插入之前，我們要找到數(shù)據(jù)五的位置才能插入。

如何查找元素呢？

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

第一個(gè)參數(shù)是指向第一個(gè)節(jié)點(diǎn)的指針，第二個(gè)是要尋找的數(shù)據(jù)，雖然這里可能會(huì)存在相同的數(shù)字，但是這只是我們練習(xí)的場(chǎng)景，假設(shè)我們要存儲(chǔ)人的身份信息，這是不可能存在相同的人的，所以我們這里假設(shè)數(shù)據(jù)不相同。

最后返回這個(gè)節(jié)點(diǎn)的地址。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* pcur = phead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
};

和打印數(shù)據(jù)相同。我們只需要遍歷整個(gè)數(shù)組即可，如果找到就返回這個(gè)節(jié)點(diǎn)的地址，否則就返回空。

接著我們?cè)賮硗瓿芍付ㄎ恢貌迦霐?shù)據(jù)。

即使我們找打這個(gè)節(jié)點(diǎn)的地址，我們要在它之前插入數(shù)據(jù)，也就是再創(chuàng)建一個(gè)節(jié)點(diǎn)，然后把這個(gè)節(jié)點(diǎn)的next指針指向找的節(jié)點(diǎn)，這樣我們就在指定節(jié)點(diǎn)前面插入了數(shù)據(jù)。

但是我們新建的這個(gè)節(jié)點(diǎn)是沒有被節(jié)點(diǎn)指向的，所以我們還要讓前一個(gè)節(jié)點(diǎn)指向新的節(jié)點(diǎn)。

這個(gè)SLTBuyNode是創(chuàng)建新節(jié)點(diǎn)函數(shù)，我們?cè)诓迦霐?shù)據(jù)時(shí)，會(huì)頻繁用到這個(gè)代碼，如果重復(fù)的寫，就太浪費(fèi)時(shí)間了，所以我們單獨(dú)封裝一個(gè)函數(shù)來完成這個(gè)功能。

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

		SLTNode* pcur = *pphead;while (pcur->next != pos) {pcur = pcur->next;}pcur->next = SLTBuyNode(x);pcur->next->next = pos;

可是這樣寫就完了嗎？

如果我們要在鏈表的第一個(gè)節(jié)點(diǎn)之前插入數(shù)據(jù)，我們會(huì)發(fā)現(xiàn)這個(gè)代碼循環(huán)是根本沒有進(jìn)入的，并且會(huì)訪問NULL地址，這是非法的。

所以為了防止這樣的問題，我們還需要額外區(qū)分頭插的情況。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(*pphead);if (*pphead == pos) {*pphead = SLTBuyNode(x);(*pphead)->next = pos;}else {SLTNode* pcur = *pphead;while (pcur->next != pos) {pcur = pcur->next;}pcur->next = SLTBuyNode(x);pcur->next->next = pos;}
};

?然后我們來思考，為什么這里要使用二級(jí)指針，我們使用指針的目的是為了在函數(shù)中改變指針?biāo)赶虻淖兞康闹?#xff0c;這里就是傳值和傳址的區(qū)別了，我們?cè)陬^插的過程中指向頭節(jié)點(diǎn)的指針，是會(huì)改變的，如果我們傳一級(jí)指針，是改變不了這個(gè)指針的，所以我們要使用二級(jí)指針。

然后就是刪除數(shù)據(jù)函數(shù)

void SLTErase(SLTNode** pphead, SLTNode* pos);

這里與插入函數(shù)一樣，是需要考慮頭刪的。

void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;if (pos == *pphead) {*pphead = pos->next;free(pos);}else {while (pcur->next != pos) {pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
};

刪除指定節(jié)點(diǎn)，只需要我們將前一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)就行了，然后再釋放指定節(jié)點(diǎn)即可?。

而頭刪就是釋放頭節(jié)點(diǎn)，然后將頭指針指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)既可以。

為了方便，頭插頭刪位插尾刪，我們都使用前面兩個(gè)函數(shù)來進(jìn)行完成，這樣更加方便。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead == NULL) {*pphead = SLTBuyNode(x);}else {SLTInsert(pphead,NULL,x);}
}

在尾插時(shí)，如果鏈表為空，我們就直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)即可，否則我們就只需要在NULL前面插入一個(gè)節(jié)點(diǎn)即可，因?yàn)樽詈笠粋€(gè)節(jié)點(diǎn)的next指針指向的是空。

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead == NULL) {*pphead = SLTBuyNode(x);}else {SLTInsert(pphead, *pphead, x);}
};

頭插同理，如果鏈表為空直接創(chuàng)建新的鏈表即可，否則就是在頭節(jié)點(diǎn)之前插入即可，而且頭節(jié)點(diǎn)直接作為參數(shù)給我們使用了，所以我們就不需要再查找了.?

void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur->next != NULL) {pcur = pcur->next;}SLTErase(pphead,pcur);
};

尾刪就需要我們遍歷鏈表，找到最后一個(gè)鏈表的指針?，這樣再刪除即可。鏈表為空就不能刪了，所以我們要斷言一下。

void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTErase(pphead,*pphead);
};

頭刪更簡(jiǎn)單，不需要遍歷，直接調(diào)用刪除函數(shù)即可。

//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* next = SLTBuyNode(x);next->next = pos->next;pos->next = next;
};
//刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos) {assert(pos);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;
};

?這里是同理，要插入就直接創(chuàng)建新鏈表然后插入即可,刪除也是同理，這里是需要判斷pos是否為空的，因?yàn)槿绻麤]有找到find函數(shù)就會(huì)返回空。

刪除鏈表

void SListDesTroy(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
};

就需要遍歷整個(gè)鏈表然后依次釋放，最后為了防止野指針，我們還需要將*pphead置為NULL。?

三.鏈表?

鏈表的種類有很多種。

任意兩兩組合就有2 * 2 * 2 = 8種組合

這個(gè)帶頭和不帶頭后面雙鏈表再講解。

我們通常所說的單鏈表是不帶頭單向不循環(huán)鏈表。

單向就是通過一個(gè)只能訪問下一個(gè)節(jié)點(diǎn)不能訪問上一個(gè)節(jié)點(diǎn)，否則就是雙向。

循環(huán)就是鏈表圍成一個(gè)圈，鏈表的最后一個(gè)節(jié)點(diǎn)next指向頭節(jié)點(diǎn)了，而不是NULL.

1. ??頭單向?循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，?般不會(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)反?簡(jiǎn)單了，后?我們代碼實(shí)現(xiàn)了就知道了。

?