TS 學資料結構與演算法 (資料結構篇) — 鏈結串列 Linked List
眼尖的讀者可能會發現，之前不是 ”JS“ 學資料結構與演算法嗎？怎麼變成 “TS” 了？原因其實很簡單，自從使用 TS 進行開發後，就被強型別的特性深深吸引了，在開發應用時也在 compile time 就避免很多原先用 JS 在 run time 才會發現的錯誤。而這系列的主題 —資料結構篇，往往會使用物件導向的概念來實作資料結構，因此更能體現 TS 的美好，因此之後的篇章將使用 TS 來開發。
鏈結串列是什麼？
想必每個對程式開發有一定了解的人不管使用什麼語言，都對陣列（List）相當熟悉吧。而鏈結串列其實跟陣列有一點點的相似，都是用來儲存資料的資料結構。然而不同於陣列的是，鏈結串列的元素在記憶體當中並不是連續的。由文章開頭的圖片中可以看到，鏈結串列的每一個元素是由資料與指標（pointer）所組成，資料很單純，就是儲存的資料，指標則是指向下一個元素，當元素數量一多，即便各元素在記憶體中是不連續的，也能透過指標串連起來，因此才會得出鏈結串列這個名稱。
鏈結串列的優點
- 元素在記憶體中可以不連續：因占用連續的記憶體空間可能會浪費不必要之記憶體，因此鏈結串列在某些狀況下會比陣列還節省記憶體空間。
- 方便動態刪除或插入新元素
- 各節點資料型態不必一定相同
鏈結串列的缺點
- 資料容易遺失（指標若斷裂，資料就會遺失）
- 循序存取速度較慢（因需要先讀取指標）
鏈結串列的種類
鏈結串列其實擁有非常多種類，而文章開頭的圖片其實是最基本的單向鏈結串列。一般來說，鏈結串列的種類有以下幾種：
單向鏈結串列
雙向鏈結串列
迴圈鏈結串列
塊狀鏈結串列
然而本篇文章旨在介紹鏈結串列的基本概念與基本特性實作，因此將以“單向鏈結串列”為範例。
鏈結串列的 properties 與 methods
properties:
head: 代表串列中最頭的元素
tail: 代表串列的尾元素
每個串列節點則包含本身的 Vaule 與 next(指向下一個元素)
length: 紀錄鏈結串列的長度
methods:
append: 在鏈結串列最尾端加入新的元素
prepend: 在鏈結串列最開頭加入新的元素
printArray: 返回整個鏈結串列
insert: 插入元素到鏈結串列的特定位置中
traverseToIndex: 返回特定 index 的元素
remove: 移除串列中特定元素
程式碼實作
雖然要明確指出在 coding 日常中到底哪裡會使用到 Linked List 還蠻抽象的，但它的確是一個重要的資料結構，之後介紹 queue 與 stack 也會以 Linked List 為基礎實作，最後附上一個連結，原來 React 的底層也有使用 Linked List 實作呢！
