資料結構與演算法-1-Linked List

前言

參考資料2
講師將Linked List(以下縮寫為LL)稱為node base data structure是蠻有道理,看看上面的圖,每一個節點包含資料本身以及指向另一個資料位置的紀錄。
根據指向的內容,可能有不同稱呼,像是指向next的Single Linked List、既指向next也指向previous的Bio Linked List。

介面

下面是一個單向的LL的介面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node {
constructor(value) {
this.value = value; // 資料本身
this.next = null; // 指針
}
}

class LL {
constructor() {
this.head = this.tail = null;
this.length = 0;
}

print() {}
pop() {}
insert(value) {}
}

限制與運用

LL最大的優點在於寫入跟刪除的速度極快,因為是固定的步驟去重新指向,所以時間複雜度是O(1)等級,另外他在儲存上也有一個優勢是可以散亂的儲存,因為有指針的存在,不用連續資料也可以;而LL的缺點在於讀取資料,在讀取資料的時候,因為要跟著指針一個個循序讀取,而隨著資料的變大,他的worst case可能跟著跟著變大,所以時間複雜度是O(n),另外因為需要額外儲存指向的資料,需要額外花費容量。

而他的所以優缺點剛好都相對於Array,之後到Array時再來多加介紹。

實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class LL {
constructor() {
this.head = this.tail = null;
this.length = 0;
}

print() {
let now = this.head;
while (now) {
console.log(now.value);
now = now.next;
}
}

// 移除LL最後一個節點: 因為是單向LL,所以要找到最後一個節點的前一個只能循序訪問。
pop() {
this.length = Math.max(0, this.length - 1);
if (!this.tail) return undefined;

let current = this.head;
const tail = this.tail;
while (node.next !== tail) {
current = node.next;
}

const prevTailNode = currentNode;
this.tail = prevTailNode;
this.tail.next = null;

return tail;
}

// 插入最後一個節點
insert(value) {
this.length++;

const newNode = new Node(value);
if (!this.tail) {
this.tail = this.head = newNode;
return newNode;
}

this.tail.next = newNode;
this.tail = newNode;

return newNode;
}
}

小結

這個系列會來學習資料結構與演算法,並透過撰寫文章整理想法及內化知識,大致會以這樣的架構輸出:前言也就是簡介,聊聊這個資料結構的運用情境、強弱限制、時間複雜度等,最後就會是用javascript實作,特別感謝免費課程The Last Algorithms Course You’ll Need,帶給我大量的啟發以及對資結及演算法的興趣。

此文章同步發表於部落格,歡迎來逛逛~

參考資料

The Last Algorithms Course You’ll Need
What is Linked List