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教程: