JavaScript資料結構：鏈結串列

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

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

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

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

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

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

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

class Item {
 next = null
 value = null
 constructor(value) {
 this.value = value
 }
}

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

然後，我們定義一個LinkedList類別，該類別將擁有兩個私有值：head和tail。

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

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
 }
}

這是我們如何使用它：

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

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

class LinkedList {
 //...
 size = () => {
 let count = 1
 let item = this.#head
 if (!item) return 0
 while ((item = item.next)) {
 count++
 }
 return count
 }
}

const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

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

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()方法，用於將項目插入到串列的末尾。現在讓我們實現一種方式，在特定位置插入項目：

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

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