鏈結陣列(Linked List)是基本資料結構之一，與陣列相同，都是按照順序儲存資料，但它們內部連接資料的方式並不相同，因此它們適用於不同的情境。

Introduction

鏈結陣列的結構與陣列最大的差異是，鏈結陣列每個節點(Node)裡面並不是只有儲存資料(Value)，還有儲存下一個節點的位置(Next)，如下圖所示：

這就是所謂的單向鏈結陣列(Singly Linked List)，第一個指向第二個，第二個指向第三個，直到沒有下個值(Null)；不過，既然有單向也會有雙向，雙向鏈結陣列(Doubly Linked List)在之後的篇章才會介紹。

訪問鏈結陣列中的元素

與陣列不同，鏈結陣列創建時並不會在記憶體挖取一個確定大小的空間存放資料，而是透過每個節點指向下一個節點的位置，因此若要訪問鏈結陣列中的元素只能從頭開始找起，至少是個O(n)時間的查詢操作。

新增

單看查詢操作的話可能會覺得鏈結陣列很廢，不過它的強項是在於新增和刪除，新增只需要三個步驟。

以前一個段落的鏈結陣列為例，將10新增至索引1的位置：

1. 建立一個新的節點(10)，並移動到指定索引-1的位置(4)。
2. 設定新節點(10)的下一個節點為原本索引位置的節點(2)。
3. 而指定索引-1位置(4)的節點設定下一個節點位置為新節點(10)。

如此一來，就將新節點(10)新增至索引1的位置，並且新增節點的時間複雜度僅為O(n)，不需要像陣列一樣，將後續的全部元素往後移動。

刪除

新增需要三個步驟而刪除更少，刪除僅需要兩個步驟。

繼續以第一個段落的鏈結陣列為例，將索引1的節點刪除：

1. 移動至指定索引位置(2)，並暫存前一個節點資料(4)。
2. 將前一個節點(4)的下一個節點位置指向指定索引的下一個節點(8)。

這樣兩個步驟就將原本索引1的節點(2)給移除掉了，下次查詢索引1的節點就會變成原本索引2的節點(8)，這個時間複雜度也是O(n)，也不需要將後續的全部元素往前移動。

小結

我們總結一下鏈結陣列的特點：

1. 各節點的資料型態可以不相同。
2. 每個節點的記憶體位置並不一定連續。
3. 因為記憶體位置不連續，因此也不用事先設定陣列長度。
4. 每個節點都會指向下一個節點位置。
5. 僅有指向下一個節點位置的是單向，若有指定前後節點位置的是雙向。
6. 能夠被直接存取的節點只有最前面的第一個節點。

參考資料

Explore - LeetCode