一、單鏈表的概念和結構

1、單鏈表的概念：

鏈表也是屬于我們的線性表中的一種，其物理結構上是不一定連續的，但是邏輯結構上是一定連續的，所以其是沒辦法像前面的順序表一樣通過++找到下一個元素的，其是通過指針來找到下一個元素的。

好比如，我們平時坐的火車，我們會發現火車也是有長有短的，當平時人少的時候，我們火車的車廂數量就會少一點，然后到節假日的時候，那么此時的火車車廂數量就會增加，火車每個車廂處是會有一個節點來鏈接的，然后我們要想走到后面的車廂 ，是必須要經過前面的車廂才可以。

如下所示：

我們的鏈表其實大致也是這樣，其由兩個部分組成，一個是要存儲的數據，還有一個是指向下一個節點的指針。

如下所示：

?2、單鏈表的節點：

和前面學習的順序表不太一樣的是，我們的鏈表中的每個節點都是單獨申請空間的，節點中主要由要存儲的數據和指向下一個節點的指針構成，這樣我們就可以通過這個指針來找到下一個節點的數據了，但不能從后一個節點找到前節點的。

還有就是這個指針變量，并不是要存儲的數據類型的指針變量，因為我們要這個指針指向的是下一個節點，那么其類型就應該是節點類型。

下面我們看看單鏈表的節點是如何進行定義的：

那么我們上面定義的節點中，其是用來存放整型數據的，所以第一個成語是要存儲的數據，然后第二個成員要指向下一個節點的指針，那么有的同學可能會認為是int*，因為我們存儲的數據類型是int類型的，但是我們別忘記了，我們指向的是節點，節點中不僅有這個存儲的數據，還有指向下一節點的指針，所以其類型有應該是結構體指針，也就是節點類型指針即：struct? SListNode*類型的指針。

然后因為我們對于存放的數據可能會有不同，那么這里我們使用typedef關鍵字定義一個類型，到后面我們要是需要其他類型的直接對這個定義進行修改即可。

3、單鏈表的性質：?

• 鏈表是無序的結構，其在邏輯結構上是連續的，在物理結構上是不一定連續的。
• 節點一般是一個一個申請的空間，不是一塊進行申請的，其在堆上進行申請的，我們使用malloc函數進行申請。
• 我們在堆上申請的空間是不知道連續不連續的，所以節點在內存中是不一定連續的
• 要訪問鏈表中的元素時，我們只需要知道鏈表的頭節點即可，根據節點中存儲下一節點的指針變量可以找到下一節點的數據。所以我們一般會專門使用一個指針變量來存儲鏈表的頭節點。

二、實現單鏈表?

1、定義一個單鏈表

下面我們先是實現對一個單鏈表的創建，這次我們創建一個頭文件SList.h頭文件來定義好這個單鏈表的結構。

?2、單鏈表的節點申請

我們鏈表的申請和順序表的申請是有很大的不同的，首先我們順序表中是直接申請一塊空間，我們的鏈表是需要存儲數據的時候再進行申請對應大小的空間，所以我們的節點申請的時候，是需要將要存儲的數據進行輸入的，所以函數的參數應該為要存放的數據的類型，然后我們進行空間的申請，申請的空間的大小應該為一個節點的大小，然后我們使用一個指針變量來接收，然后再使用if語句進行判斷其空間是否申請成功，如果不成功就使用perror來判斷其內沒有申請成功的原因。

然后我們使用就將這個要存儲的數據存儲進這個節點，然后將這個節點指向下一個節點的指針置為NULL。

然后再將這個節點返回即可。

3、單鏈表數據的訪問

我們的訪問主要是想將鏈表的內容打印到屏幕上，看看鏈表的情況是否按照我們想要的方向去走。

前面我們對于順序表的打印，主要是通過++進行，這是因為順序表在物理結構上是連續的，其是挨著存放的。現在我們對于單鏈表，我們在定義的時候有講到，我們可以通過當前的節點找到下一節點，我們就可以從這個鏈表的頭節點開始往后找，就可以找到所有的數據元素。

我們函數名字取為：SLTPrint，然后我們需要從頭節點開始找，所以我們要傳入的參數也應該為一個指針，那么我們可以創建一個指針變量，用來存儲我們的頭節點，然后使用一個循環，只要這個指針變量不為空，那么就可以打印數據，但是還有個問題就是我們這個指針變量是指向頭節點的，然后我們要是對其進行賦值下一節點的地址，由于我們是地址傳遞的，那么其形參的改變是會造成實參的改變的，那么我們就可以在函數體內部創建一個節點類型的指針變量來替代這個頭節點進行下一節點的尋找。

然后當其為NULL的時候，就說明我們的鏈表已經打印完成，然后這個臨時的指針變量不用理，當這個函數執行完后，編輯器會自己釋放的。

函數實現如下：

我們來鏈表打印完后，再進行打印一個NULL表示當前的鏈表數據已經完全打印出來，或者當當前鏈表為空表的話，那么就表示當前鏈表是個NULL的表。

4、 鏈表的頭插和尾插

頭插：

在對于鏈表的創建中，我們就是使用一個指針變量phead節點指針來指向這個鏈表的頭節點， 最開始對其置為NULL，而且不需要進行初始化操作，每個節點在創建的時候就已經輸入了數據了。

頭插就是將這個節點變成這個鏈表的頭節點，那么指向頭節點的指針變量就變成指向這個要插入的節點，然后我們插入的這個節點，其成語中指向原來的頭節點。·

那么細心的同學就會發現了，我們這里要改變的值，是地址，是一個指向節點的地址，是一個一級指針，那么我們在傳參數的時候，就需要使用到二級指針了，這樣才可以達到形參的改變會影響實參。

然后因為其傳入的參數是一個指針，那么我們在函數的開頭也是需要對其進行一個斷言。

函數實現如下：

?我們可以看到鏈表的頭插的時間復雜度為O(1)。

尾插：

尾插就是在鏈表的尾部進行插入數據，那么我們就需要找到鏈表的尾部才可以進行插入，其是尾插也很好理解，就是讓當前鏈表的最后一個節點的指向要插入的節點的指針，然后要插入的這個節點指向下一節點的指針為NULL即可。

但是我們也要考慮到一個特殊情況，那么就是當前的鏈表是一個空鏈表的情況，那么此時我們的鏈表就不存在尾節點，那么就是我們當前要插入的節點變成這個鏈表的頭節點。

那么對于這種情況，我們直接讓這個指向頭節點的指針指向這個要插入的節點，那么我們可以使用一個if語句。

然后如果不是空鏈表，那么我們創建一個指針變量來代替保存著頭節點的指針變量往后找到鏈表的尾節點，然后進行尾插。

那么我們使用一個while循環往后找，直到我們這個指針當前的位置在尾節點的時候，也就是這個節點的next指針變量為NULL的時候結束往下找，然后對其進行修改，使其指向要插入的節點，然后要插入的節點的next指針要為NULL。

函數如下：

5、鏈表的頭刪和尾刪?

頭刪：

頭刪就是將當前的頭節點從鏈表中刪除，那么其該如何進行刪除呢？

那么我們就需要將頭節點的這個空間進行釋放，還給操作系統，然后第二個節點就順位成為頭節點，那么我們也需要找到第二個節點。那么我們需要先找到第二個節點才行，那么我們先創建一個指針變量來存儲當前頭節點的地址，然后將指向頭節點的指針指向下一節點。然后再對這個空間進行釋放。 然后我們是要對指向頭節點的指針進行修改，那么我們要使用二級指針來接收。然后就是我們不能傳一個空表進來，空表的話沒有東西可以進行刪除。那么我們對指向頭節點的指針進行斷言。

函數實現如下：

尾刪：

尾刪很好理解的，前面我們已經寫了尾插了，其也是一樣，首先我們要找到尾節點，然后才可以對其進行釋放，那么我們就需要進行遍歷，找到尾節點，那么我們創建一個指針變量來進行遍歷，對其賦值為頭節點的地址。然后找到尾節點后，我們對其進行內存釋放，然后其前一個節點就成為了尾節點了，那么其指向下一個指針的指針變量也要指向NULL，那么我們再

是不是這樣呢？我們下面寫一下看看：

當我們的鏈表只有一個節點的時候呢？那么此時的鏈表其首節點也是尾節點，此時尾節點的前面是沒有節點的，那么我們前面要找其前一個節點，對其是不成立的。那么我們可以分情況進行操作，對于其只有一個節點的情況就特殊處理。

正確代碼：

?

6、查找指定節點?

查找指定節點，不用進行啥操作，就是進行查詢，那么我們很容易就想到的遍歷，然后看看能不能找到想要的數據即可。要是找到，就返回其對于的節點，如果沒有找到那么就返回一個空。那么我們要創建一個指針變量來進行遍歷。

然后這個功能是不需要對實參進行修改的，那么我們這里的參數就不需要使用到二級指針了。

7、指定位置刪除和插入?

指定位置的刪除和插入，我們要搭配上面的查找指定節點的函數進行使用，我們使用查找指定節點的函數找到我們要插入的位置，或者刪除的位置，然后進行操作。

刪除指定節點：

刪除鏈表中指定位置的節點，我們首先使用上面的查找函數進行查找，然后使用一個節點類型指針來接收這個地址，然后我們要刪除這個節點，那么這個節點前面的節點嗎，其指向下一個節點的指針就需要指向這個要刪除的節點的下一個節點。然后我們再看兩個特殊的位置，就是尾節點和頭節點，尾節點的話，我們刪除后，其前一個節點指向的確實NULL。

那么我們再看看頭節點，我們前面提到要將這個要刪除的節點的前節點指向下一個節點，但是我們的頭節點是沒有前節點的，那么這個是矛盾的，那么我們就可以特殊處理一下。然后我們前面寫了一個頭刪，所以這個情況我們直接使用頭刪除即可。

在指定位置之前插入：?

我們要在指定節點前插入數據，那么我們就需要得到指定位置前的地址，但是我們的鏈表是沒辦法直接得到前一個節點的地址的，那么我們就可以通過頭節點來找到，即可這個節點的下一節點為pos的時候就找到了，然后我們讓這個節點的指針變量指向要插入的節點，然后這個插入的節點指向指定的這個位置。

但是我們和上面一樣，這個指定位置前插入數據要有前節點才可以，那么我們要是指定的位置是頭節點前，那么這個邏輯就矛盾了，那么我們就特殊處理這個情況即可，當這個指定的節點是頭節點的時候，那么就是我們的頭插了，那么我們調用頭插函數即可。

函數實現如下：

?在指定位置之后插入數據：

在指定的位置之后插入數據，那么我們就將這個指定的位置指向下一個節點的指針指向這個要插入的節點，然后這個插入的節點要指向這個指定位置的后一個節點，那么我們的順序是如何呢？

我們應該先讓這個要插入的節點指向下一個節點的指針指向這個指定位置的下一個節點，這是因為我們要是先使這個指定位置指向下一節點的指針指向了這個要插入的節點，那么我們要找這個指定位置的一下節點就找不到了。

然后對于尾節點這個特殊位置，我們尾節點后面的節點為空，這個直接插入是可以的。

8、鏈表的銷毀

在上面我們實現了一系列對于鏈表的操作，那么我們使用完這個鏈表后，就得將這個鏈表進行銷毀吧，提高空間的利用效率。那么我們的鏈表是如何進行銷毀的呢？前面我們的順序表，是可以直接使用一個free進行釋放，這是因為其物理結構是連續的，其是在內存中使用的是一塊連續的空間的。

但是我們的鏈表并不是，其是每個節點獨立進行空間的申請的，其物理結構是不連續的，所以我們的鏈表的銷毀，就需要直接進行遍歷，然后對其進行釋放，我們釋放好一個后，就繼續下一個節點的釋放，直到釋放好全部節點，那么我們在釋放節點前，先將其指向下一個節點的指針變量指向的地址使用一個節點類型指針來存放，這樣才可防止當前的節點釋放后能夠順序找到下一節點。

?在銷毀完后，不要忘記給指向頭節點的指針變量置空，防止其成為野指針。