來征服資料結構與演算法吧 | 關於 Linked List 的基本介紹 feat. JavaScript
Hi！大家好，我是神 Q 超人！不得不說，演算法和資料結構真的是我心中最軟的那一塊，每一次打開 LeetCode 看到什麼 Linked List 或是 Tree 的題目，我的腦袋就直接當機，呈現失智狀態。
但是大概從今年初開始，給自己的其中一個目標（每年都有的目標 😂）就是把演算法和資料結構都練起來！而在經過兩個月的修煉後，就想說差不多可以從 Linked List 開始，分享目前學習的心得和一些相關題目的解析方式。
Linked List
介紹
Linked List 就像火車一樣，是種一個串著一個的資料結構，如果畫成圖就會變成這樣子：
以上方的 Linked List 來說，每一個藍色的圓形都是代表 Linked List 的 Node（節點），而每個 Node 裡面會有兩個屬性，第一個是 Node 的 Value，也就是上方的 A、B、C。另一個屬性則是指向下一個 Node 的 Next，但如果 Node 在整個 Linked List 的尾端，沒有下一個 Node 的話，該 Node 的 Next 則指向 Null。
在了解基本概念後，就能夠進一步把概念轉換成程式碼，首先把 A、B、C 三個 Node 都描繪成 Object：
雖然在上圖中已經沒有箭頭把三個 Node 串起來了，但是大家可以仔細觀察一下，每個 Node 都是 Object，而 Object 內也都有各自存放 Node 值的 val 和指向下一個 Node 的 next，而 nodeC 又因為是最後一個，所以 next 會是 null。
在進入下一個階段前，我們先建立一個 Function Constructor，讓我們可以輕鬆地定義 Node：
最後把整串 Linked List 的 nodeA、nodeB 和 nodeC 用程式碼表達：
上方先是用 Node 把 nodeA、nodeB 和 nodeC 個別建立出來，接著再指定 nodeA 的 next 為 nodeB、nodeB 的 next 為 nodeC，最後一個 nodeC 的 next 因為沒有指向任何一個 Node，所以還是原來的 null。
這就是基本的 Linked List 介紹啦！那接下來就搭配一些簡單的演算法題目，學習 Linked List 的一些基本操作吧！
讀取 Node
如果要在 Linked List 中讀取某個特定 Node，需要利用 next 來找到想讀取的目標 Node，再從 val 取得該 Node 的值。以下會用個演算法來進一步解釋。
876. Middle of the Linked List
關於 Middle of the Linked List 這道題目，簡單來說就是要你回傳某個 Linked List 中間的 Node。
Input: 1->3->7->4 Output: 7
Input: 1->2->3 Output: 2如果我們要在 Linked List 中找到中間的 Node 後回傳，首要的先決條件就是要先知道 Linked List 的長度為多少，我們可以寫一個迴圈，並在迴圈中計算 Linked List 的長度，迴圈會從 Linked List 的第一個 Node 開始，一直用 Next 讀取下一個 Node，直到 Node 變成為 null，也就是把所有 Node 跑完時停止，得到總長度後就能除 2 取得中間的 Node 了。寫成程式會變成：
上方的關鍵點在於 while 的條件於只要 head 為 null 就停止，以及在迴圈內一直把 head 更新成 head 的下一個值，如此一來 head 總是會變成 null 的，因為最後一個 Node 的 next 就是 null。
但這裡有個要注意的地方，那就是當 head 跑到 null 的時候，就無法再往前讀取 Linked List 的 Node 了，因此我在做 Linked List 相關題目的時候，都會特別留意要留下 Linked List 的第一個 Node，不斷變成 next 的這種事情，就定義另一個變數去做吧：
上方先是定義另一個 workHead 取代 head 的操作，這樣我們就會一直保留著 Linked List 的開頭 Node 了，因此在得到 Linked List 的 middle 後，就能再把已經變成 null 的 workHead 恢復成 head，再跑一次迴圈，一直到 currentIndex 等於 middle 後，直接回傳 workHead 當下的 Node。
經過這道題目我們可以知道，在單向的 Linked List 裡面，我們雖然能夠透過 next 取得下一個 Node，但我們是沒有辦法往前取得上一個 Node 的，因此留住 Linked List 的第一個 Node 是很重要的技巧。
另外，上方我說的是 單向的 Linked List，就像四大天王其實有五個人一樣，除了單向的 Linked List 以外，其實還存在著 雙向的 Linked List，雙向的 Linked List 和單向的差不多，只是多了一個 prev 指向上一個 Node，用圖表示的話會像這樣子：
至於該怎麼知道題目給的是單向的 Linked List 還是雙向的呢？如果是在做 LeetCode 的話，在你寫答案的地方其實都會註明當下 Node 是什麼樣子，需要的話就直接拿下來用，不需要自己另外寫：
增加 Node
在 Linked List 要增加 Node 非常容易，只需要操作 Node 的 next 就好，畢竟 Linked List 就是 Node 透過 next 來串連起來的，而增加 Node 有三種狀況，分別是加在最前面、中間和最後，以下用簡單的程式碼說明三種狀況：
首先是增加新的 Node 到 Linked List 的最前面
只要先定義一個擁有新值的 Node，之後把新 Node 的 next 指定成原本的 Linked List 就好了：
將上方的圖片邏輯轉換成程式碼會是：
將新的 Node 插到 Linked List 中
一樣先定義出新的 Node，接下來找到要插入的位置，把上一個 Node 的 next 指定成新的 Node，並把新 Node 的 next 指定成原本上一個 Node 的 next，聽起來有點饒舌，不過搭配圖片看會更清楚：
轉換為程式碼會變成（假設第一個 Node 的 index 從 0 開始，所以下方是要插 A 和 B 的中間）：
上方的程式碼需要注意的是在第 3 行，我定義了一個 dummyHead，用來當作假的初始值，下一行則是把它的 next 變成原本的 Linked list，這個動作就代表 dummyHead 是上一個值，而 head 這個當前值則是 dummyHead 的下一個值，也就是說，如果我們要插入 Node 在第一個位置，就是插在 dummyHead 和 head 中間，也等於原本的 head 前面多了一個新的 Node。
跑迴圈時會再另外用 currentIndex 來計算當前跑到第幾個 Node 了，同時也防止要插入的位置根本就沒有 Node，所以除了 currentIndex <= targetIndex 外還多判斷了 head !== null。在迴圈裡會一直更新 head、prev 和 currentIndex，一直到 currentIndex 等於 targetIndex ，就會建立一個新的 Node，之後把上一個 Node 的 next 指定成新的 Node，新 Node 的 next 則是指定成當前的 head，完成插入 Node 的動作。
因為我們在程式執行的過程一直在操作 head，所以當插入新的 Node 後， head 不會是題目一開始給我們的 Linked List 的第一個 Node，單向的 Linked List 又無法往前更新到第一個值，我們能夠回傳的也就不是完整的 Linked List 了，該怎麼辦？
這是 dummyHead 另一個有用的地方了！在一開始我們建立完 dummyHead 的時候，就將它的 next 指定成一開始還在 Linked List 第一個 Node 的 head，所以 dummyHead 的 next 會一直在剛開始 Linked List 的第一個 Node，最後也只要回傳 dummyHead.next 就好。
將新的 Node 插到 Linked List 的尾端
如果了解上方的兩個操作，那要把新的 Node 插入到 Linked List 尾端的邏輯一點都不難，只要先找到當前 Linked List 的最後一個 Node，並把它的 next 指定成新的 Node 就完成了：
將圖轉換為程式碼會變成：
上方的邏輯先使用 while 迴圈，找到 next 為 null 的 Node（最後一個 Node 的 next 會指向 null），之後把該 Node 的 next 指定成新的 Node，回傳的部分一樣用 dummyHead 的技巧，不論 head 目前跑到第幾個 Node，最後都只要回傳一直在 Linked List 最前面的 dummyHead.next 就好。
至於練習增加 Node 的演算法有個滿適合的題目，不過在那之前我們得先知道如何在 Linked List 中移除 Node，所以先來說說移除吧！
移除 Node
移除 Node 和增加 Node 一樣，也分為在 Linked List 的前、中和尾端移除，那因為 dummyHead 的概念在 Linked List 中太好用了，所以下方的範例都會再繼續使用 dummyHead 的技巧哦！
將 Linked List 最前面的 Node 移除
要將最前面的 Node 給移除，就只要將原本在 Linked List 內的第二個當作第一個，因為只要從第二個 Node 開始，就是另一個沒有第一個 Node 的 Linked List 了。這次聽起來有點哲學，我們一樣搭配圖片：
轉化為程式碼就是這樣子：
我絕對沒有偷懶，但就是那麼簡單！只要從第二個 Node 開始，就是一個移除了第一個 Node 的 Linked List 了！
移除 Linked List 中的 Node
要移除 Linked List 中的某個 Node，只需要將目標 Node 的前一個 Node 的 next 指向目標 Node 的 next 就好了，這樣要要移除的 Node 就會被跳過，前一個 Node 的 next 就會直接變成被移除的 Node 的下一個。可以對照圖會更好理解：
如果要把上圖的 nodeB 移除的話，就把 nodeA 的 next 指向 nodeB 的 next，也就是 nodeC 就好，如此一來在讀 Linked List 的 Node 的時候，nodeA 的下一個 Node 就是 nodeC，nodeB 就消失在 Linked List 囉！
轉換成程式碼的邏輯如下（假設第一個 Node 的 index 從 0 開始，所以下方要移除掉第二個 Node b）：
一樣用個 dummyHead 做一個開頭連接原本的 Linked List，並把 prev 設置為 dummyHead，然後在 while 迴圈內更新 prev 和當前的 Node，如果 currentIndex 等於 targetIndex 的話，就把 prev 的 next 設置為當前 Node（要被移除的 Node）的 next。
設置完後因為 head 已經不是在 Linked List 最開頭的位置了，所以直接回傳 next 為原本 Linked List 開頭 Node 的 dummyHead.next。
移除 Linked List 最後一個 Node
要移除 Linked List 的最後一個 Node 就要先找到倒數第二個 Node，然後直接把倒數第二個 Node 的 next 改成 null，如此一來整個 Linked List 就沒有原本的最後一個 Node 囉！
轉換成程式的話如下：
在移除前先做了判斷，如果當前 Node 的下一個就是 null，代表這個 Linked List 只有一個 Node，因此直接回傳 null，代表把自己移除。如果不是的話就跑迴圈，一直到把 head.next.next 為 null，也就是當前的 head 是 Linked List 倒數第二個 Node 的時候，就直接把倒數第二個 Node 的 next 改成 null，並回傳 dummyHead 的 next。
到這裡應該已經大概了解如何對 Linked List 中各個位置的 Node 做新增和移除，那接下來就是練習時間了！
1670. Design Front Middle Back Queue
這個題目滿有趣的，它要求你實作一個存放資料的 Queue（隊列），如果還不曉得什麼是 Queue，在這裡可以先直接當成 Linked List 來理解（注意哦！是只在個題目而已！並不是 Queue 等於 Linked List），而這個 Linked List 必須要可以分別從前、中和後新增和取出並移除 Node，有沒有非常熟悉？都是上方所提過的東西！
所以在做這一題的時候，只要利用 Linked List，並且分別把 Node 新增和移除到前、中和後的邏輯都寫出來就好（下方的程式碼非常長，建議可以單個單個方法看，都是上方所提過的操作邏輯）：
其實在答案裡比較多程式碼的部分只有 pushMiddle 和 popMiddle 而已，因為在異動 Linked List 之前，必須要先找到 Middle 的 Node 是第幾個，找到 Middle 後就是依如往常熟悉的操作了（各位也可以封裝算長度的邏輯，或是自己用另一個屬性計算當前 Linkes List 的長度）。另外要注意的是，移除 Node 的同時也要將該 Node 的值回傳。當初做這一題的時候有種在做 Linked List 總驗收的感覺。 😂
和 Array 的差異
在一開始學到 Linked List 的時候，都會反射性地聯想到 Array，因為兩者都是串列式的資料結構（都是一條長長的 😂），那它們有什麼不同呢？以下從存取資料的角度來看看：
讀取資料
在取資料方面，能夠直接用 index 取得元素的 Array 大勝，相比之下 Linked List 就只能用 next 來一個一個往下找自己要的東西，而且如果是單向的 Linked List 的話還要注意最前面的 Node 不能消失，不然就回不去了。
以時間複雜度來說的話 Array 在取資料方面是 O(1)，而 Linked List 則是 O(n)。
新增或移除資料
Array 在新增和移除資料時就比較麻煩，因為 Array 的長度是固定的，在宣告的時候就必須給定 Array 裡有多少空間，因此如果要新增或移除 Array 裡的元素，就得再另外宣告新長度的 Array，然後把異動後的資料放進去。
這裡順便提一下 JavaScript 中的 Array，在 JavaScript 裡面 Array 之所以可以自由地增加及減少元素，是因為它更像是一個 Object（事實上在你輸入 typeof [] 時也會得到 'object'），想知道更多可以參考 此 Stack Overflow 的問答 或是 ECMA-262 的 Array 部分。
另一方面，在 Linked List 要新增和移除元素就非常容易，因為只要操作 next 就好，不需要其他的操作，麻煩的是你得先找到你要新增或移除的那個 Node。
以時間複雜度來看，Array 在新增或移除資料的時間複雜度是 O(n)，而 Linked List 如果是新增或移除在第一個 Node，那時間複雜度是 O(1)，中間或最尾端的情況，因為還要搜索的時間，所以時間複雜度是 O(n)。但如果是雙向的 Linked List，也能夠直接從最後一個 Node 開始，所以不論是在第一個或最後一個 Node 增加、移除 Node，時間複雜度都會是 O(1)。
比較結論
所以 Linked List 麻煩歸麻煩，但還是有可取之處的，當你在事先不知道資料數有多少，或是你會很頻繁的新增或刪除資料時，選擇 Linked List 會比 Array 還要好！
以上就是一些關於 Linked List 的操作和用法！大家現在可以到 LeetCode 的 Linked List 區 火速刷題了 😂，如果有希望可以再補充什麼內容，或範例和解釋有任何問題的，再麻煩留言告訴我！我會盡快修正，非常感謝！ 🙌
