/

JavaScript資料結構:鏈結串列

JavaScript資料結構:鏈結串列

鏈結串列是你可以學習到的最重要的資料結構之一。

在鏈結串列中,每個項目都包含對其後繼項目的引用。

我們可以從串列的開始處,即「頭部」,開始迭代遍歷所有項目,直到達到末尾(即「尾部」)。

相較於陣列,在低階程式語言中,項目並不相鄰於實際的記憶體位置,且沒有索引可供我們隨機訪問陣列中的項目。

我們無法在不從開始的情況下引用列表中的中間項目,因為我們不知道如何引用它。

JavaScript本身並沒有鏈結串列的實作,因此我們現在將創建一個。

首先,我們創建一個會成為鏈結串列中每個項目的容器的Item類別:

1
2
3
4
5
6
7
class Item {
next = null
value = null
constructor(value) {
this.value = value
}
}

我們有一個指向鏈結串列中下一個項目的指標,以及該項目的值。

然後,我們定義一個LinkedList類別,該類別將擁有兩個私有值:headtail

我們定義了一個append()方法,用於將項目添加到串列中。如果它是第一個添加的項目,該項目同時是串列的頭部和尾部。否則,我們創建該項目並將其分配給尾部項目的next屬性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LinkedList {
#head = null
#tail = null
append = (value) => {
const item = new Item(value)
if (!this.#head) {
this.#head = item
this.#tail = item
return
}
this.#tail.next = item
this.#tail = item
}
size = () => {
let count = 1
let item = this.#head
if (!item) return 0
while ((item = item.next)) {
count++
}
return count
}
}

這是我們如何使用它:

1
2
3
4
const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)

我們可以添加一個size()方法來返回串列的大小:

1
2
3
4
5
6
7
8
9
10
11
12
class LinkedList {
//...
size = () => {
let count = 1
let item = this.#head
if (!item) return 0
while ((item = item.next)) {
count++
}
return count
}
}
1
2
3
4
5
6
7
const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

我們如何根據值在串列中查找項目?讓我們實現一個方法來做到這一點:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LinkedList {
//...
find = (value) => {
let count = 1
let item = this.#head
if (!item) return null
while ((item = item.next)) {
if (item.value === value) {
return item
}
}
return null
}
}

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
const item = list.find(2) // item.value === 2

如果我們想在鏈結串列中插入項目,該怎麼做?我們已經有了append()方法,用於將項目插入到串列的末尾。現在讓我們實現一種方式,在特定位置插入項目:

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
class LinkedList {
//...
insert = (index, value) => {
//檢查超出範圍的索引值
if (index < 0 || index > this.size()) return

const node = new Item(value)
let current = this.#head
let previous

if (index === 0) {
//第一個位置
node.next = current
this.#head = node
} else {
let i = 0
while (i++ < index) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
}
}

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
list.insert(2, 'a')
list.size() //4

另一種類型的鏈結串列是雙向鏈結串列,其中每個項目還包含到前一個元素的連結。

tags: [“JavaScript”, “Data Structures”, “Linked List”, “鏈結串列”, “資料結構”]