寫在前面

• 很多粉絲經(jīng)常私信問我有關(guān)指針、鏈表相關(guān)的問題，也非常希望我出一篇有關(guān)鏈表的教學(xué)，最近剛好也在整理有關(guān)單鏈表相關(guān)的知識點，便作了此文，為大家講解有關(guān)單鏈表方面的各塊知識點。
• 本文考慮到閱讀者的水平和能力，內(nèi)容有深有淺，總體講解主要是從淺入深循序漸進(jìn)地闡述有關(guān)鏈表相關(guān)的知識

鏈表真的很難嗎？

• 一、前言
• • 1、順序表的缺陷【生活小案例1——盛20粒米飯🍚】
  • 2、優(yōu)化方案
• 二、鏈表的初步認(rèn)知
• • 1、結(jié)構(gòu)的聲明與定義
  • 2、棧區(qū)存放與堆區(qū)存放
  • 3、開始鏈接結(jié)點啦🎉【邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)分】
  • 4、運行起來了，開始玩鏈表
  • • 打印鏈表【生活小案例2——王思聰不需要省錢】
    • 函數(shù)調(diào)用棧幀圖【?庖丁解牛，細(xì)致剖析】
• 三、接口算法實現(xiàn)【是時候表演真正的技術(shù)了🆒】
• • 1、尾插【Hard】
  • • 經(jīng)典錯誤案例分析
    • 二級指針真正改變頭結(jié)點的指向【?????】
  • 2、尾刪【Circuitous】
  • • 經(jīng)典錯誤案例分析
    • 修改方式一：保存ptail的上一個結(jié)點
    • 修改方式二：ptail->next->next
    • 特殊情況修正【單個結(jié)點、二級指針修改、斷言報錯】
  • 3、頭插【Easy】
  • 4、頭刪【Easy】
  • 5、查找
  • 6、在pos位置之后插入結(jié)點
  • • 警惕傳入空指針【?細(xì)致講解斷言assert】
    • 【生活小案例3——請人吃飯要帶錢💴】
  • 7、在pos位置之前插入結(jié)點
  • 8、刪除pos位置之后的結(jié)點
  • • 野指針的危害【生活小案例4——酒店房門的鑰匙🔑】
  • 9、刪除pos位置之前的結(jié)點
  • 10、釋放鏈表
  • • 【生活小案例5——利劍不鋒利🗡】
• 四、整體代碼展示【需要自取】
• 五、有關(guān)二級指針和斷言的小結(jié)【?謹(jǐn)記?】
• 六、OJ題目實訓(xùn)
• • 【LeetCode】21 - 合并兩個有序鏈表
  • 【LeetCode】203 - 移除鏈表元素
  • 【LeetCode】206 - 反轉(zhuǎn)鏈表
  • 【LeetCode】876 - 鏈表的中間結(jié)點
  • 【牛客CM】11 - 鏈表分割
  • 【牛客JZ】22 - 鏈表中倒數(shù)第k個結(jié)點
• 七、總結(jié)與提煉

一、前言

1、順序表的缺陷【生活小案例1——盛20粒米飯🍚】

缺陷1：空間經(jīng)常會不夠，需要擴(kuò)容

• 在上一節(jié)，我們講到了順序表基本函數(shù)結(jié)構(gòu)的算法實現(xiàn)，說到了順序表其實和數(shù)組本質(zhì)差不多，存放的數(shù)據(jù)都是連續(xù)的，但是通過一些頭插、尾插和萬能插入可以看出順序表在有些情況下可能會出現(xiàn)空間不夠，需要擴(kuò)容的操作，而且對于擴(kuò)容機(jī)制，我們上次講到了【本地擴(kuò)容】和【異地擴(kuò)容】，尤其是對于異地擴(kuò)容，需要先釋放掉原先存放的地址，然后再去異地申請一塊地址，這其實是需要一定代價的
• 對于擴(kuò)容的大小來說，一擴(kuò)就是原來的2倍，這些擴(kuò)出來的2倍我們不一定都能使用得完，所以就存在一定的空間浪費。那有同學(xué)說你怎么知道會用不完呢，萬一我用完了呢，其實這你我都不敢肯定自己需要使用多大的空間，只是知道現(xiàn)在的空間不夠了，需要再申請一些空間
• 這其實就是我們吃飯的時候吃了一碗不夠需要再去盛一碗是一樣的，那一碗不夠你可能就會去盛兩碗，但是有點時候兩碗又吃不完（能吃完的請忽略😄），所以這個時候我們就會選擇少盛一點，但是盛少了又不夠吃，如果給你盛1碗20粒米飯這多出來的20粒米你覺得真的夠吃嗎，所以你還會再去盛。所以要盛多少呢？這就好比我們?nèi)ド暾埧臻g，若是申請得太少了，就可能需要頻繁地再去申請，但若是申請得太多了就會用不完，浪費

缺陷2：插入或刪除數(shù)據(jù)時需要挪動大量數(shù)據(jù)，效率低下

• 雖然有了萬能插入，但是我們前面在寫頭插、尾插、頭刪、尾刪的時候花了不少的功夫去解決這些難題，對于頭插，需要將數(shù)據(jù)從后往前一一后移；對于頭刪，需要將數(shù)據(jù)從前往后一一前移，這兩種情況就是插入和刪除中最壞的兩種，時間復(fù)雜度接近O(N)，因此我們可以看出對于順序表它還具有一大缺陷就是對于數(shù)據(jù)的插入和刪除需要挪動大量的數(shù)據(jù)，因為時間復(fù)雜度的過高，導(dǎo)致效率的低下

2、優(yōu)化方案

因為我們就應(yīng)該對這兩種缺陷做一個改進(jìn)

• 對于空間不夠需要擴(kuò)容的情況，我們可以使用動態(tài)申請，就像動態(tài)順序表那樣使用malloc來申請所需要的空間，需要存儲一個數(shù)據(jù)就開一塊空間，在本節(jié)要介紹的【鏈表】中，叫做【結(jié)點】，當(dāng)然有些書上寫叫做【節(jié)點】，這個都可以，沒有區(qū)別，隨你怎么叫。
• 對于增刪需要挪動大量數(shù)據(jù)的情況，我們可以使用一種手段將前后兩個結(jié)點之間做一個聯(lián)系，也就是前一個結(jié)點存放下一個結(jié)點在堆區(qū)中申請的那塊內(nèi)存地址，也就是我們在C語言中所學(xué)到的指針可以存放一塊地址，這樣就使得前一個結(jié)點和后一個結(jié)點產(chǎn)生了一定的關(guān)聯(lián)。然后當(dāng)我們需要去插入或者刪除數(shù)據(jù)時，只需要修改當(dāng)前結(jié)點所存放的內(nèi)存地址即可，修改了所存放的地址值，這個時候便與新的結(jié)點產(chǎn)生了聯(lián)系

---

對于鏈表這一塊，如果C語言的指針和結(jié)構(gòu)體這一塊你沒有很熟悉的話，學(xué)起來確實會比較困難，但這也不妨礙你看本文，我一定會慢慢地帶你從淺到深，去領(lǐng)會鏈表該如何操作

二、鏈表的初步認(rèn)知

1、結(jié)構(gòu)的聲明與定義

• 首先里看一下鏈表的結(jié)構(gòu)，它的每一個結(jié)點因為要存放數(shù)據(jù)和下一個結(jié)點的地址，因此需要一個數(shù)據(jù)域、一個指針域，如下圖所示👇

• 了解了鏈表的結(jié)構(gòu)體是如何的，接下來我們用代碼的形式將其展現(xiàn)出來
• 可以看到，這里數(shù)據(jù)域的類型是單獨typedef的，這個在順序表中講過，因為每一個數(shù)據(jù)可能并不是整型的，可能是char、long或者是double類型。對于next指針域，你可以看到其為一個結(jié)構(gòu)體指針類型，因為這個next指針，它指向的下一個結(jié)點又是一個封裝好的結(jié)構(gòu)體。

typedef int SLTDataType; typedef struct SListNode { //結(jié)構(gòu)體大小：8BSLTDataType data;struct SListNode* next;//SLTNode* next; 不可以這樣定義，因為還沒有到聲明 }SLTNode;

• 此處的結(jié)構(gòu)體類型我們也進(jìn)行了一個typedef，但是當(dāng)這個結(jié)構(gòu)體聲明出來后，有同學(xué)就把這個next指針的類型就定義成了typedef后的類型，這個是不對的，如果你這樣定義，那說明你的結(jié)構(gòu)體學(xué)的不扎實，這是一種錯誤的定義方式，此處的SLTNode還沒有聲明出來，所以是不可以使用的
• 它的定義格式實際上是這樣的，當(dāng)你去使用SLTNode定義next指針時，它還沒有被聲明出來

typedef int SLTDataType; struct SListNode { //結(jié)構(gòu)體大小：8BSLTDataType data;struct SListNode* next; }; typedef struct SListNode SLTNode；

2、棧區(qū)存放與堆區(qū)存放

明白了如何去定義一個結(jié)構(gòu)體，接下去我們就用這個定義的結(jié)構(gòu)體試著去創(chuàng)建一兩個結(jié)點，然后對它們進(jìn)行一個鏈接，我用了下面兩種定義和鏈接方法，你覺得哪個更好呢？

第一種，指針類型【動態(tài)開辟】

SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode)); SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode)); n1->next = n2;

第二種，變量類型【直接定義】

SLTNode n3, n4; n3.next = &n4;

• 那有小伙伴可能就被難住了，接下來聽我給你說說👊
• 對于鏈表，當(dāng)我們?nèi)ザx一個個結(jié)點進(jìn)行插入的時候，都是希望在最后能將這些結(jié)點鏈接成為一個鏈?zhǔn)奖硪粯?#xff0c;所以想讓它保存在最后。但是第二種直接定義的變量類型卻做不到這一點，這樣的定義方式屬于一種局部變量的定義，對于局部變量的定義，是在內(nèi)存中的【棧區(qū)】為其開辟空間的，這就我們常說的【棧幀】，函數(shù)中的變量定義就需要消耗一定的棧幀，但你這個函數(shù)結(jié)束之后，那這個棧幀也就銷毀了，此時你辛辛苦苦鏈接起來的鏈表中各個結(jié)點的數(shù)據(jù)也就隨著棧幀的銷毀而蕩然無存了，這其實就相當(dāng)于是出Bug了
• 但若是用上面一種定義方式去弄的話，就不會造成這樣的現(xiàn)象，之前我們有說到過，對于動態(tài)申請的空間，是存放在內(nèi)存【堆區(qū)】中的，而對于堆區(qū)中存放的內(nèi)容，是到程序結(jié)束才會銷毀，而且上面提到，對于每一個鏈表結(jié)點，我們最好使用動態(tài)開辟的方式是申請空間，這樣的彈性就更加大一些，不會像順序表那樣需要不斷地擴(kuò)容

3、開始鏈接結(jié)點啦🎉【邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)分】

• 明白了要使用malloc去動態(tài)開辟結(jié)點，將其存放在【堆區(qū)】中，接下去就開辟幾個結(jié)點，然后將他們進(jìn)行一個鏈接

SLTNode* BuySLTNode(SLTDataType x) {//動態(tài)開辟SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL; }

• 可以看到，這里我將動態(tài)開辟一塊空間并且初始化結(jié)點值封裝成了一個叫【BuySLTNode】的函數(shù)，也就是得到一個鏈表結(jié)點，最后用一個鏈表結(jié)構(gòu)體類型去接收一下，就有了四個結(jié)點值，最后將他們一一鏈接起來即可🔒

SLTNode* n1 = BuySLTNode(1); SLTNode* n2 = BuySLTNode(2); SLTNode* n3 = BuySLTNode(3); SLTNode* n4 = BuySLTNode(4); n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL;

• 那個這四個結(jié)點在你腦海中鏈接起來是什么樣子的呢，我想一定是下面這種樣子，每個結(jié)點對應(yīng)一個變量，然后其next指針域使用一個箭頭符號指向下一個結(jié)點

• 這是大多數(shù)人的思維，但是在計算機(jī)實際的內(nèi)存中，可不是這樣存儲的，真正的物理結(jié)構(gòu)是下面這樣
• 當(dāng)你申請出了一塊空間，然后初始化這個結(jié)點的值并且用一個結(jié)構(gòu)體鏈表結(jié)點去接收的時候，這個n1，n2，n3，n4并不是普通的變量，而是一個指針變量，一個結(jié)構(gòu)體指針變量，既然是指針那就一定指向一塊內(nèi)存地址，也就是我們在Buy一個結(jié)點的時候為這個結(jié)點所申請的這塊內(nèi)存地址，而當(dāng)你去解引用這個指針變量時，也就拿到了這塊內(nèi)存的地址值，這其實就可以解釋了為什么n1->next = n2，是等于n2，而不是一個內(nèi)存地址值，因為這個n2中存放的就是當(dāng)前這個結(jié)點在堆區(qū)中申請的這塊地址

n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL;

• 接下去我解釋一下這些結(jié)點之間的聯(lián)系，對于這些結(jié)點我們上面說過了，具有一個數(shù)據(jù)域和一個指針域，對于指針域，它與下一個結(jié)點之間的關(guān)系其實并不是用一個箭頭去指向的，當(dāng)然下面的這張圖我只是為了更加形象，當(dāng)前結(jié)點指針域與下一個結(jié)點之間的關(guān)系應(yīng)該是當(dāng)前結(jié)點指針域存放下一個結(jié)點在堆區(qū)中申請的內(nèi)存地址

• 那這么說可能還是不太直觀，我們進(jìn)編譯器中去DeBug一探究竟🔍
• 可以看出，確實是這樣，這下你應(yīng)該有所理解了吧

4、運行起來了，開始玩鏈表

搞清楚了鏈表的各個結(jié)點直接是如何前后鏈接起來的，接下去我們正式地來玩一玩💷，申請多個結(jié)點將他們串起來

SLTNode* BuySLTNode(SLTDataType x) {//動態(tài)開辟SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL; } SLTNode* SListCreate(int n) {SLTNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; ++i){SLTNode* newnode = BuySLTNode(i);if (phead == NULL)phead = ptail = newnode;else{ptail->next = newnode;ptail = newnode;}}return phead; }

• 解釋一下新寫的這段邏輯，通過傳進(jìn)來需要構(gòu)建的n個結(jié)點，我們需要通過循環(huán)去一一搭建，那我們就需要使用到構(gòu)建鏈表的一個很重要邏輯——尾插法，首先我們要去定義一個頭結(jié)點指針和一個尾結(jié)點指針，對于鏈表，有帶頭結(jié)點和不帶頭結(jié)點的類型，后面我們會詳細(xì)介紹。對于這個頭結(jié)點指針phead，就是用來保存頭結(jié)點的，對于這個ptail尾結(jié)點指針，就是用來鏈接數(shù)據(jù)的，將每一個待插入的結(jié)點鏈接到當(dāng)前尾結(jié)點指針的后一個結(jié)點，也就是執(zhí)行這句

ptail->next = newnode; ptail = newnode;

• 我們通過圖示來看一下

• 可以看到，這通過ptail的移動，newnode被不斷插入到鏈表的后面，但是phead卻沒有變化，始終守護(hù)在頭結(jié)點的身邊👼，最后當(dāng)你想要觀看整個鏈表的結(jié)構(gòu)時，去獲取這個頭結(jié)點即可，因為后面的結(jié)點都是鏈接在頭結(jié)點之后的，所以頭結(jié)點不可以變化，一旦變化了那么整個鏈表的結(jié)構(gòu)就亂了😂，最后這是個函數(shù)，返回值類型是LSTNode*，因此返回phead，主函數(shù)中去接收一下即可
• 也就是這個SList，因為當(dāng)這個函數(shù)結(jié)束之后，所建立的棧幀也就跟著銷毀了，此時的phead就不復(fù)存在，但我們將其return返回了，那這個時候SList就保存了這個頭結(jié)點，之后便可以根據(jù)這個頭結(jié)點去訪問鏈表中的所有元素

SLTNode* SList = SListCreate(10);

• 我們?nèi)eBug中看一下，從SList的數(shù)據(jù)結(jié)果來看，它確實獲取了整個鏈表的所有內(nèi)容😍

打印鏈表【生活小案例2——王思聰不需要省錢】

• 通過畫圖和文字說明，懂得了鏈表存儲的邏輯以及使用頭結(jié)點去訪問整個鏈表，但我們還是看不見摸不著，接下去就進(jìn)行一個可視化，將這個鏈表打印出來看看
• 我們一樣是本著這個不輕易改變頭結(jié)點的原則，定義一個結(jié)點指針去存放獲取這個頭結(jié)點，將phead的值給到一個cur的指針變量，然后的話就是我們熟悉的遍歷操作，上代碼??

void PrintList(SLTNode* phead) {SLTNode* cur = phead; //盡量不用頭指針，定義變量存放while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n"); }

• 那有同學(xué)還是搞不懂既然這個phead和cur都是相同的，那直接使用phead去遍歷不就好了，再定義一個結(jié)構(gòu)體指針又需要消耗內(nèi)存空間
• 這里我就要和你普及一下有關(guān)內(nèi)存空間的大小的知識了，對于操作系統(tǒng)來說，這個內(nèi)存空間是很富裕的，在計算機(jī)內(nèi)存中1M = 10W(byte)，1G = 10億(byte)，對于一個cur結(jié)構(gòu)體指針的大小，也就是8個B的大小，對于系統(tǒng)來說完全就是芝麻粒小的東西，所以有沒有這個cur完全沒有影響。
• 其實這么小一個cur對于操作系統(tǒng)來說和億萬富萬看待幾千塊錢是一個道理，那比如我們經(jīng)常在媒體娛樂中看到的王思聰，它爸爸就是萬達(dá)集團(tuán)的老總王健林，有一天王思聰和王健林說我這個月給您省了5千塊錢，但是他爸爸卻滿不在乎，因為這些前對他來說就是零花錢一般，省了和沒省也沒什么區(qū)別。
• 那從這里就可以反映出對于編程時有些需要使用到的變量定義我們盡量還是不要省，可以起到它獨特的作用，比如說幫助理解程序，再者就是像我們這里的保護(hù)頭結(jié)點不被輕易改變

此時美麗的鏈表就被形象地打印了出來📷

• 但是為了更加形象地讓大家看出鏈表的物理存儲結(jié)構(gòu)，所以我這樣做👍

printf("[%d|%p]->", cur->data,cur->next);

函數(shù)調(diào)用棧幀圖【?庖丁解牛，細(xì)致剖析】

• 我們可以看到，當(dāng)在Test函數(shù)中調(diào)用這個Create函數(shù)創(chuàng)建鏈表時，便對應(yīng)地開辟出了相應(yīng)的函數(shù)棧幀，對于Test函數(shù)和SListCreate函數(shù)都有它們自己單獨的棧幀，棧幀內(nèi)部就是函數(shù)體中定義的各種變量。因此在起初創(chuàng)建newnode的時候，phead和ptail均是指向這個鏈表的第一個結(jié)點，存了第一個結(jié)點的【地址】。phead是為了函數(shù)結(jié)束后返回，ptail則是為了鏈接
• 對于函數(shù)而言，建立一個函數(shù)開辟棧幀，隨著函數(shù)的結(jié)束棧幀也就跟著銷毀了，這里的phead和ptail也不會存在，這就是我們?yōu)槭裁匆诙阎猩暾埧臻g去存放一個個結(jié)點，上面說到過，堆中申請的空間不會像棧中那樣，隨著函數(shù)的結(jié)束而被釋放，對于malloc動態(tài)開辟出來的空間是需要你去手動釋放的，也就是free()

• 隨著新結(jié)點的插入，尾指針ptail不斷進(jìn)行移動，直至插入最后一個結(jié)點之后便結(jié)束插入，最后ptail是指向最后一個尾結(jié)點，phead是指向頭部第一個結(jié)點，【保存有整個鏈表的結(jié)構(gòu)】，最后將這個phead返回由函數(shù)外界的SList接收，便將Create函數(shù)中的建立的鏈表的頭拷貝給了SList，此時隨著Create函數(shù)的結(jié)束，所建立的棧幀也將銷毀，在函數(shù)內(nèi)部創(chuàng)建的局部變量也跟著一起銷毀，不復(fù)存在
• 我們在C語言中講到過有【作用域】這么一個概念，任何變量，都有它的作用域：對于全局變量而言，它的作用域是從聲明開始到整個程序結(jié)束，但是對于局部變量而言，它的作用域也就是在其所聲明的函數(shù)內(nèi)部而已，出了作用域就銷毀了，但好在我們保存并返回了這個指向鏈表頭的指針，這個指針中又保存著第一個結(jié)點的地址，此時SList便可以通過這個地址去訪問這個鏈表

• 當(dāng)這個SList獲取了鏈表頭結(jié)點的地址后，便將其傳入PrintList中，但是呢PrintList里是不可以使用外界的這個指針變量的，所以在函數(shù)形參部分，就定義了一個指針變量去接收，繼而就將這個鏈表頭結(jié)點指針?biāo)４娴牡刂房截惤o了這個phead的，這里的phead和Create中的phead又是不同的兩個東西，不要混淆。此時兩個獨立的函數(shù)棧幀中的指針變量就都指向堆區(qū)中的同一塊內(nèi)存地址
• 上面說到過，為了不讓這個頭結(jié)點指針發(fā)生變動，就繼續(xù)定義了一個指針變量去進(jìn)行一個變量，從而打印出了這個鏈表的樣子

