Linked list Javascript實作及Leet code題目解析

nchuuu
nchuuu
Nov 6 · 5 min read

開始之前

因最近正在複習資料結構(基本上就是重新學習了吧😂),希望能把一些比較重要的部分記錄下來,並在撰寫文章的過程中讓自己的記憶更加深刻。以下會盡量使用 ES6 的語法來創建資料結構的實例,當然也會有思慮不周的部分,還請大家多多留言指教!

Intro

Linked list 鏈結串列,是一種動態的資料結構,相對於 Array 陣列,不需連續的記憶體空間即可儲存,對於資料的操作成本較低;然而若欲取得其中某一節點 Node 上的資料,則必須從頭開始遍歷查找。

A simple example of a linked list, nchuuu

Practice

由上圖可知,一個串列中存在多個 Node 結構,且 HEAD 會指向第一筆資料;而 Node 結構中由 Item 存儲資料,Next 負責指向下一筆 Node。故我們創建一個 Linked list 的 Class 思路為:

  1. 鏈結串列有起始位置 head,亦即串列中第一筆 Node。
  2. Node 節點以 item 存放資料。
  3. Node 節點以 next 作為指標,指向下一個 Node。
  4. 為 List 加入一些參數如 length ,便於後續操作。

節由以上整理我們可以先開始創建符合需求的 ES6 Class:

LinkedList及Node分別為兩個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 如上例,需注意的是 currentprev 兩個變數的使用;透過他們我們可以對遍歷到的節點進行暫存,到達指定 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.

這邊解題的思路為:

  1. 遍歷兩個 Input,每個位數互相加總。
  2. 注意是否有進位,需在下一筆資料加上。
  3. 兩個 input 有可能長度不同 (ex: 123, 45),只要還遍歷的到任一 Input 存在就必須進行加總(ex: 1+4, 2+5, 3+0)

以上文章簡略以 ES6 Class 實作了 Linked list 物件,除了上述的方法,我們也可以增加如 getAtindexOf(以節點上的資料找尋其index位置)等實用的擴充。我個人的leet code解題實例也以 Gist 附上,希望能對大家有幫助,若有任何問題也歡迎留言討論哦!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade