連結串列基礎複習：陣列連結串列和陣列的作用相同。都是用來儲存資料。因此，使用陣列和連結串列進行類比是一個不錯的選擇。 陣列是很常用的資料結構。在多數語言中，我們都可以很容易的宣告一個數組型別，並使用 [] 符號取出其中的元素。 C 語言的示例如下：

在此不再贅述。 陣列存在如下缺點： 陣列的大小總是固定的。儘管在 C99 中提供了 VLA ，以及可以使用 reaclloc() 進行動態記憶體分配。但是那樣需要很強的技術。真的猛士，敢於直面慘淡的手動管理記憶體，敢於正視淋漓的 errors。 —— 魯迅因為 1 的問題，大多數普通程式設計師在新建陣列時候總是會偷懶選擇一個足夠大的數量，保證資料都能被存進去。但是這樣就會造成兩個問題，其一就是空間的嚴重浪費，再就是當資料規模真的超過我們預先定義的資料規模時整個程式就會出現問題，輕則某個模組停止執行，重則當場死給你看。在陣列的頭部插入資料的代價過大。和陣列一樣，連結串列也有自己的優點和缺點。但是連結串列在陣列具有缺陷的地方卻恰好很強大。兩種資料結構的特徵來自於他們的儲存策略：陣列是一次分配完全部記憶體，而連結串列則是在需要時再分配記憶體。 連結串列的概念建立陣列時，我們會直接分配出所有我們需要的記憶體。但是對於連結串列，我們每次只分配出一個節點（node） 的記憶體。連結串列使用指標將各個節點組合到一起，這樣就形成了一個連一個的鏈式的結構，這就是連結串列（Linked List）這個名稱的由來。 連結串列的每個節點都有兩個部分：資料區和指標區。前者用來儲存資料，後者用來儲存指向下一個節點的指標。我們使用 malloc() 函式來為每個節點分配記憶體。節點的頭部只含有指向第一個節點的指標。如下是一個數據為{1,2}的連結串列。 其中，儲存在棧區的 head 指向了儲存在堆區的節點。堆區的節點又互相連線，形成鏈狀的結構。最後一個節點的指標區被賦值為 NULL，標明瞭連結串列的結束。因為上圖的連結串列儲存了兩個節點，所以該連結串列的長度為 2。長度為 0 的連結串列，或者說叫空連結串列，通常以 NULL 指標表示。空連結串列是連結串列操作的最常見的一個邊界條件，本文所述程式碼肯定是能完美處理這種條件的。當讀者在自己實踐時，考慮這種狀況是一種很有益處的思維訓練。 連結串列結構在我們開始討論程式碼實現時，我們需要定義一些結構。 本文中的定義如下： 這裡使用到了 C 語言的結構體的自引用（Self reference），就是在結構體內部，包含指向自身型別結構體的指標。 注意： 本文中程式碼並未處理 函式執行失敗時的錯誤處理，在實際使用時是需要進行處理的。 示例下面是生成上文提到的連結串列的具體函式： 練習使用最少的等於號生成上文那樣的資料結構。我們需要兩個等於號呼叫 malloc()，兩個用來儲存資料，還有三個用來設定連線關係。但是使用一點小技巧，我們能將等於號的數量降到 5 個。 建立連結串列上一部分提到的 函式就是很好的建立連結串列的示例。根據那個函式，我們可以抽象出建立連結串列的幾個基本操作： 分配記憶體儲存資料處理指標基於此，不難寫出建立一個只有一個節點的連結串列的函式，示例如下： 連結串列的基本操作本節介紹的是連結串列的基本操作。 1. 遍歷連結串列對於連結串列，最常見的操作就是遍歷連結串列。比較常見的實現方法是使用 語句實現：首先將頭指標 (head) 複製到臨時變數 裡。使用 測試 是否為空指標，最後在迴圈體裡移動指標。示例如下： 也有很多人使用一個 迴圈來簡化步驟（比如懶人如我）… 2. 在連結串列結尾新增資料除了遍歷連結串列之外，最常用的操作就是新增和刪除資料了。下面的幾個操作都是新增/刪除資料。 首先我們來看在連結串列的結尾新增資料。要想在連結串列的結尾新增資料，我們要做的事情有如下幾件： 找到連結串列末尾的節點新建節點，儲存資料，處理指標在將連結串列的結尾指向剛剛新建的節點以下是程式碼示例： 使用 current 而不是直接改變 head 的原因： 筆者不習慣直接修改（滑稽） 下面以向連結串列 {1,2} 的結尾新增資料 3，為例演示全過程。 首先是最初的連結串列： 第一步完成之後： 第二步： 第三步： 在函式呼叫者的視角里，連結串列變成了這樣： 就這樣，一個全新的連結串列就誕生了！ 3. 在連結串列結尾刪除資料刪除資料和新增資料有著一定的共性，因此筆者將刪除資料和新增資料放在一起說明。 與新增操作類似，刪除操作要做的又如下幾步： 找到連結串列倒數第二個節點（因為需要修改這個節點的next為 NULL）刪除其下一個節點修改 next 為 NULL根據步驟我們可以寫出 C 程式碼,需要注意的是這次我們需要處理連結串列長度為 1 的特殊情況： 第二步： 第三步： 需要注意的是我們在這裡傳遞的是連結串列頭結點指標的指標，因為我們需要修改頭指標的數值為 NULL。 4. 在連結串列頭部新增資料在頭部新增資料不是很難，步驟如下： 新建節點，儲存資料讓新建節點的 next 指向之前的頭節點將頭節點指標指向剛剛新建的節點。程式碼如下： 下面演示在連結串列 {1,2} 的前面插入資料 0： 第一步： 第二步： 5. 在任意節點新增刪除資料在任意節點（不考慮頭節點和尾節點）新增資料的步驟： 新建節點，儲存資料找出要添到的節點的上一個節點的位置（記為 P）將新建節點的 next 修改為 P 的 next 值將 P 的 next 修改為新建節點的位置在任意節點（不考慮頭節點和尾節點）刪除資料的步驟： 找出要刪除的節點的上一個節點的位置（記為 P）記錄下要刪除的節點的位置將 P 的 next 值修改為要刪除的節點的 next 指標的值釋放記憶體這兩個操作的實現請讀者自己嘗試實現。 連結串列的其他幾種實現方式除了上面所述的最基礎的連結串列之外，還有很多種進行過改動的連結串列實現方式。每種方式都有各自的優點。不過，在關心魔改版實現之前，最好好好理解基礎的連結串列知識，確保你能理解之後再繼續前進。 空頭列表 為了防止再連結串列為空時出現頭指標為 NULL 的情況。這種連結串列採用了一個沒有資料只有指向 NULL 的指標的節點標誌連結串列為空。這種的好處就是對於 Push 那種操作，我們不需要傳遞指標的指標進去。而且一些迭代操作的進行會比較簡單。缺點就是會浪費記憶體空間。再就是有些演算法的實現不怎麼優雅。環狀連結串列 將尾指標的.next欄位設為頭指標的連結串列。指向任何一個節點的指標都可以被視為頭指標。雙向連結串列 在連結串列的結構裡新增一個 prev 欄位，指向上一個節點。這種連結串列插入/刪除元素需要的操作比較多。但是其他操作都被大大地簡化了。塊連結串列 在一個連結串列節點記憶體儲多個數據。