Back in we got a birds-eye look at what linked lists are and why they’re necessary for creating more advanced data structures. Now we can learn how to start implementing a fully-featured doubly linked list in JavaScript.

在我们鸟瞰了什么是链表以及为什么创建更高级的数据结构需要链表。 现在我们可以学习如何开始在JavaScript中实现功能齐全的双向链表。

Singly linked lists and implementations in other data structures will generally just be more barebones versions of what we’ll cover here, so this would be good to bookmark as a general reference.

单链列表和其他数据结构中的实现通常只是我们将在此处介绍的更准系统的版本，因此将其标记为一般参考将是不错的选择。

结构体 (Structure)

Like any other class, we can store whatever we want in each node, the only important parts are the next and prev pointers, which should be null by default.

像任何其他类一样，我们可以在每个节点中存储所需的内容，唯一重要的部分是next和prev指针，默认情况下应为null 。

Likewise the only things our list needs are its tail, head, and length. We’ll need to manually manipulate the length since, unlike arrays, it won’t be calculated for us and will be necessary for searching for items.

同样，列表所需的唯一内容是tail ， head和length 。 我们需要手动操作长度，因为与数组不同，它不会为我们计算出来，并且对于搜索项目是必不可少的。

class Node {  constructor(val) {    this.val = val;    this.next = null;    this.prev = null;  };};class linkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  };};

创造 (Create)

Now we can start setting up all of our methods inside our linkedList class. Since we don’t have any of our normal goodies like push or shift we’ll have to create our own versions.

现在，我们可以开始在linkedList类中设置所有方法。 由于我们没有像push或shift这样的常规物品，因此我们必须创建自己的版本。

首尾 (Head and Tail)

Most of our operations are based more on manipulating the pointers in the surrounding nodes than on the item we want to change. To add something isn’t just shoving a new node where we want, like with an array, but changing the pointers on the items before or after to point to our new item, then manually incrementing the list’s length.

我们的大多数操作更多地基于操纵周围节点中的指针，而不是基于我们要更改的项目。 添加一些东西不仅像在数组上那样，在我们想要的地方插入一个新节点，而且在改变项目之前或之后的指针以指向我们的新项目，然后手动增加列表的长度。

If there isn’t anything in the list, we want to set the new item as both the head and tail, since it’s the only item. To add or remove from the end of the list we’ll take the current head/tail we want to replace and set its pointer to our new item or null, change the list’s head/tail to our new node or null, then increment the length.

如果列表中没有任何内容，我们希望将新项目设置为头部和尾部，因为它是唯一的项目。 要从列表末尾添加或删除列表，我们将获取要替换的当前头/尾，并将其指针设置为新项目或null，将列表的头/尾更改为新节点或null，然后增加长度。

addHead(val) {  let newNode = new Node(val);  if (!this.head) {    this.head = newNode;    this.tail = this.head;  };  this.head.prev = newNode;  newNode.next = this.head;  this.head = newNode;  this.length++;  return this;}addTail(val) {  let newNode = new Node(val);  if (!this.head) {    this.head = newNode;    this.tail = newNode;  };  this.tail.next = newNode;  newNode.prev = this.tail;  this.tail = newNode;  this.length++;  return this;}removeHead() {  let removed = this.head;  if (!this.head) return undefined;  this.head = this.head.next;  this.head.prev = null;  this.length--;  return removed;}removeTail() {  let removed = this.tail;  if (!this.tail) return undefined;  if (this.length === 1) {    this.head = null;    this.tail = null;  };  this.tail = removed.prev;  this.tail.next = null;  this.length--;  return removed;}

找 (Find)

Since we don’t have an index to get our item by we’re going to have some problems with inserting/removing in the middle of the list, so we’re going to need our own utility function.

由于我们没有索引来获取商品，因此在列表的中间插入/删除会遇到一些问题，因此我们将需要自己的实用程序功能。

It’s very simple, we just need to store the current item and use a for or while loop to use our pointers to update current until we’re at the item we want.

这非常简单，我们只需要存储当前项目，并使用for或while循环使用指针来更新current直到找到所需的项目为止。

Graphic/Animation thanks to

图形/动画得益于

Of course, this gives us an O(n) search time, but since we’re using a doubly linked list we can just start from the tail if what we want is past the middle of the list, giving us O(n / 2).

当然，这给了我们O(n)搜索时间，但是由于我们使用的是双向链表，因此如果想要的内容超出列表的中间位置，我们可以从尾部开始，从而获得O(n / 2) 。

find(index) {  let current  if (index < 0 || index >= this.length) return undefined;  if (index <= this.length / 2) {    current = this.head;    for (let i = 0; i < index; i++) current = current.next;  } else {    current = this.tail;    for (let i = this.length; i > index; i--) current = current.prev;  }  return current;}

插入和移除 (Insert and Remove)

Now that we have our little utility in place we can use it to find the item in the index we want then set the pointers on it and the item before and after it to our new node, thus “stitching” it into place.

现在我们已经有了小工具，可以使用它在索引中找到所需的项目，然后将其上的指针以及该项目前后的指针设置到新节点，从而将其“缝合”到位。

Graphic/Animation thanks to

图形/动画得益于

If the index is on the head or tail, we can just reuse our previous methods.

如果索引在头或尾上，我们可以重复使用以前的方法。

insert(val, index) {  if (index < 0 || index > this.length) return null;  if (index === this.length) return this.addTail(val);  if (index === 0) return this.addHead(val);  let prev = this.find(index - 1),      newNode = new Node(val),      temp = prev.next;  prev.next = newNode;  newNode.next = temp;  newNode.prev = prev;  this.length++;  return true;}

Removing is obviously just the inverse of inserting and a bit simpler. Find the node we want to remove and set the pointers on the surrounding nodes to each other, leaving nothing that references the removed node.

删除显然只是插入的逆过程，并且更简单。 找到我们要删除的节点，并将周围节点上的指针彼此设置，不留任何引用已删除节点的指针。

Graphic/Animation thanks to

图形/动画得益于

remove(index) {  if (index < 0 || index >= this.length) return null;  if (index === this.length) return this.removeTail();  if (index === 0) return this.removeHead();  let removed = this.find(index);  removed.prev.next = removed.next;  removed.next.prev = removed.prev;  this.length--;  return removed;}

更新资料 (Update)

This one is so simple it’s almost no even worth mentioning, just find the item and reset it’s value.

这是如此简单，几乎一文不值，仅需找到该项目并重置其值即可。

update(val, index) {  let node = this.find(index);  if (node) node.val = val;  return node;}

结论 (Conclusion)

While this may have seemed like a lot of work, it’s good to keep in mind that in many cases you won’t need all of it.

尽管这似乎是一项艰巨的工作，但请记住，在许多情况下您并不需要全部。

I really recommend checking out for when you don’t feel like manually making one, although it’s always good to understand the concept on a deeper level.

我真的建议您查看以 ，尽管更深入地了解这一概念总是不错的。

翻译自: