【資料結構&演演算法】連結串列特性淺析

1.底層儲存結構

• 陣列需要一塊連續的記憶體空間來儲存， 對記憶體的要求比較高。如果我們申請一個 100MB 大小的陣列，當記憶體中沒有連續的、足夠大的儲存空間時，即便記憶體的剩餘總可用空間大於 100MB，仍然會申請失敗。
• 而連結串列恰恰相反，它並不需要一塊連續的記憶體空間，它通過「指標」將一組零散的記憶體塊串聯起來使用，所以如果我們申請的是 100MB 大小的連結串列，根本不會有問題。

2.連結串列分類

2.1 單連結串列

將所有的結點串起來，每個連結串列的結點除了儲存資料之外，還需要記錄鏈上的下一個結點的地址。如圖所示，我們把這個記錄下個結點地址的指標叫作後繼指標 next。

• 頭結點 & 尾結點

  • 我們習慣性地把第一個結點叫作頭結點，把最後一個結點叫作尾結點

  • 頭結點用來記錄連結串列的基地址。有了它，我們就可以遍歷得到整條連結串列

  • 尾結點特殊的地方是：指標不是指向下一個結點，而是指向一個空地址 NULL，表示這是連結串列上最後一個結點

• 哨兵節點：為了操作的便利，有時會將頭結點設定為一個儲存資料為null的節點

2.2 迴圈連結串列

迴圈連結串列是一種特殊的單連結串列。實際上，迴圈連結串列也很簡單。它跟單連結串列唯一的區別就在尾結點。

• 單連結串列的尾結點指標指向空地址，表示這就是最後的結點了。
• 迴圈連結串列的尾結點指標是指向連結串列的頭結點。它像一個環一樣首尾相連，所以叫作「迴圈」連結串列
  

2.3 雙向連結串列

雙向連結串列需要額外的兩個空間來儲存後繼結點和前驅結點的地址。所以，如果儲存同樣多的資料，雙向連結串列要比單連結串列佔用更多的記憶體空間。雖然兩個指標比較浪費儲存空間，但可以支援雙向遍歷，這樣也帶來了雙向連結串列操作的靈活性。

從結構上來看，雙向連結串列可以支援 O(1) 時間複雜度的情況下找到前驅結點，正是這樣的特點，也使雙向連結串列在某些情況下的插入、刪除等操作都要比單連結串列簡單、高效。

2.4 雙向迴圈連結串列

3.操作時間複雜度分析

3.1 插入 & 刪除（理論）

• 在進行陣列的插入、刪除操作時，為了保持記憶體資料連續性，需要做大量的資料搬移，所以時間複雜度是O(n)
• 在連結串列中插入或者刪除一個資料，我們並不需要為了 保持記憶體的連續性而搬移結點，因為連結串列的儲存空間本身就不是連續的。所以，在連結串列中插入和刪除一個資料是非常快速的。我們只需要考慮相鄰結點的指標改變，所以對應的時間複雜度是 O(1)

3.2 插入 & 刪除（實際）

插入和刪除實際上有以下兩種情況：

• 刪除「某個給定值」的結點 == 插入節點到給定值後
  • 不管是單連結串列還是雙向連結串列，為了查詢到值等於給定值的結點，都需要從頭結點開始一個一個依次遍歷對比，直到找到值等於給定值的結點，然後再通過我前面講的指標操作將其刪除。
  • 儘管單純的刪除操作時間複雜度是 O(1)，但遍歷查詢的時間是主要的耗時點，對應的時間複雜度為 O(n)。根據時間複雜度分析中的加法法則，刪除值等於給定值的結點對應的連結串列操作的總時間複雜度為 O(n)
• 刪除給定指標指向的結點，即要刪除node已經給定 == 插入給定node後
  • 單連結串列：我們已經找到了要刪除的結點，但是刪除某個結點 q 需要知道其前驅結點，而單連結串列並不支援直接獲取前驅結點，所以，為了找到前驅結點，我們還是要從頭結點開始遍歷連結串列，直到 p->next=q，說明 p 是 q 的前驅結點。所以，單連結串列刪除操作需要 O(n) 的時間複雜度
  • 雙向連結串列：因為雙向連結串列中的結點已經儲存了前驅結點的指標，不需要像單連結串列那樣遍歷。所以，雙向連結串列只需要在 O(1) 的時間複雜度內就搞定了

3.3 隨機存取

• 連結串列要想隨機存取第 k 個元素，就沒有陣列那麼高效了（根據首地址和下標，通過定址公式就能直接計算出對應的記憶體地址）
• 連結串列中的資料並非連續儲存的，需要根據指標一個結點一個結點地依次遍歷，直到找到相應的結點。
  • 單連結串列：從頭到尾進行遍歷
  • 雙向連結串列：我們可以記錄上次查詢的位置 p，每次查詢時，根據要查詢的值與 p 的大小關係，決定是往前還是往後查詢，所以平均只需要查詢一半的資料

4.連結串列 VS 陣列

4.1 操作時間複雜度

	陣列	連結串列
插入刪除	O(n）	O(1)
隨機存取	O(1)	O(n)

4.2 cpu快取預讀

• 陣列簡單易用，在實現上使用的是連續的記憶體空間，可以藉助 CPU 的快取機制，預讀陣列中的資料，所以存取效率更高
• 連結串列在記憶體中並不是連續儲存，所以對 CPU 快取不友好，沒辦法有效預讀

4.3 動態擴容（重點）

• 陣列的缺點是大小固定，一經宣告就要佔用整塊連續記憶體空間。
  • 如果宣告的陣列過大，系統可能沒有足夠的連續記憶體空間分配給它，導致「記憶體不足（out of memory）」
  • 如果宣告的陣列過小，則可能出現不夠用的情況。這時只能再申請一個更大的記憶體空間，把原陣列拷貝進去，非常費時
  • 雖然ArrayList底層實現了動態擴容，但假設ArrayList 儲存了了 1GB 大小的資料，這個時候已經沒有空閒空間了，當我們再插入資料的時候，ArrayList 會申請一個 1.5GB 大小的儲存空 間，並且把原來那 1GB 的資料拷貝到新申請的空間上
• 連結串列本身沒有大小的限制，天然地支援動態擴容，我覺得這也是它與陣列最大的區別

4.4 記憶體利用率

• 一般情況下連結串列可以動態擴容所以比一般陣列記憶體利用率高。但若陣列在已知要儲存元素多少的情況下初始化，記憶體很少會被浪費，陣列更優
• 連結串列不適用於記憶體要求嚴苛的場景
  • 連結串列中的每個結 點都需要消耗額外的儲存空間去儲存一份指向下一個結點的指標，所以記憶體消耗會翻倍。但是對於比較大的Node，這點存指標的記憶體可以忽略
  • 對連結串列進行頻繁的插入、刪除操作，還會導致頻繁的記憶體申請和釋放，容易造成記憶體碎片，如果是 Java 語言，就有可能會導致頻繁的 GC（Garbage Collection，垃圾回收）