明天就是雙十連假了，我還在電腦前撰文
深呼吸告訴自己，是我要選參加鐵人賽的喔！是我！都是我

昨天討論到了陣列的 index 可以記錄資料在主記憶體中的位址，今天要來談跟它有點像的「鏈接串列」

▌鏈接串列（Linked list）

「鏈接串列」中的元素（串列中的資料）可以被放在記憶體中的任何一個空位

「鏈接串列」在存放每個元素的同時，就會「紀錄下一個元素的存放位址」，所以能夠以「位址」依序找到每個串列中的「存取元素」，可以想成是我用地址找到你家。當今天我們要存一筆資料時，就必須要佔用到記憶體的空間，「鏈接串列」會依照記憶體中哪裡有空位，就把資料給塞進去，十分的彈性，塞進的位置有可能會在目前節點的前方或後方

在上一篇我們可以發現 C 語言在宣告陣列時，需要先指定每列和每行有幾個元素，也就是你得需要知道資料的大小，但這樣其實要動態新增、刪除元素時，是件很麻煩的事，但「鏈接串列」就不需要遵守這個規則

▪ 鏈接串列的特點：

• 是由一個個節點（Node）所組成的，每個節點的tpye不必相同
• 每一個節點裡會存下一個節點的指標（Pointer）
• 不按照順序排列、儲存（非連續）
• 充分利用電腦記憶體空間
• 新增、刪除元素很方便，彈性度高
• 存取速度比陣列慢，因要先讀取指標
• 並非所有程式語言都有，像JS就沒有內建 Linked List，可以使用這個 link list 第三方套件擴充

▪ 什麼時候適合使用鏈接串列？

資料存取的方式有兩種

• 依序存取（Sequential Access）: 也是逐一存取，依照第一個元素開始依序存取
• 隨機存取（Random Access）：依照資料的「index」 來存取

看到這應該可以猜想到鏈接陣列是哪一從存取方式了
那就是「依序存取」！

假設今天我們要存取鏈結串列的第五個元素，必須要先依序訪問前面四個元素，得到節點指標後，才能找到第五個元素

所以「鏈接串列」的使用時機是需要「逐一存取元素」時！讀取一個元素後，再依照位址讀取下一個元素，如果沒有要依序讀取，可以選擇使用「陣列」Array。此外，鏈結串列也會用來構建許多其它資料結構，像是之後會提到的堆疊（Stack），佇列(Queue)等（這是非常重要的觀念，前端面試中很常考）

P.S 陣列就是「隨機存取」，在實務上的應用比較廣

▌資料的操作 - 新增

這裡先拿自己比較熟悉的JS舉例

const foodList = ['pasta', 'coffee', 'pizza', 'chocolate']

如果你今天想要在 'coffee' 和 'pizza' 中間插入 'shushi'，你會選用「陣列」還是「鏈接串列」？

答案是「鏈接串列」！！
原因是如果選用陣列，就必須要在插入 'shushi' 後的所以元素都往後移，如果沒有記憶體空間可以移，就必須換到其他位子，十分的麻煩。用「鏈接串列」只需要修改前一個元素（也就是'coffee' ）中記錄的下一個節點指標即可

突然覺得「陣列」、「鏈接串列」分別有點像一般筆記本和活頁式筆記本，一般筆記本頁數都是固定的，也代表書寫空間有限，今天突然心血來潮想在某頁之間插入新頁是很麻煩的！但是活頁式就可以看我想在哪新增就在哪，方便許多

▌資料的操作 - 刪除

如果你今天想要把 'pizza' 移除，你會選用「陣列」還是「鏈接串列」？

答案還是「鏈接串列」
因為只要修改前一個節點中所存下的節點指標就可以了！反觀「陣列」在刪除 'pizza' 後，還要把後面的所有元素我前挪動。與「新增」不同的是，「刪除」並不會遇到「記憶體空間不足」而失敗的問題

▌總結

「鏈接串列」和「陣列」有一個很大的不同，就是鏈接串列的「邏輯順序」和「實體順序」可能不同，也就是它的 index 不一定是 0, 1, 2... 由小到大排列，因其不連續性，我們可利用「鏈接串列」來儲存不確定大小或會動態刪減的資料，以下是「陣列」和「鏈接串鍊」的比較表

▌參考資料

1. 白話演算法！Aditya Y. Bhargava 著
2. wikipedia