三、接口算法實現(xiàn)【是時候表演真正的技術(shù)了🆒】

認(rèn)真看完了上面兩個模塊，相信你對鏈表的整體框架和結(jié)構(gòu)已經(jīng)有了一個基本的認(rèn)識，現(xiàn)在我們要真正地去實現(xiàn)一些有關(guān)鏈表操作的接口，以便觀察鏈表這種數(shù)據(jù)結(jié)構(gòu)在處理數(shù)據(jù)的時候與順序表有何不同?

1、尾插【Hard】

• 首先第一個我們就來看看尾插，這個在順序表中有講到過，就是在尾部插入一個數(shù)據(jù)結(jié)點，對于順序表來說很簡單，就是在size的位置放入這個元素接口，然后size++，但是對于鏈表來說，也會很容易嗎？我們一起來看看

經(jīng)典錯誤案例分析

void SListPushBack(SLTNode* phead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);SLTNode* ptail = phead; // while(tail != NULL)while (ptail) //一般寫成這樣{ptail = ptail->next;}ptail = newnode; //只是存放在局部變量中 }

• 首先我給出一種很多同學(xué)常見的思路和寫法，也就是定義一個ptail指針從頭結(jié)點開始慢慢遍歷到最后為空的時候，然后把動態(tài)開辟出來的結(jié)點放到這個ptail中，這是很常見的一種錯誤，原理也是和我們上面講到過的函數(shù)棧幀的建立和銷毀一個道理，這里的ptail只是一個SListPushBack所在的棧幀中的一個局部變量而已，你讓它指向堆區(qū)新開辟出來的一塊空間，在函數(shù)內(nèi)部看起來是鏈接上了，但是當(dāng)這個函數(shù)結(jié)束時，所建立的棧幀便銷毀了，此時局部變量出了它的作用域也會跟著銷毀，所以這個尾部新插的結(jié)點newnode根本就沒有鏈接上
• 對于尾插來說，它的本質(zhì)其實是讓最后一個結(jié)點鏈接新結(jié)點，也就是讓這個next去存放這塊堆區(qū)中申請的地址，這就是我們上面所說的物理結(jié)構(gòu)中結(jié)點與結(jié)點之間的關(guān)系

• 所以應(yīng)該要像下面這么寫，去判斷ptail的next域是否為空，若為空則表示遍歷到了最后一個結(jié)點，此時應(yīng)該使用【 ptail->next = newnode】，讓ptail的next域指向這個新的結(jié)點才對

void SListPushBack(SLTNode* phead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);SLTNode* ptail = phead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode; }

• 當(dāng)然還有一種特殊情況就是這個單鏈表為空，那就要進(jìn)行一個單獨的判斷，然后讓phead指向這個新插入的結(jié)點newnode即可

void SListPushBack(SLTNode* phead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);if (phead == NULL){phead = newnode; //形參的改變不會影響實參}else{SLTNode* ptail = phead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}

• 寫了這么一大堆，這回肯定是天衣無縫了，我們?nèi)y試一下吧
• 哦哦，好像不太對誒😳，插入了三個數(shù)據(jù)，但是完全沒有插進(jìn)去的樣子，這是為什么？我們來DeBug看一下

• 可以看到在DeBug中，我們需要讓這個單鏈表形成的樣子應(yīng)該是第一次尾插的時候?qū)⑵渥鳛槭捉Y(jié)點，先進(jìn)去第一個if判斷，然后在后面兩次時都進(jìn)入下面的else判斷，但是當(dāng)我在調(diào)試的時候，發(fā)現(xiàn)每一次進(jìn)入的都是第一個if，也就意味著這個SList一直就是為空的，但是進(jìn)入函數(shù)內(nèi)部卻可以發(fā)現(xiàn)其實這個phead是指向了newnode所在的內(nèi)存地址的，但是在外面看的時候，這個SList卻始終都是空的，這是為什么呢？
• 這就要說到C語言中的函數(shù)傳參問題了，我們知道，形參的改變是不會影響實參的，對于這個phead，就是SListPushBack中的形參，只是接收外界實參SList傳入的頭指針，也就是說phead所指向的地址并不代表SList也指向這塊地址，這和我們上面Create的時候不同，Create在創(chuàng)建出這個鏈表時會返回指向其頭部的head指針，外界可以接收到，但是在這里的尾插只是一個操作罷了，函數(shù)的返回值是void，因此外界根本無法從返回值來獲取和指向這個首部的指針
• 那有同學(xué)說，這該怎么辦吶，好不容易寫出來了😢。我們繼續(xù)看下去

二級指針真正改變頭結(jié)點的指向【?????】

本模塊對于二級指針不太熟悉的同學(xué)先去看看二級指針有關(guān)的文章，我推薦這篇深入理解二級指針

• 這個時候我們應(yīng)該聯(lián)想到C語言中有關(guān)指針方面很經(jīng)典的一道例題，就是交換兩個變量的值，我們來回顧一下這個代碼

void Swap1(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;} int a = 2, b = 5; printf("a = %d, b = %d\n", a, b); Swap1(&a, &b); printf("a = %d, b = %d\n", a, b);

• 可以看到，兩個變量的值得到了交換，也就是很經(jīng)典的通過指針接收地址去交換兩個變量的值，我們先通過這個小案例帶大家DeBug一下

• 可以看到，對于Swap1函數(shù)，我們傳入了變量a和變量b的地址，然后在形參中，使用到兩個指針變量去接收這兩個地址，在函數(shù)體中，我們又可以通過【*p1和 *p2】解引的操作獲取變量a和變量b的內(nèi)容，引入第三方變量暫時存放一下，就可以實現(xiàn)一個交換了

• 然后在Swap函數(shù)執(zhí)行完后，【*p1】和【*p2】的值進(jìn)行了一個交換

• 當(dāng)這個Swap函數(shù)結(jié)束的時候，因為我們傳入的是兩個變量的地址，所以指針的解引直接是訪問這兩塊地址的內(nèi)容，因而就發(fā)生了一個交換

---

• 好，有了這么一個引入，接下去我們將二級指針的傳參時就好理解一些了
• 對于【int】型的變量，我們要交換改變它們的值需要對【int*】去傳入地址，拓展一下
• 對于【int*】型的變量，我們要交換改變它們的值需要對【int**】去傳入地址，傳入什么地址呢，傳入的就是【int*】的地址
• 這里的【int**】就是我們在C語言中學(xué)過的二級指針，接下去還是交換值，通過二級指針來看看如何進(jìn)行傳參交換

void Swap2(int** pp1, int** pp2) {int* tmp = *pp1;*pp1 = *pp2;*pp2 = tmp; } void test1() {int a = 2, b = 5;int* p1 = &a, * p2 = &b;printf("*p1 = %d, *p2 = %d\n", *p1, *p2);Swap2(&p1, &p2);printf("*p1 = %d, *p2 = %d\n", *p1, *p2); }

• 可以看到，對于這里的變量a我首先通過一個指針變量p1去存放它的地址，對于變量b則是用p2存放，然后在Swap2中，傳入這兩個【一級指針變量】的地址，給到【二級指針變量】形參分別去接收它們的地址，我們繼續(xù)通過DeBug來看一下
• 可以看到，pp1這個二級指針存放的是一級指針p1的地址；pp2同理存放p2的地址，
• *pp1解引用將二級指針降為一級指針，使得 【*pp1 = p1】【 *pp2 = p2】，此時他們的指向都是相同的，存放的都是變量a和變量b的內(nèi)存地址
• 拿一個【int*】類型的一級指針變量tmp去接收*pp1也就是一級指針p1，此時

• 可以看到，讓Swap2函數(shù)結(jié)束時，*pp1和 *pp2這兩個一級指針的指向便發(fā)生了改變，然后通過解引用又改變了指向地址中所粗放的內(nèi)容

• 結(jié)束函數(shù)回到test1()可以看到pp1和pp2這兩個二級指針都變灰了，這其實就是VS中所展現(xiàn)的函數(shù)調(diào)用結(jié)束內(nèi)部變量隨著棧幀的銷毀而被釋放，但是因為我傳入的p1與p2的這兩個一級指針的地址，所以函數(shù)內(nèi)部就相當(dāng)于獲取到了這兩個指針?biāo)赶虻牡刂?#xff0c;實現(xiàn)了一個同意操作，因此函數(shù)內(nèi)部的改變便帶動了外界的p1和p2指向的改變，由下圖便可看出
• 然后從運行結(jié)果可以看到*p1和 *p2也就是 a 與 b值進(jìn)行了一個交換，這就實現(xiàn)了一個通過二級指針傳參來交換改變變量內(nèi)容的操作

---

但是我將這個二級指針有什么用呢？難道只是給你普及一下二級指針的知識嗎，那當(dāng)然不是，實際上就是為了通過這個二級指針接收以及結(jié)構(gòu)體指針SList去真正地通過內(nèi)部的修改改變外部的頭結(jié)點指針，我們通過代碼來看一下

