JavaScript數據結構:鏈接列表

鏈接列表是您可以學習的最重要的數據結構之一。

在鏈接列表中,每個項目都包含對它後面的項目的引用。

我們可以從列表的開頭開始head,然後遍歷列表中的所有項目,直到到達末尾(tail)。

與數組相比,項目在實際的內存中不會彼此相鄰(使用低級編程語言),或者沒有可用於隨機訪問數組項目的索引。

我們不能從列表開頭就引用列表中間的項目,因為我們不知道如何引用它。

JavaScript沒有鍊錶的實現,因此我們現在將創建一個。

首先,我們創建Item列表中每個項目將包含的類:

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

我們有一個指向列表中下一項以及值的指針。

然後我們定義了LinkedList將託管2個私有值的類:headtail

我們定義一個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) => {
    //check for out-of-bounds values
    if (index < 0 || index > this.size()) return
<span style="color:#66d9ef">const</span> <span style="color:#a6e22e">node</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#a6e22e">Item</span>(<span style="color:#a6e22e">value</span>)
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">current</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">this</span>.<span style="color:#960050;background-color:#1e0010">#</span><span style="color:#a6e22e">head</span>
<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">previous</span>

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">index</span> <span style="color:#f92672">===</span> <span style="color:#ae81ff">0</span>) {
  <span style="color:#75715e">//first position

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

鍊錶的另一種類型是雙鍊錶,其中每個項目也包含指向上一個元素的鏈接。

免費下載我的JavaScript初學者手冊


更多js教程: