1 鏈表的概念及結(jié)構(gòu)

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

?從以上圖片可以看出：

1.鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但在物理上不一定是連續(xù)的。

2.現(xiàn)實(shí)中的節(jié)點(diǎn)一般是在堆上申請(qǐng)出來的。

3.從堆上申請(qǐng)的空間，是按照一定的策略來分配的，兩次申請(qǐng)的空間可能連續(xù)，可能不連續(xù)。

2 鏈表的分類

實(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í)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。

3 單向無頭鏈表的實(shí)現(xiàn)

在頭文件中包含一些函數(shù)的聲明。

因?yàn)槊總€(gè)節(jié)點(diǎn)都是一個(gè)結(jié)構(gòu)體，所以每個(gè)節(jié)點(diǎn)都要存放一個(gè)結(jié)構(gòu)體的指針，指向下一個(gè)節(jié)點(diǎn)。

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuyListBNode(SLTDataType x);void PrintSList(SLTNode* phead);void SLTPushBcak(SLTNode** pphead,SLTDataType x);//尾插void SLTPushFront(SLTNode** pphead, SLTDataType x);//頭插void SLTPopback(SLTNode** pphead);//尾刪void SLTPopFront(SLTNode** pphead,SLTDataType x);//頭刪void SLTFind(SLTNode* pphead,SLTDataType x);//查找//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之后插入x
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos的后一個(gè)位置
void SLTEraseAfter(SLTNode* pos);

3.1打印鏈表

打印鏈表首先要遍歷鏈表，那么循環(huán)的條件就是走到空。所以我們創(chuàng)建一個(gè)臨時(shí)變量cur代替頭節(jié)點(diǎn)用來遍歷，這樣就可以不用動(dòng)頭節(jié)點(diǎn)，打印就是將節(jié)點(diǎn)中的數(shù)據(jù)打印出來，所以先將各個(gè)節(jié)點(diǎn)的數(shù)據(jù)打印出來，再指向下一個(gè)節(jié)點(diǎn)，需要注意的是next就是下一個(gè)節(jié)點(diǎn)的地址，所以將cur->next賦給cur就可以拿到下一個(gè)節(jié)點(diǎn)的地址了，拿到地址就可以繼續(xù)訪問下一個(gè)節(jié)點(diǎn)了。

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

3.2創(chuàng)建節(jié)點(diǎn)

這里malloc一個(gè)節(jié)點(diǎn)出來就行了，然后判斷是否malloc成功，將需要的數(shù)據(jù)存進(jìn)data中就行了，然后將next置為NULL，然后返回這個(gè)節(jié)點(diǎn)。

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

3.3尾插節(jié)點(diǎn)

這個(gè)函數(shù)的第一個(gè)參數(shù)是一個(gè)二級(jí)指針，目的是為了修改結(jié)構(gòu)體，尾插節(jié)點(diǎn)首先需要?jiǎng)?chuàng)建一個(gè)節(jié)點(diǎn)，然后·判斷一下當(dāng)前鏈表是否為空，如果為空則將這個(gè)節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)，所以解引用這個(gè)二級(jí)指針，拿到一級(jí)指針的地址，就可以修改了。如果不為空，則創(chuàng)建一個(gè)臨時(shí)變量來保存頭節(jié)點(diǎn)的地址，然后使用這個(gè)變量來遍歷鏈表找到尾節(jié)點(diǎn)，循環(huán)的結(jié)束條件就是tail的next為空，因?yàn)槲补?jié)點(diǎn)的next是NULL，循環(huán)結(jié)束之后tail就走到了尾節(jié)點(diǎn)的位置，然后將新節(jié)點(diǎn)賦給tail的next即可。

void SLTPushBcak(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyListBNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

3.4頭插節(jié)點(diǎn)

尾插節(jié)點(diǎn)還是需要?jiǎng)?chuàng)建一個(gè)節(jié)點(diǎn)，然后將這個(gè)節(jié)點(diǎn)的next指向這個(gè)頭節(jié)點(diǎn)，但是頭插之后頭節(jié)點(diǎn)就是新插入的這個(gè)節(jié)點(diǎn)，所以需要使用二級(jí)指針，最后將新節(jié)點(diǎn)newnode賦給*pphead，這樣頭節(jié)點(diǎn)就更新了。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyListBNode(x);newnode->next = *pphead;*pphead = newnode;
}

3.4尾刪節(jié)點(diǎn)

尾刪需要分很多種情況：

1.沒有節(jié)點(diǎn)，這種情況就直接暴力檢查，沒有節(jié)點(diǎn)是刪除不了的，直接assert即可。

2.一個(gè)節(jié)點(diǎn)，如果是一個(gè)節(jié)點(diǎn)的話，這個(gè)節(jié)點(diǎn)的next一定是NULL，所以使用if判斷*pphead->next是否為NULL，如果是的話直接free掉這個(gè)節(jié)點(diǎn)然后置為空就行了。