//傳二級指針 void SListPushBack(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;//通過二級指針的解引用改變頭結(jié)點【從NULL->newnode】}else{SLTNode* pptail = *pphead;while (pptail->next){pptail = pptail->next;//無需再使用二級指針，無需改變頭結(jié)點，只需要做一個鏈接//改變結(jié)構(gòu)體的指向，使用結(jié)構(gòu)體指針}pptail->next = newnode;} } SLTNode* SList = NULL; SListPushBack(&SList, 100); SListPushBack(&SList, 200); SListPushBack(&SList, 300); PrintList(SList);

• 可以看到函數(shù)中的形參我使用的是一個二級指針，然后在test中，我將這個指向頭結(jié)點的一級指針SList的地址傳了進(jìn)去，當(dāng)?shù)谝淮挝膊暹@個100的時候，便會進(jìn)入第一個if分支,*pphead便是解引用之后的一級指針，就相當(dāng)于這個SList，因此當(dāng)你將新開辟的結(jié)點newnode插入時，便直接將【*pphead】指向了這塊堆區(qū)中的地址。然后在第二次插入200的時候，便會進(jìn)入第二個else分支，使用一個一級指針類型的指針變量pptail去接收【 *pphead】，不斷往后遍歷，然后將兩個結(jié)點通過【存放地址】的關(guān)系鏈接起來，就完成了我們的尾插操作
• 有同學(xué)可能對下面這段else邏輯比較疑惑，為什么在修改頭結(jié)點的時候要用到二級指針，但是在后面的鏈接中不需要用到了呢?，這個時候就要去思考，因為在后驅(qū)的結(jié)點鏈接時只是做一個將當(dāng)前結(jié)點的next存放下一個結(jié)點在堆區(qū)中開辟的地址，這個操作我們前面的一級指針也可以完成，因此無需使用到二級指針，但是在外界傳參的時候我們還是選擇用二級指針接收以及指針的地址，因為函數(shù)的結(jié)構(gòu)已經(jīng)聲明了是無法改變的，不能因為第一次需要改變頭結(jié)點傳入二級指針，但是在后面要無需用到二級指針就突然將這個pphead變?yōu)橐患壷羔?#xff0c;這違背了編程的嚴(yán)謹(jǐn)性

接下去一樣通過函數(shù)棧幀來講解一下，加深印象，幫助理解

• 可以看到，這里將SList拷貝給了pphead，然后pphead指向這個值為100的結(jié)點了，但是呢SList并沒有，這里的具體操作就是將SList這個一級指針的地址給到了二級指針pphead
• pphead中存地是SList的地址，這里的【*pphead】解引用之后就是這個SList本身，然后主函數(shù)看到【SList = NULL】,所以在判斷【*pphead】的時候就想當(dāng)于在判斷【*SList】，這才會進(jìn)入if分支，通過讓【*pphead = newnode】也讓這個SList指向了100這個數(shù)據(jù)結(jié)點

• 然后隨著PushBack函數(shù)的結(jié)束，函數(shù)所建立的棧幀也就被銷毀，pphead和pptail就都沒了，但此時這個SList卻通過二級指針傳參指向了尾插進(jìn)去的第一個結(jié)點，此時這個SList的頭部結(jié)構(gòu)才真正地被改變了，可以繼續(xù)尾插后面的結(jié)點

對于尾插法，你學(xué)【廢】會了嗎😝

---

2、尾刪【Circuitous】

有尾插，那一定也有尾刪，我們一起來探究一下

經(jīng)典錯誤案例分析

• 對于尾刪我們一樣從一個經(jīng)典的錯誤案例開始說起

void SListPopBack(SLTNode* phead) {SLTNode* ptail = phead;while (ptail->next){ptail = ptail->next;}free(ptail);tail = NULL; }

• 對于tail，當(dāng)其遍歷到最后一個結(jié)點，也就是next 為空的時候，跳出循環(huán)，然后free釋放掉這個結(jié)點，然后又進(jìn)行了一步操作將這個tail的值置為空，這個意思就是想著說刪除了一個結(jié)點后尾結(jié)點繼續(xù)置為空
• 有不少同學(xué)一開始都是這樣去是實現(xiàn)的，但這么去寫是會出現(xiàn)問題的，我們?nèi)eBug看一下

• 通過DeBug我們可以看到，當(dāng)PopBack函數(shù)中將這個ptail置為NULL的時候，確實其內(nèi)存地址就變成了【0x00000000】，但是這也只是修改了這個局部變量ptail的值，與鏈表當(dāng)前一個結(jié)點的next域其實沒有任何關(guān)系，可以看到phead最后一個結(jié)點300的next于還是一個地址值，并沒有被置空，這其實就相當(dāng)于一個野指針一般，到后面萬一不小心去修改這個next值，就會造成很大的問題，有關(guān)野指針的問題，后面我會詳細(xì)敘述
• 此時只是這個局部變量做了一個修改，并沒有改變這個結(jié)構(gòu)體，要改變結(jié)構(gòu)體就要使用到結(jié)構(gòu)體指針

修改方式一：保存ptail的上一個結(jié)點

• 首先來看第一種修改方式，也就是將這個ptail向后遍歷的時候先做一個保存，放到一個結(jié)構(gòu)體指針prev中，在向后遍歷的時候若ptail遍歷到最后一個結(jié)點，直接free釋放ptail即可，然后讓prev->next = NULL，這個時候結(jié)構(gòu)體就發(fā)生了改變，這個next指針域也發(fā)生了真正的改變，不會像上面一樣變成一個野指針充滿【?dangerous?】

//way1 SLTNode* ptail = phead; SLTNode* prev = NULL; while (ptail->next != NULL) {prev = ptail;ptail = ptail->next; } free(ptail); prev->next = NULL;

修改方式二：ptail->next->next

• 然后說說第二種修改方式，也就是不需要去再定義一個prev指針去保存，而是直接判斷【ptail->next->next】是否為空即可，此時這里的ptail便為尾結(jié)點的前一個結(jié)點，因此free(ptail->next)就是刪除尾結(jié)點，最后將這個結(jié)點置為空

//way2 SLTNode* ptail = phead; while (ptail->next->next != NULL) {ptail = ptail->next; } free(ptail->next); ptail->next = NULL;

特殊情況修正【單個結(jié)點、二級指針修改、斷言報錯】

• 你以為用這樣就可以真正地實現(xiàn)尾刪了嗎，那還遠(yuǎn)遠(yuǎn)不夠，路還有很遠(yuǎn)🐎，繼續(xù)分析下去吧
• 可以看到，在這里我執(zhí)行了三次PopBack，然后到最后一次的時候，發(fā)現(xiàn)ptail->next==NULL，但是ptail->next->next卻是一個越界的位置，這個時候其實就不對了，之前我們有說過，訪問越界是一個很大的問題

• 所以，對于單個結(jié)點的尾刪，我們應(yīng)該進(jìn)行一個單獨的判斷。也就是當(dāng)前傳入進(jìn)來然后接收的這個phead所指向的next是否為空。若為空，則表示此單鏈表只有一個結(jié)點，直接free這個phead即可，然后將其置為NULL

