JavaScript数据结构：链接列表

链接列表是您可以学习的最重要的数据结构之一。

在链接列表中，每个项目都包含对它后面的项目的引用。

我们可以从列表的开头开始head，然后遍历列表中的所有项目，直到到达末尾（tail）。

与数组相比，项目在实际的内存中不会彼此相邻（使用低级编程语言），或者没有可用于随机访问数组项目的索引。

我们不能从列表开头就引用列表中间的项目，因为我们不知道如何引用它。

JavaScript没有链表的实现，因此我们现在将创建一个。

首先，我们创建Item列表中每个项目将包含的类：

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

我们有一个指向列表中下一项以及值的指针。

然后我们定义了LinkedList将托管2个私有值的类：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) => {
    //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初学者手册

JavaScript数据结构：链接列表

更多js教程：