3.如果是多個(gè)節(jié)點(diǎn)的話創(chuàng)建一個(gè)臨時(shí)變量來遍歷鏈表找到尾，需要注意的是，這個(gè)循環(huán)的結(jié)束條件是tail->next->next為空。下面這段代碼就是錯(cuò)誤的，因?yàn)閒ree（tail）的本質(zhì)是將tail指向的節(jié)點(diǎn)free，再將tail置為空相當(dāng)于給tail賦值0x00000000，局部變量出了作用域就銷毀了，但是前一個(gè)節(jié)點(diǎn)還是野指針，next雖然還是指向這個(gè)節(jié)點(diǎn)，但是這個(gè)節(jié)點(diǎn)已經(jīng)free了。所以解決的方法就是找到tail的前一個(gè)節(jié)點(diǎn)，然后free掉tail->next，再置空。

正確的方法：?

void SLTPopback(SLTNode** pphead)
{assert(*pphead);//一個(gè)節(jié)點(diǎn)if ((*pphead)->next = NULL){free(*pphead);*pphead = NULL;}else//多個(gè)節(jié)點(diǎn){SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

?3.5頭刪節(jié)點(diǎn)

頭刪也需要用到二級(jí)指針，然后暴力檢查鏈表是否為空，不為空則創(chuàng)建一個(gè)變量newnode來保存頭節(jié)點(diǎn)的next，然后free掉頭節(jié)點(diǎn)，再將newnode賦給*pphead。

void SLTPopFront(SLTNode** pphead)
{assert(pphead);SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

3.6查找節(jié)點(diǎn)

這個(gè)函數(shù)很簡單，找到data就行，然后返回節(jié)點(diǎn)。

SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{SLTNode* cur = pphead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

?3.6在pos位置之前插入節(jié)點(diǎn)

pos的位置也需要分情況：

1.暴力檢查

2.如果是頭插，直接調(diào)用頭插函數(shù)。

3.正常情況，創(chuàng)建一個(gè)結(jié)構(gòu)體變量來遍歷鏈表尋找pos節(jié)點(diǎn)，但是循環(huán)的結(jié)束條件設(shè)置成pre->next=pos最合適，因?yàn)槲覀冃枰４鎝os的前一個(gè)節(jié)點(diǎn)，所以循環(huán)結(jié)束后pre就是pos的前一個(gè)節(jié)點(diǎn)，此時(shí)創(chuàng)建一個(gè)需要插入的節(jié)點(diǎn)newnode，將pre的next指向newnode，再將newnode的next指向pos，就完成鏈接了。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (*pphead == pos){SLTPopFront(pphead,x);}else{SLTNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}SLTNode* newnode = BuyListBNode(x);pre->next = newnode;newnode->next = pos; }
}

3.7在pos位置之后插入節(jié)點(diǎn)

首先暴力檢查，再創(chuàng)建一個(gè)新節(jié)點(diǎn)newnode，插入需要注意的是以下這種寫法是錯(cuò)誤的，因?yàn)楫?dāng)我們將pos的next指向newnode的時(shí)候，就與后面的節(jié)點(diǎn)完全斷開了，然后newnode的next又指向pos的next相當(dāng)于形成了一個(gè)死循環(huán)。正確的方法應(yīng)該是pos的next指向newnode的next，相當(dāng)于先將newnode的next指向pos的后一個(gè)節(jié)點(diǎn)形成newnode的尾部鏈接，再將pos的next指向newnode完成newnode的頭部鏈接。

?

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyListBNode(x);newnode->next = pos->next;pos->next = newnode;}

3.8刪除pos位置的節(jié)點(diǎn)

首先暴力檢查，再判斷pos是不是頭刪，正常刪除就是創(chuàng)建一個(gè)變量遍歷鏈表，pos的next為空作為循環(huán)的結(jié)束條件，循環(huán)結(jié)束之后pre就是pos的前一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候?qū)re的next指向pos的next也就是pos的下一個(gè)節(jié)點(diǎn)就行了，然后frre掉pos，這時(shí)候就不需要置空了。

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

3.9刪除pos位置之后的節(jié)點(diǎn)?

首先暴力檢查，然后再檢查是否為尾節(jié)點(diǎn)。創(chuàng)建一個(gè)變量posNext保存pos的下一個(gè)節(jié)點(diǎn)，然后即將pos的下一個(gè)節(jié)點(diǎn)指向pos的下下個(gè)節(jié)點(diǎn)即可。然后free掉posNext。

void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//檢查是否是尾節(jié)點(diǎn)SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);
}

---

今天的分享到這里就結(jié)束啦！謝謝老鐵們的閱讀，讓我們下期再見。