void SListPopBack(SLTNode* phead) {if (phead->next == NULL){ //只有一個結(jié)點free(phead);phead = NULL;}else{SLTNode* ptail = phead;while (ptail->next->next != NULL){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;} }

---

• 那有同學(xué)說，這個時候應(yīng)該沒問題了吧，單個結(jié)點的情況都被我考慮到了，簡直天衣無縫😏
• 但是。。。Exception它又來了

• 不說了，沒有愛了??直接DeBug吧??
• 那這里是又可以看到，我們在寫尾插的時候出現(xiàn)過的情況，就是函數(shù)內(nèi)部做了改變但是外界并不知曉，那這個時候該怎么辦呢？沒錯，就是它，👉二級指針👈

• 那這下可好了，整個函數(shù)的結(jié)構(gòu)又要重新定義，這其實是正常的，調(diào)Bug就是不斷在試錯的過程，當(dāng)你找出錯來了，那就應(yīng)該及時更正，不要怕麻煩
• 一樣，就像下面這么改，對于只有單個結(jié)點需要單獨處理時使用*pphead去獲取一級指針進(jìn)行操作~

void SListPopBack(SLTNode** phead) {if ((*phead)->next == NULL){ //若只有一個結(jié)點，直接將其釋放，傳入二級指針便改變了鏈表的頭結(jié)點free(*phead);*phead = NULL;}else{SLTNode* ptail = *phead;while (ptail->next->next != NULL){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;} }

• 然后我們再來看一下運行結(jié)果，可以看到，鏈表終于被清干凈了

---

• 真的是天衣無縫、百無一失了嗎？我再刪一次你看看😱

• 可以看到，此時的鏈表已經(jīng)為空，但是我又執(zhí)行了一次PopBack操作，那有同學(xué)說，那你這不是手欠嗎，人家都被刪空了你還要再刪一次，成心跟人過不去是吧😠
• 記住一點，你永遠(yuǎn)要考慮要一些隨性操作的用戶，指不定那天進(jìn)行了一些你開發(fā)時想都想不到的操作🐭

• 這其實就是什么問題？沒錯，就是訪問越界的問題，當(dāng)你將鏈表已經(jīng)刪空的時候，再去對鏈表進(jìn)行一個刪除，此時訪問的就是一個隨機(jī)的位置，超出了你所能訪問的界限，編譯器也就很好地為你【檢查出了錯誤】
• 那此時我們應(yīng)該怎么辦呢？沒錯，就是在PopBack函數(shù)進(jìn)來的一開始，就進(jìn)行一個判斷，看看這個指針?biāo)赶虻念^是否為空，若是為空，則執(zhí)行相應(yīng)的報錯
• 在這里我們選擇直接使用暴力的方式，也就是斷言【assert】，不要溫柔的if判斷，直接報出來哪里有問題，然后打一頓再說💪

void SListPopBack(SLTNode** phead) {assert(*phead);if ((*phead)->next == NULL){ //若只有一個結(jié)點，直接將其釋放，傳入二級指針便改變了鏈表的頭結(jié)點free(*phead);*phead = NULL;}else{SLTNode* ptail = *phead;while (ptail->next->next != NULL){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;}

以上就是尾刪法的最終版本，你又學(xué)【廢】了嗎😝

---

說完尾插和尾刪，還有頭插和頭刪，但是不要驚慌，對于頭插和頭刪，沒有你想象得那么復(fù)雜😵

3、頭插【Easy】

• 對于頭插其實并不復(fù)雜，也就是創(chuàng)建出一個新的結(jié)點newnode，然后讓這個結(jié)點的next域存放首個結(jié)點的地址，還是一樣，對于頭插和頭刪，都是要使用到二級指針的，否則內(nèi)部的改動是無法帶動外部的變化
• 要將這個二級指針化為一級指針我們說過很多遍，一次*解引用即可。鏈接上后將這個新的頭所存在的地址給到指向頭結(jié)點的指針即可

void SListPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);newnode->next = (*pphead); //二級指針解引，變?yōu)橐患壷羔?/span>*pphead = newnode; //再讓newnode變?yōu)樾碌念^ }

• 怎么樣，簡單吧，很快就說完了，一方面是因為我們前面鋪墊得很多，你所掌握的東西我已經(jīng)不需要說了，另一方面在對于單鏈表而言，它的頭插和頭刪確實比尾插和尾刪來得高效

4、頭刪【Easy】

• 說完頭插，馬上趁熱打鐵來說說頭刪
• 還是一樣，并不復(fù)雜。因為刪除這個頭，那當(dāng)其刪除之后，它的后一個結(jié)點也就成為了新的頭，這個時候就需要做一個更新，但這個前提是你能訪問到后面這個結(jié)點，所以我們要事先去保存當(dāng)前頭結(jié)點的后一個結(jié)點，然后將頭結(jié)點free釋放，最后更新讓頭結(jié)點指針重新指向下一個新的結(jié)點即可

void SListPopFront(SLTNode** pphead) {assert(*pphead); //刪除都先斷言一下，看看傳進(jìn)來的鏈表是否為空SLTNode* next = (*pphead)->next; //先保存當(dāng)前首結(jié)點的下一個結(jié)點free(*pphead);(*pphead) = next; }

5、查找

• 看完了尾插、尾刪、頭插、頭刪。接下來我們要學(xué)習(xí)的是去鏈表中查找指定元素，先來看看接口定義

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

• 可以看到，形參接收的是頭結(jié)點指針，以及需要查找的值，返回值類型是一個結(jié)構(gòu)體指針，也就是說返回的是一個指向待查結(jié)點的結(jié)構(gòu)體指針，并不是一個下標(biāo)，一個位置，那函數(shù)內(nèi)部我們該如何去寫呢？
• 很簡單，只需要一個cur指針先獲取頭結(jié)點的指向，然后一個個向后查詢即可，若是發(fā)現(xiàn)其指向的data值相同，便返回當(dāng)前的cur指針

SLTNode* cur = phead; //while (cur != NULL) while (cur) {if (cur->data == x)return cur;cur = cur->next; } return NULL; //返回的是指向這個待查結(jié)點的指針，并不是位置

• 我們來測試一下看看

SLTNode* SList = NULL; SListPushBack(&SList, 1); SListPushBack(&SList, 2); SListPushBack(&SList, 3); SListPushBack(&SList, 4); SListPushBack(&SList, 5); PrintList(SList);SLTNode* pos = SListFind(SList, 3); if (pos != NULL) {printf("找到了\n");printf("pos = %d\n", pos->data); } else {printf("沒找到\n"); }

• 可以看到，確實是可以找到，我將這個結(jié)點的data值打印了出來

---

那有同學(xué)問，找到返回了這個值又能怎樣呢，可以拿來做什么？那我告訴你這個用處可大了，后面我們將在找到的這個pos所指的結(jié)點之前、之后進(jìn)行插入和刪除相應(yīng)的結(jié)點，都是要以這個Find接口作為前提

6、在pos位置之后插入結(jié)點

• 接下來我們就來看一看如何在找到的pos位置之后插入一個結(jié)點呢

• 可以看到，我們最后要達(dá)到的是這種效果，就是pos的next要指向這個newnode，然后newnode的next要指向pos->next，這時候有些同學(xué)就會這么去寫。先讓這個pos的next指向newnode，然后再讓newnode的next指向pos的next
• 這個邏輯其實就有問題，當(dāng)pos的next所指位置變化之后也就找不到4這個結(jié)點了，執(zhí)行完第一條語句后pos的next就變成了newnode，這個時候再讓newnode指向pos的next，也就是讓newnode指向它自己，這也就不對了

//pos的下一個位置就沒了，相當(dāng)于是newnode自己指向自己 pos->next = newnode; newnode->next = pos->next;

• 所以應(yīng)該把這兩條語句做一個交換。先讓newode的next指向pos的next，也就是4，然后再讓pos指向這個newnode，這個時候結(jié)點之間的鏈接就沒問題了😯

newnode->next = pos->next; pos->next = newnode;

• 通過這段代碼，我們插入一個值試試看。從打印結(jié)果看來，確實在3后面插入了一個9

警惕傳入空指針【?細(xì)致講解斷言assert】

• 還是一樣，繼續(xù)思考有沒有可能出現(xiàn)特殊情況，我們來看看這種
• 可以看到，鏈表中的結(jié)點值只有1~5但是卻需要找一個88，很明顯是找不到的，此時便會return NULL，那么外界的pos接受到的值就是一個空值，也就說這是一個空指針，所以當(dāng)你傳一個空指針進(jìn)去，你讓函數(shù)內(nèi)部怎么實現(xiàn)一個插入呢

SLTNode* pos = SListFind(SList, 88); SListInsertAfter(pos, 9); PrintList(SList);

• 此時可以看到，程序發(fā)生了奔潰/(ㄒoㄒ)/~~

• 看到這個地方，我相信你的第一反應(yīng)就是在函數(shù)一開始的加一個斷言，判斷這個pos是否為空
• 可能有些同學(xué)不了解里面的傳參機(jī)制以及判斷機(jī)制，我這里講一下：對于assert斷言來說，就是還函數(shù)還沒有執(zhí)行的時候去做的一件事，而不是應(yīng)該把它放在函數(shù)體的中間或者結(jié)尾，這點首先要明確；其次assert斷言的內(nèi)部參數(shù)你需要傳入的是你需要檢查的傳入進(jìn)來的某個參數(shù)變量，一般是去判斷是否為空或者是否小于0。所以對于參數(shù)，你應(yīng)該寫入的是會報出錯誤的對立面，舉個例子，當(dāng)你想要檢查a是否大于0，a小于0就會報錯，因此應(yīng)該寫assert(a > 0)。若是去判斷一個指針是否為空，就要這樣寫：assert(p != NULL)，或者直接簡寫成assert( p )，就想我們的while循環(huán)去判空是一個道理；知道了傳參邏輯，最后說說assert的判斷機(jī)制，就是當(dāng)你所寫的表達(dá)式不成立時，也就是當(dāng)【p == NULL】時，就會出現(xiàn)警告，報出錯誤。在計算機(jī)中【0是假，非0才是真】，當(dāng)【p = NULL】時，這個表達(dá)式就變?yōu)榱思?#xff0c;非0一般指1，就是p != NULL，表明傳進(jìn)來的指針p不為空，那也就是不會滿足條件
• 我們通過CPlusPlus來看看，明確說到當(dāng)表達(dá)式的值為0的時候，就會向標(biāo)準(zhǔn)的錯誤設(shè)備寫入一條消息終止調(diào)用，也就是斷言assert后面的語句均不會執(zhí)行

• 所以應(yīng)該在InsertAfter函數(shù)的開頭加上這一句話

//0是假，非0才是真 assert(pos != NULL); //若不為空，則不會執(zhí)行；若為空，則報出警告 //assert(pos);

• 此時可以看到，加上這句話后斷言就出現(xiàn)了，直接給你報出了那個cpp文件的哪一行出了問題，也就是我們剛才寫斷言的地方，這個時候你立馬可以進(jìn)行精確定位然后排錯，這個時候也就提高了程序的可維護(hù)性，所以作為我們程序員來說，學(xué)會使用斷言是很重要的，但是斷言并不是什么地方都可以隨便加的，根據(jù)需求來加，也就是【因地制宜】，不然會出現(xiàn)麻煩，結(jié)尾總結(jié)的時候會說到📖

【生活小案例3——請人吃飯要帶錢💴】

• 通過傳入空指針去插入一個結(jié)點可以看到是一個很荒謬的事情，我們聯(lián)想一個生活中的小案例來理解一下，順便輕松一刻，你傳入一個空指針和一個待插入的結(jié)點值，其實就相當(dāng)于你帶你說今天請你朋友去外面吃飯，但是吃飯之后一看錢包是空的，于是這個時候就只能讓你朋友付錢了【假設(shè)不支持手機(jī)支付】，那你說這個事情是不是很荒謬，assert斷言其實就是在出門之前檢查一下你有沒有帶錢，如果沒有帶那就會報出警告提醒你要帶錢出門
• 所以在函數(shù)進(jìn)行傳遞指針的時候一定要檢查傳遞的是不是空指針，就想出門檢查自己有沒有帶錢是一個道理

7、在pos位置之前插入結(jié)點

• 說完了在這個pos位置之后插入結(jié)點，那有后一定有前，現(xiàn)在我們來談一談如何在獲取到的pos位置前插入一個結(jié)點。對于這個，說在前面，會出現(xiàn)兩種情況：一種是當(dāng)前找到的pos在鏈表中間的某個地方，還有一種比較特殊，就是這個pos剛好是頭結(jié)點，這個時候進(jìn)行的其實就是我們上面說過的頭插法，那既然是頭插法，就需要去改變這個鏈表的頭，所以又需要使用到二級指針

void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x) {if (*pphead == pos) {//若pos位置就為原先的頭結(jié)點，則使用頭插法進(jìn)行插入SListPushFront(pphead,x);}else {SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* newnode = BuySLTNode(x);//此處無需考慮前后錯亂問題，直接鏈接即可cur->next = newnode;newnode->next = pos;} }

• 直接給出代碼做講解。一樣的老套路，通過*pphead進(jìn)行解引用，獲取到外界SList這個頭結(jié)點指針，然后去進(jìn)行一個判斷即可，若這個 *phead真的和pos相同，直接調(diào)用一下我們上面寫過的頭插法即可，實現(xiàn)了功能的復(fù)用，具體圖示如下👇

• 然后再來說一下普通情況，也就是在鏈表其中的某一個位置前插入,所以我們要獲取pos指針?biāo)赶虻那耙粋€位置，開頭說到過，雖然單鏈表對于插入和刪除很方便，但是訪問結(jié)點并不方便，需要從頭結(jié)點開始訪問，于是還是一樣的套路，定義一個cur指針首先獲取到頭結(jié)點指針的值，也就是把二級指針pphead解引用一下，然后一直去遍歷即可，直到這個【cur->next = pos】為止，停下來，此時就可以做一個鏈接了，具體圖示如下👇
• 可以看到，此時無需像在后面插入結(jié)點一般去考慮這個先后的順序關(guān)系，只需要將【cur】【newnode】【pos】這三個指針做一個鏈接即可

• 最后我們來通過測試驗證一下結(jié)果
• 這是普通情況

• 來看特殊情況

---

看完了如何插入結(jié)點，接下去我們來說說如何在查找到的pos位置前后刪除結(jié)點

8、刪除pos位置之后的結(jié)點

• 首先來說一說如何刪除pos位置之后的結(jié)點
• 首先來看一下函數(shù)體聲明，很明顯，只需要傳入一個pos指針即可，其余不需要

void SListEraseAfter(SLTNode* pos)

• 然后我們來考慮函數(shù)體內(nèi)部，首先要做的事情相信你已經(jīng)很敏感了，對于刪除我們都要assert一下這個傳入的指針是否為空，若為空則不能對其進(jìn)行操作。然后需要考慮的就是特殊情況，有什么特殊情況呢？就是下面這種pos為最后一個尾結(jié)點時，后面沒有結(jié)點可刪，此時直直接return返回即可，當(dāng)然你也可以用assert斷言

• 然后就是這種正常的情況,我們需要修改pos所在結(jié)點的指針域，因為刪除了后一個結(jié)點，所以要將其指針域改為下一個結(jié)點的再下一個結(jié)點，于是有同學(xué)就會這么寫。這里寫其實是有問題的，從內(nèi)存的角度來說，因為pos的next已經(jīng)改變了，此時【pos->next】這塊地址已經(jīng)訪問不到了，再去free的話也是徒勞

pos->next = pos->next->next; free(pos->next);

• 因為我們需要將【pos->next】做一個臨時保存，這樣當(dāng)pos的next指針域改變時，也可以訪問到這個被刪除的結(jié)點

• 具體代碼如下

void SListEraseAfter(SLTNode* pos) {assert(pos);SLTNode* nextNode = pos->next;if (nextNode == NULL){return; //考慮到所查找到的結(jié)點為最后一個結(jié)點，后面無結(jié)點可刪}else {pos->next = nextNode->next;free(nextNode);}

• 那這個時候有同學(xué)又來抬杠說，再定義一個看著冗雜，為啥不先把這個結(jié)點釋放，然后再修改指針域呢？
• 大家覺得這樣可以嗎?

free(pos->next); pos->next = pos->next->next;

• 其實這是一種非常典型的錯誤，很多同學(xué)都容易犯，當(dāng)你將這個結(jié)點free掉之后，那也就是說其data域和next都沒了，但是待刪結(jié)點3的next域存放有結(jié)點4的地址，你講它提前釋放了，那pos怎么找得到呢，此時【pos->next】就變成了一種我們都聽說過的東西，叫做【野指針】，可能有小伙伴沒聽說過，也沒關(guān)系，我們可以來了解一下

野指針的危害【生活小案例4——酒店房門的鑰匙🔑】

• 就我們理解而言，指針都是指向一個地址，野指針也不例外，它指向一個地址，但是呢，這塊地址不是確定的，而是隨機(jī)的。
• 這一塊我不是非常了解，大家可以看看這篇博客——》野指針的產(chǎn)生及其危害

通過閱讀這篇文章，我也了解到了一些有關(guān)野指針的知識，但是這么理解起來比較晦澀難懂，因為還是按照我們的慣例，通過生活的一個小案例來幫助大家理解

• 首先來說一說釋放結(jié)點的含義：對于結(jié)點的釋放呢，并不是把此結(jié)點存放的地址給銷毀了，而是此結(jié)點所存放的地址的使用權(quán)不屬于你了，還給了操作系統(tǒng)。對于申請內(nèi)存就像去酒店開房間，這個房間的使用權(quán)就屬于你了，不會有人突然闖進(jìn)來，釋放了就相當(dāng)于是退房了，這個房間的使用權(quán)就不屬于你了，但是這個房間還在【這一點很重要，這個房間還在！！】
• 剛才說到酒店開房，我們具體來說說：你在酒店🏨開了一個房間，住了一晚后把這個房間退了，但是在走之前打電話找了一個鎖匠根據(jù)這個房間的所配了一把鑰匙。野指針訪問隨機(jī)內(nèi)存就好比你后一個晚上沒有登記入住但是卻通過這把自己裝配的鑰匙進(jìn)入了這個房間，又在里面住了一個晚上然后這個晚上剛好沒什么客人，保潔阿姨也請假了，所以你又白嫖了一個晚上。于是你打算明天再來住一次，可是這一次，卻有很大的禍患，晚上來了一個旅行團(tuán)，于是很多房間都要重新打掃，然后就發(fā)現(xiàn)你還住在這里，就報警把你抓了起來👮
• 這把鑰匙其實就相當(dāng)于是野指針。野指針真正的危害在于【這塊內(nèi)存已經(jīng)釋放了，是一個隨機(jī)值，但還有一個指針指向這塊地址，但是這個地址是不被保護(hù)的，隨時都有可能出問題】
• 所以對于野指針的訪問不一定會報錯，取決你有沒有被編譯器查到💻

通過這么一個案例，大家對野指針這一塊應(yīng)該有所了解了，所以不要輕易將指針亂指，可能那塊地址就是隨機(jī)的

---

• 看了野指針的危害，我們繼續(xù)回到代碼中來DeBug看看，使用野指針會出現(xiàn)什么情況

free(pos->next); pos->next = pos->next->next;

• 從圖中可以看出，一開始進(jìn)去的時候，pos->next也就是我們定義的nextNode，存有4的地址，但是當(dāng)我們先去free之后，這個地址就不見了，而且數(shù)據(jù)值也變成了一個隨機(jī)值，所以這個時候再去訪問pos->next就是一個【野指針】了

• 但是這個時候編譯器卻不會報錯，正常運行下去了，此時我們來看看外界的SList
• 可以看出，確實出問題了，我們需要刪除的是pos所指向的next，也就是3這個位置，但是當(dāng)先free之后，此時4也沒有了，找不到了，2的next指向的是一個隨機(jī)的地址，那編譯器對于這種問題不會報錯嗎？當(dāng)然會，但不會是在這里，而是在Print中

• 因為打印的時候需要隨著next指針?biāo)娣诺牡刂芬灰辉L問，因此當(dāng)訪問到2的next時，便出現(xiàn)了訪問異常，因為它訪問的是一塊不確實的地址，是沒有被分配的，里面沒有任何東西，因此這時編譯器就會報出異常

所以大家在進(jìn)行指針操作的時候一定要小心，可以一疏忽你的指針就變成了野指針🗡

9、刪除pos位置之前的結(jié)點

• 說完了pos位置之后的結(jié)點刪除操作，那之前的一定也要說，和這個和插入一樣，會有多種情況，可能會改變頭結(jié)點，因此需要使用到二級指針

void SListEraseBefore(SLTNode** pphead, SLTNode* pos)

第一種：pos就位于頭結(jié)點位置

• 這種情況的話是無法刪除的，因為頭結(jié)點前面為空，所以直接返回即可，當(dāng)然你也可以assert

//當(dāng)pos就為頭結(jié)點時 if ((*pphead) == pos) {return; }

第二種：pos位于頭結(jié)點的后一個位置，需要刪除的便為頭結(jié)點

• 這個的話就是我們前面講到過的頭刪，直接調(diào)用即可

else if ((*pphead)->next == pos) {SListPopFront(pphead); //頭刪 }

第三種：正常情況，但是比較繁瑣

• 對于正常情況，其實是比較麻煩的，我們來看看

• 對于這種情況，因為我們是要去刪除pos結(jié)點的前一個結(jié)點，但是我們知道，要刪除一個結(jié)點，就要找到它的前一個結(jié)點，因此這個時候我們需要定義一個結(jié)構(gòu)體指針cur，剛開始指針【*pphead】，在不斷往后遍歷的時候當(dāng)【cur->next->next == pos】時，定義一個指針指向當(dāng)前cur的next，進(jìn)行一個保存，接著執(zhí)行【cur->next = delnode->next】，便可以進(jìn)行一個刪除
• 具體代碼如下

void SListEraseBefore(SLTNode** pphead, SLTNode* pos) {assert(pos); //刪除結(jié)點要斷言assert(*pphead); //當(dāng)pos就為頭結(jié)點時if ((*pphead) == pos) {return;} //當(dāng)刪除的結(jié)點為頭結(jié)點時else if ((*pphead)->next == pos) {SListPopFront(pphead); //頭刪}else {SLTNode* cur = *pphead;while (cur->next->next != pos)cur = cur->next;SLTNode* delnode = cur->next;cur->next = delnode->next;free(delnode);} }

• 我們來測試一下看看

10、釋放鏈表

• 最后的壓軸💃當(dāng)然是給到Destroy，既然Create了，那一定要Destroy，有始有終，才是最好
• 首先說一下整體思路。對于單鏈表來說，它和順序表并不一樣，因為對于順序表而言，是一塊連續(xù)的存儲空間，申請的時候是一整塊一起申請，釋放的時候自然也是一整塊一起釋放，因此直接free即可。但是對于鏈表不同，鏈表的每一個結(jié)點在堆內(nèi)存中的空間是隨機(jī)申請的。因此存儲是不連續(xù)的，那對于釋放來說，就需要從頭結(jié)點開始，一一釋放下去
• 首先還是一樣，保留好頭結(jié)點，拿一個指針代替，接著在釋放頭結(jié)點的時候還要先行保存其下一個結(jié)點，然后free掉當(dāng)前的cur結(jié)點，讓cur結(jié)點指向下一個結(jié)點，繼續(xù)進(jìn)行一個釋放

• 看一下代碼

void SLIstDestroy(SLTNode** pphead) {SLTNode* cur = *pphead;while (cur){SLTNode* nextNode = cur->next;free(cur);cur = nextNode;} }

• 你覺得這樣可以了嗎？那有同學(xué)可以說我這么問肯定是不可以，那你知道缺了什么嗎，我們將一個單鏈表Destory一下試試，然后將其打印出來再看看

• 是的，可以看到又是我們所熟悉的野指針，為什么呢？因為你將鏈表的頭結(jié)點釋放了，那這就是一塊隨機(jī)的地址，上面說到過，訪問一塊隨機(jī)的地址，也就形成了【野指針】

【生活小案例5——利劍不鋒利🗡】

• 上面又說到了這個野指針的問題，我們再來談一談，對于野指針，也是它就像是一把鋒利的劍一樣，非常危險，但是呢，它又不是隨時都會有危險，因為當(dāng)這把劍放在劍鞘中時，其實是非常安全的，并不是傷害到你，但是當(dāng)你將它把出來的時候，那這個時候你就要小心使用了，一不留神可能就會傷到自己。
• 對于野指針也是一樣，有的時候你知道這個指針可能會是野指針，但是你不去使用它訪問數(shù)據(jù)，那其實是很安全的，不會有問題，但是當(dāng)你使用到了這個野指針去訪問的時候，其實就會非常危險了。所以在這里還是和大家說一句：謹(jǐn)慎使用指針

---

好，我們回歸正題，既然這樣會造成野指針，那應(yīng)該怎么修改呢，那就是將和這個頭結(jié)點指針置為NULL即可，這個時候再去打印的時候這個鏈表就是空的，也就不會出錯了

---

四、整體代碼展示【需要自取】

SList.h

#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h>typedef int SLTDataType; typedef struct SListNode { //結(jié)構(gòu)體大小：8BSLTDataType data;struct SListNode* next;//SLT* next; 不可以這樣定義，因為還沒有到聲明 }SLTNode;SLTNode* BuySLTNode(SLTDataType x); SLTNode* SListCreate(int n); void PrintList(SLTNode* phead);void SListPushBack(SLTNode** phead, SLTDataType x); void SListPopBack(SLTNode** phead); void SListPushFront(SLTNode** pphead, SLTDataType x); void SListPopFront(SLTNode** pphead);SLTNode* SListFind(SLTNode* phead, SLTDataType x); void SListInsertAfter(SLTNode* pos, SLTDataType x); void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x); void SListEraseAfter(SLTNode* pos); void SListEraseBefore(SLTNode** pphead, SLTNode* pos); void SLIstDestroy(SLTNode** pphead);

SList.cpp

#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" //----------------- /*動態(tài)開辟結(jié)點*/ SLTNode* BuySLTNode(SLTDataType x) {//動態(tài)開辟SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL; } //----------------- /*建立鏈表*/ SLTNode* SListCreate(int n) {SLTNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; ++i){SLTNode* newnode = BuySLTNode(i);if (phead == NULL)phead = ptail = newnode;else{ptail->next = newnode;ptail = newnode;}}return phead; } //----------------- /*打印鏈表*/ void PrintList(SLTNode* phead) {//無需斷言，鏈表為空，可以打印SLTNode* cur = phead; //盡量不用頭指針，定義變量存放【4 byte】while (cur != NULL){printf("%d->", cur->data);//printf("[%d|%p]->", cur->data,cur->next);cur = cur->next;}printf("NULL\n"); } //----------------- /*尾插*/ void SListPushBack(SLTNode** pphead, SLTDataType x) {//無需斷言，鏈表為空，可以尾插SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;//通過二級指針的解引用改變頭結(jié)點【從NULL->newnode】}else{SLTNode* pptail = *pphead;while (pptail->next){pptail = pptail->next;//無需再使用二級指針，無需改變頭結(jié)點，只需要做一個鏈接//改變結(jié)構(gòu)體的指向，使用結(jié)構(gòu)體指針}pptail->next = newnode;} } //----------------- /*尾刪*/ void SListPopBack(SLTNode** phead) {assert(*phead); //必須斷言，鏈表為空，不可尾刪if ((*phead)->next == NULL){ //若只有一個結(jié)點，直接將其釋放，傳入二級指針便改變了鏈表的頭結(jié)點free(*phead);*phead = NULL;}else{SLTNode* ptail = *phead;while (ptail->next->next != NULL){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;} } //----------------- //頭插 void SListPushFront(SLTNode** pphead, SLTDataType x) {//無需斷言，鏈表為空，可以頭插SLTNode* newnode = BuySLTNode(x);newnode->next = (*pphead); //二級指針解引，變?yōu)橐患壷羔?/span>*pphead = newnode; //再讓newnode變?yōu)樾碌念^ }//----------------- //頭刪 void SListPopFront(SLTNode** pphead) { //必須斷言，鏈表為空，不可頭刪assert(*pphead); //刪除都先斷言一下，看看傳進(jìn)來的鏈表是否為空SLTNode* next = (*pphead)->next; //先保存當(dāng)前首結(jié)點的下一個結(jié)點free(*pphead);(*pphead) = next; } //----------------- //查找 SLTNode* SListFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;//while (cur != NULL)while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;//返回的是指向這個待查結(jié)點的指針，并不是位置 } //----------------- //在pos位置之后插入結(jié)點 void SListInsertAfter(SLTNode* pos, SLTDataType x) {//0是假，非0才是真assert(pos != NULL); //若不為空，則不會執(zhí)行；若為空，則報出警告SLTNode* newnode = BuySLTNode(x);//pos->next = newnode;//newnode->next = pos->next;//pos的下一個位置就沒了，相當(dāng)于是newnode自己指向自己newnode->next = pos->next;pos->next = newnode; } //----------------- //在pos位置之前插入結(jié)點 void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x) {if (*pphead == pos) {//若pos位置就為原先的頭結(jié)點，則使用頭插法進(jìn)行插入SListPushFront(pphead,x);}else {SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* newnode = BuySLTNode(x);//此處無需考慮前后錯亂問題，直接鏈接即可cur->next = newnode;newnode->next = pos;} } //----------------- //刪除pos位置之后的結(jié)點 void SListEraseAfter(SLTNode* pos) {assert(pos);SLTNode* nextNode = pos->next;if (nextNode == NULL){return; //考慮到所查找到的結(jié)點為最后一個結(jié)點，后面無結(jié)點可刪}else {//free(pos->next); //會產(chǎn)生野指針//pos->next = pos->next->next;pos->next = nextNode->next;free(nextNode);} //----------------- //刪除pos位置之前的結(jié)點 void SListEraseBefore(SLTNode** pphead, SLTNode* pos) {assert(pos); //刪除結(jié)點要斷言assert(*pphead); //當(dāng)pos就為頭結(jié)點時if ((*pphead) == pos) {return;} //當(dāng)刪除的結(jié)點為頭結(jié)點時else if ((*pphead)->next == pos) {SListPopFront(pphead); //頭刪}else {SLTNode* cur = *pphead;while (cur->next->next != pos)cur = cur->next;SLTNode* delnode = cur->next;cur->next = delnode->next;free(delnode);} } //----------------- //釋放鏈表 void SLIstDestroy(SLTNode** pphead) {SLTNode* cur = *pphead;while (cur){SLTNode* nextNode = cur->next;free(cur);cur = nextNode;}*pphead = NULL; }

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <malloc.h> #include "SList.h"/* 順序表缺陷 * 1.空間不夠，需要擴(kuò)容。擴(kuò)容（尤其是異地擴(kuò)容）是有一定代價的。其次還可能存在一定的空間浪費 * --》擴(kuò)容都是擴(kuò)2倍，擴(kuò)得多了，一些不用空間的就會浪費 * --》擴(kuò)得少了，插入一些數(shù)空間又不夠了，又需要頻繁的擴(kuò)容 * * 【吃米飯】一碗不夠，吃兩碗 * 吃一碗零20粒，頻繁去鍋里舀飯 * * 2.頭部或者中部插入刪除，需要挪動數(shù)據(jù)，效率低下 *//* 優(yōu)化方案 * 1.按需申請釋放【要存儲一個數(shù)據(jù)就開一塊空間（結(jié)點）】 * 2.不要挪動數(shù)據(jù)【指針可以存放下一塊空間的地址】 *//* * 順序表支持隨機(jī)訪問，可以根據(jù)下標(biāo)快速訪問到某個元素 * 鏈表不支持隨機(jī)訪問，只能通過頭結(jié)點的next指針域一個個訪問下去，最壞會到達(dá)O(N) * 假設(shè)順序表是貨車，鏈表是公交車，都是不可替代的 */ void TestSList1() { SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n1->next = n2;SListNode n3, n4;n3.next = &n4;}void TestSList2() {/**/SLTNode* n1 = BuySLTNode(1);SLTNode* n2 = BuySLTNode(2);SLTNode* n3 = BuySLTNode(3);SLTNode* n4 = BuySLTNode(4);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;SLTNode* SList = SListCreate(5);PrintList(SList); }void Swap1(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp; }void Swap2(int** pp1, int** pp2) {int* tmp = *pp1;*pp1 = *pp2;*pp2 = tmp; } void test1() {int a = 2, b = 5;//printf("a = %d, b = %d\n", a, b);//Swap1(&a, &b);//printf("a = %d, b = %d\n", a, b);int* p1 = &a, * p2 = &b;printf("*p1 = %d, *p2 = %d\n", *p1, *p2);Swap2(&p1, &p2);printf("*p1 = %d, *p2 = %d\n", *p1, *p2);printf("a = %d, b = %d\n", a, b); }//尾插 void TestSList3() {//SLTNode* SList = SListCreate(10);//PrintList(SList);//SListPushBack(SList, 100);//SListPushBack(SList, 200);//SListPushBack(SList, 300);SLTNode* SList = NULL;SListPushBack(&SList, 100);SListPushBack(&SList, 200);SListPushBack(&SList, 300);PrintList(SList); }//尾刪 void TestSList4() {SLTNode* SList = NULL;SListPushBack(&SList, 100);SListPushBack(&SList, 200);SListPushBack(&SList, 300);PrintList(SList);SListPopBack(&SList);PrintList(SList);SListPopBack(&SList);PrintList(SList);SListPopBack(&SList);PrintList(SList);//再多刪一次SListPopBack(&SList); //訪問越界PrintList(SList); }//頭插 — 頭刪 //void TestSList5() //{ // SLTNode* SList = NULL; // printf("尾插："); // SListPushBack(&SList, 100); // SListPushBack(&SList, 200); // SListPushBack(&SList, 300); // PrintList(SList); // // SLTNode* SList2 = NULL; // printf("頭插："); // SListPushFront(&SList2, 100); // SListPushFront(&SList2, 200); // SListPushFront(&SList2, 300); // SListPushFront(&SList2, 400); // PrintList(SList2); // // printf("頭刪：\n"); // SListPopFront(&SList2); // PrintList(SList2); // SListPopFront(&SList2); // PrintList(SList2); // SListPopFront(&SList2); // PrintList(SList2); // SListPopFront(&SList2); // PrintList(SList2); //}//查找與插入 void TestSList6() {SLTNode* SList = NULL;SListPushBack(&SList, 1);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 4);SListPushBack(&SList, 5);PrintList(SList);//SLTNode* pos = SListFind(SList, 3);//if (pos != NULL) {// printf("找到了\n");// printf("pos = %d\n", pos->data);// SListInsertAfter(pos, 9);// PrintList(SList);//}//else {// printf("沒找到\n");//}//SLTNode* pos = SListFind(SList, 88);//SListInsertAfter(pos, 9);//PrintList(SList);//SLTNode* pos = SListFind(SList, 3);//SListInsertAfter(pos, 9);//PrintList(SList);//SListInsertBefore(&SList, pos, 11);//PrintList(SList);SLTNode* pos = SListFind(SList, 1);SListInsertBefore(&SList, pos, 8);PrintList(SList); } //刪除之后的結(jié)點 void TestSList7() {SLTNode* SList = NULL;SListPushBack(&SList, 1);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 4);PrintList(SList);SLTNode* pos = SListFind(SList, 2);SListEraseAfter(pos);PrintList(SList); } void TestSList8() {SLTNode* SList = NULL;SListPushBack(&SList, 1);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 4);PrintList(SList);//SLTNode* pos = SListFind(SList, 4);SLTNode* pos = SListFind(SList, 2);//SLTNode* pos = SListFind(SList, 1);SListEraseBefore(&SList, pos);PrintList(SList);SLIstDestroy(&SList);PrintList(SList);} void test() {int a = 'o';printf("%d\n", a); } int main(void) {//TestSList2();//test1();//TestSList3();//TestSList4();//TestSList5();//TestSList6();//TestSList7();TestSList8();//test();return 0; }

五、有關(guān)二級指針和斷言的小結(jié)【?謹(jǐn)記?】

• 看完了上述有關(guān)單鏈表的所有操作，從這些代碼中我們可以看到對于二級指針和斷言的使用比較頻繁，很多接口算法中都用到了這兩個東西，但是對于二級指針和斷言，并不是什么地方都要使用的。
• 仔細(xì)地分析一下就可以知道，對于頭插、尾插、頭刪、尾刪這些操作，以及在pos結(jié)點之前插入和刪除結(jié)點、銷毀結(jié)點，這些接口均需要使用到二級指針來接受鏈表的頭指針，這是為什么呢？不知道大家有沒有想過，那我在各個算法的講解過程中其實都是從一級指針轉(zhuǎn)換到二級指針，原因就是對于函數(shù)內(nèi)部頭結(jié)點的修改不會影響外部頭結(jié)點指針的修改，而且我在二級指針引入那一塊也說到了要改變【int】，就要使用【int*】;要改變【int*】，就要使用【int**】，也就是說我們要改變一級頭結(jié)點指針就要使用二級指針去修改，對于上面這些接口操作，均需要修改頭結(jié)點指針，因此我們便需要使用到二級指針去進(jìn)行一個控制。
• 但是呢，并不是所有的接口都需要使用到二級指針，像打印、查找、在pos結(jié)點之后插入和刪除結(jié)點這些操作，都是不會修改頭結(jié)點指針的，所以我們只需要以及指針就可以了

---

• 然后再來說說斷言的情況，對于斷言，我們在接口的算法實現(xiàn)時也是用的即為頻繁，相信在這么多算法看下來后，你對斷言應(yīng)該是有了一個認(rèn)知了，當(dāng)你程序出問題的時候，它可以幫你快速定位程序的異常之處，這個功能對于大多數(shù)的程序員來說可是一個福音，網(wǎng)上都流傳著這么一句話【一杯茶、一包煙、一個Bug改一天】，這個話其實不無道理，因為在一些大型項目中，若是出現(xiàn)了一個Bug，因為很多代碼邏輯都是串聯(lián)的，可能你修改了這個Bug，另一個地方又出了Bug，這個時候其實assert斷言其實就可以幫助到我們很多，尤其是對于一些數(shù)組訪問越界、野指針訪問、空指針異常這些，若是你一步步去調(diào)試的話其實是很難找出來的，那用assert就很香了，馬上就給你報出來，而且哪一個【.cpp】文件的哪一行都會告訴你，于是程序員呼：assert實在是太棒了
• 但是對于assert我們真的可以什么地方都使用嗎？當(dāng)然不是，可以看到，我在很多刪除算法的地方一般都會使用到assert，因為指針在不斷前移或者后移的情況下可能造成越界訪問，這個時候就會出現(xiàn)大問題了；還有一點的話就是我們通過找出來的【pos】位置去刪除其之前或之后的結(jié)點，對于這個傳進(jìn)來的【pos】指針可能是一個空指針，我們知道對空指針進(jìn)行操作是很危險的一件事，所以也需要斷言一下；最后一點的話可能就是對于二級指針接收的一級頭結(jié)點指針吧，對于傳進(jìn)來的頭結(jié)點指針我們也需要進(jìn)行一個判斷，尤其是在尾刪或者頭刪鏈表的地方，若是這個鏈表本身就是空的，那么如何對其進(jìn)行一個刪除呢？這其實也是一種對空指針的違法操作。有關(guān)如何斷言的操作我在前面已經(jīng)講過了，如還有不清楚的再去看看
• 所以對于以上可能會出現(xiàn)問題的接口內(nèi)部一開始的地方就要進(jìn)行一個斷言，但是除了這些地方其實有些不需要斷言的地方你要平白無故地加上一個assert在前面，當(dāng)你的同事看到這個斷言的時候就會感到很詫異，例如說在pos位置前后去插入結(jié)點，這其實也沒必要斷言，因為可以進(jìn)行頭插和尾插，是不會出現(xiàn)非法操作的；在開發(fā)的過程中，我們也需要考慮到用戶的不當(dāng)操作，然后作出一些提醒，但是對于像某些場景比如說用戶在刪除一個文件時可能是一時的不當(dāng)操作，這個時候你就需要彈出一個對話框去告訴他是否需要繼續(xù)進(jìn)行操作，再讓他確認(rèn)一下，這樣顯得其實是比較合理的，但若是你直接在這個地方給出一個斷言，判斷用戶執(zhí)行了這個操作就直接報錯，那用戶可能就會被你嚇到了，影響用戶的體驗感
• 所以說對于二級指針和斷言，并不是什么地方都可以使用，我們應(yīng)該在使用之前先做一個考慮和評估，看看在此處使用是否合理，真正地做到【因地制宜】，才能展現(xiàn)出邏輯型更強(qiáng)的代碼🐳

六、OJ題目實訓(xùn)

以下題目請通過我另一個專欄【LeetCode算法題解】觀看📺——題解更新中．<{=．．．．

【LeetCode】21 - 合并兩個有序鏈表

【LeetCode】203 - 移除鏈表元素

鏈接

【LeetCode】206 - 反轉(zhuǎn)鏈表

【LeetCode】876 - 鏈表的中間結(jié)點

【牛客CM】11 - 鏈表分割

鏈接

【牛客JZ】22 - 鏈表中倒數(shù)第k個結(jié)點

七、總結(jié)與提煉

• 最后，我們一起來回顧一下本文所學(xué)習(xí)的內(nèi)容。除題解外，本文大概使用了近四萬字左右的篇幅詳細(xì)講解了單鏈表相關(guān)的知識點
• 首先分析了順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)各自的優(yōu)缺點：對于【順序表】，雖然可以做到隨機(jī)快速訪問，但是對于數(shù)據(jù)的插入和刪除卻很麻煩；對于【鏈表】，雖然在插入和刪除這一塊無需像順序表那樣，只要修改next指針域的指向即可，但是對于鏈表而言不支持隨機(jī)訪問，需要從頭開始一一遍歷才可訪問到需訪問元素
• 接著帶著大家先行去初步了解了有關(guān)鏈表的結(jié)構(gòu)，從邏輯結(jié)構(gòu)和物理結(jié)構(gòu)講到了棧區(qū)和堆區(qū)的存儲原理，進(jìn)一步從底層的存儲加深了對鏈表的了解
• 其次，開始了鏈表的各種接口算法實現(xiàn)，這一部分是最核心，也是最重要的，學(xué)了鏈表，最重要的是要學(xué)會如何去使用，那對于其創(chuàng)建、銷毀、打印以及各種頭插、尾插、頭刪、尾刪等增刪查改操作，其中的核心代碼都是需要牢記心中
• 最后，是帶大家做了一些在線OJ題目，來自【牛客】和【力扣】，這兩個在線OJ網(wǎng)站還是不錯的，推薦給大家，加深對知識的理解和掌握，這部分也是非常重要的，對于算法題，無論是在筆試還是面試中，也是除了基礎(chǔ)知識以外面試官極為看重的一部分，所以大家要早早開始刷題

OK，以上就是本文所要講解的全部內(nèi)容，非常感謝您的觀看，如有問題請于評論區(qū)留言或者私信我🌺

總結(jié)

以上是生活随笔為你收集整理的数据结构 | 单链表SingleList【带你从浅入深真正搞懂链表】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。