開始之前
因最近正在複習資料結構(基本上就是重新學習了吧😂)，希望能把一些比較重要的部分記錄下來，並在撰寫文章的過程中讓自己的記憶更加深刻。以下會盡量使用 ES6 的語法來創建資料結構的實例，當然也會有思慮不周的部分，還請大家多多留言指教！
Intro
Linked list 鏈結串列，是一種動態的資料結構，相對於 Array 陣列，不需連續的記憶體空間即可儲存，對於資料的操作成本較低；然而若欲取得其中某一節點 Node 上的資料，則必須從頭開始遍歷查找。
Practice
由上圖可知，一個串列中存在多個 Node 結構，且 HEAD 會指向第一筆資料；而 Node 結構中由 Item 存儲資料，Next 負責指向下一筆 Node。故我們創建一個 Linked list 的 Class 思路為：
- 鏈結串列有起始位置
head，亦即串列中第一筆 Node。 - Node 節點以
item存放資料。 - Node 節點以
next作為指標，指向下一個 Node。 - 為 List 加入一些參數如
length，便於後續操作。
節由以上整理我們可以先開始創建符合需求的 ES6 Class：
有了 Class 後必須有對應的方法來操作資料(ex: Array.push())，以下會依序實作(1)新增，(2)刪除，(3)插入。
(1) 新增 (append)
新增資料通常我們會串連至 Linked list 的尾部，也就是 append 一個節點。若為串列的第一筆資料，將串列的 head 指向新增的 Node 即可；其它則需透過遍歷找到尾部的 Node 再加入。故我們可以在 Linked list 中新增一個 method append：
首先判斷是否為第一筆資料，將串列的 head 指向新增的 Node；若否則利用 while loop 判斷遍歷的節點找到最後一個 Node (也就是上例的tail)，再將其上的 next 欄位指向新的資料。另外也別忘記將 List 的長度往上加一(this.length++)。
(2) 指定位置移除(removeAt)
給定一個 index 移除資料，如同新增的步驟，先判斷移除的項目是否為第一筆，若是，則將 head 指向第二筆資料；若否，則遍歷找到該 index 下的 Node ，移除的操作即是將前一個節點之 next 欄位指向下一個節點。
removeAt 的 method 如上例，需注意的是 current 及 prev 兩個變數的使用；透過他們我們可以對遍歷到的節點進行暫存，到達指定 index 時將 next 的指向置換即可。操作的結果如下：
// a new linked list
let ln = new LinkedList(); // append items
ln.append('1');
ln.append("2");
ln.append("3");// remove item in index 1
ln.removeAt(1);// out print of ln
{
"length":2,
"head": {
"item":"1",
"next":{
"item":"3",
"next":null
}
}
}
(3) 指定位置插入(insert)
插入的操作同樣和刪除很像，除了判斷是否為第一筆外，透過遍歷找到我們給定的 index 位置，並利用 prev current 等變數輔助，改變 next 指向就好囉。
Leet code
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
在 Leet code (2) Add Two Numbers 中，題目給予兩個不為空的串列，分別代表兩個非負整數，其數字的“位數”是反向儲存的 (2→ 4→ 3, 代表342)。最後將兩個串列中數值相加後，以同樣的型式回傳這個串列(其實這個reverse order個人覺得挺陷阱的😂，畢竟我們在處理時只要按照同樣的順序處理，也不太需要擔心👍)。
Example:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
這邊解題的思路為：
- 遍歷兩個 Input，每個位數互相加總。
- 注意是否有進位，需在下一筆資料加上。
- 兩個 input 有可能長度不同
(ex: 123, 45)，只要還遍歷的到任一 Input 存在就必須進行加總(ex: 1+4, 2+5, 3+0)。
以上文章簡略以 ES6 Class 實作了 Linked list 物件，除了上述的方法，我們也可以增加如 getAt 或 indexOf(以節點上的資料找尋其index位置)等實用的擴充。我個人的leet code解題實例也以 Gist 附上，希望能對大家有幫助，若有任何問題也歡迎留言討論哦！
