JavaScript資料結構:鏈結串列 鏈結串列是你可以學習到的最重要的資料結構之一。
在鏈結串列中,每個項目都包含對其後繼項目的引用。
我們可以從串列的開始處,即「頭部」,開始迭代遍歷所有項目,直到達到末尾(即「尾部」)。
相較於陣列,在低階程式語言中,項目並不相鄰於實際的記憶體位置,且沒有索引可供我們隨機訪問陣列中的項目。
我們無法在不從開始的情況下引用列表中的中間項目,因為我們不知道如何引用它。
JavaScript本身並沒有鏈結串列的實作,因此我們現在將創建一個。
首先,我們創建一個會成為鏈結串列中每個項目的容器的Item
類別:
1 2 3 4 5 6 7 class Item { next = null value = null constructor(value) { this.value = value } }
我們有一個指向鏈結串列中下一個項目的指標,以及該項目的值。
然後,我們定義一個LinkedList
類別,該類別將擁有兩個私有值:head
和tail
。
我們定義了一個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”, “鏈結串列”, “資料結構”]