JavaScript implements common data structures (stack, queue, linked list, hash table, tree)

Related recommendations: "javascript video tutorial"

In JavaScript, data structures are usually ignored or not touched much. But for many large companies, you generally need to have a deep understanding of how to manage data. Understanding data structures can also help you in your work when solving problems.

In this article, the data structure we will discuss and implement is:

• Stack
• Queue
• Linked list
• Hash table
• Tree

Stack

The first data structure is the stack. It's very similar to a queue, and you may have heard of a call stack before, which is the way JavaScript handles events. The stack looks like this:

The last item stored on the stack will be the first item removed. This is called last-in-first-out (LIFO). The back button in a web browser is a good example of this: every page you view is added to a stack, and when you click "Back", the current page (the last page added) is popped from the stack.

Enough with the theory. Next, look at some code:

class Stack {
  constructor() {
    // 创建栈结构，这是一个空对象
    this.stack = {}
  }
  // 把一个值压入栈的顶部
  push(value) {

  }
  // 弹出栈顶的值并返回
  pop() {

  }

  // 读取栈中的最后一个值，但是不删除
  peek() {

  }
}

I have commented the above code, now let’s implement it together. The first method is

push

. First think about what we need this method to do:

We need to accept a value

• And then add the value to the top of the stack
• The length of the stack should also be tracked in order to know the index of the stack
• It would be great if you could try it yourself first. The complete

push

method is implemented as follows:<pre class="brush:js;toolbar:false;">class Stack { constructor() { this._storage = {}; this._length = 0; // 这是栈的大小 } push(value) { // 将值添加到栈顶 this._storage[this._length] = value; // 因为增加了一个值，所以也应该将长度加1 this._length++; } /// ..... }</pre> I bet it's easier than you think. There are many structures like this that sound much more complicated than they actually are.

Now comes the

pop

method. The goal of the pop method is to remove the last value added to the stack and then return it. If possible, please try to implement it yourself first: <pre class="brush:js;toolbar:false;">class Stack { constructor() { this._storage = {}; this._length = 0; } pop() { // we first get the last val so we have it to return const lastVal = this._storage[--this._length] // now remove the item which is the length - 1 delete this._storage[--this._length] // decrement the length this._length--; // now return the last value return lastVal } }</pre> Cool! Almost done. The last one is the

peek

function, which looks at the last item on the stack. This is the simplest function: only the last value needs to be returned. The implementation is: <pre class="brush:js;toolbar:false;">class Stack { constructor() { this._storage = {}; this._length = 0; } /* * Adds a new value at the end of the stack * @param {*} value the value to push */ peek() { const lastVal = this._storage[--this._length] return lastVal } }</pre> So it's very similar to the

pop

method, but without removing the last item. Yes! The first data structure has been implemented. Next is the queue, which is very similar to a stack.

Queue

Let’s talk about queues next - I hope the stack is still very clear in your mind, because it is very similar to the queue. The main difference between a stack and a queue is that queues are first in, first out (FIFO).

can be represented graphically like this:

So the two main methods are

enqueue

and dequeue. Data is added to the end of the queue and removed from the head. In order to better understand it, let's start implementing the queue. The core code structure is as follows:

class Queue {
  constructor() {
    // 与前面类似，我们为数据结构提供了一个对象
    // 并且还有一个变量来保存长度
    this.queue = {}
    this.length = 0
    // 这是一个跟踪头部的新变量
    this.head = 0
  }

  enqueue(value) {

  }

  dequeue() {

  }

  peek() {

  }
}

First implement the

enqueue

method. Its purpose is to add an item to the end of the queue. <pre class="brush:js;toolbar:false;">enqueue(value) { // 使用 value 参数将 length + head 的键添加到对象 this.queue[this.length + this.head] = value; this.length++ }</pre>This is a very simple way to add a value to the end of the queue, but you may be confused by

this.queue[this.length this.head] = value;

Puzzled. Suppose the queue looks like this

{14: 'randomVal'}

. When adding this content, the next value we want is 15, so it should be length(1) head(14), which is 15. The next thing to be implemented is

dequeue

: <pre class="brush:js;toolbar:false;">dequeue() { // 获取第一个值的引用，以便将其返回 const firstVal = this.queue[this.head] // 现在将其从队列中删除 delete this.queue[this.head] this.length--; // 最终增加我们的头成为下一个节点 this.head++; }</pre>The last thing to be implemented is the

peek

method, which is very simple: <pre class="brush:js;toolbar:false;">peek() { // 只需要把值返回即可 return this.queue[this.head]; }</pre>Queue implementation completed.

Linked List

First let us discuss the powerful linked list. This is much more complex than the structure above.

Maybe your first question is why use a linked list? Linked lists are primarily used in languages ​​that do not have dynamically sized arrays. A linked list organizes items in order, with one item pointing to the next.

Each node in the linked list has a

data

value and a next value. In the figure below, 5 is the data value, and the next value points to the next node, which is the node with the value 10. Visually, it looks like this:

In an object, the above

LinkedList

looks like Like the following

You will see that the

next

value of the last value 1 is null , because this is the end of LinkedList. So how to achieve it?

Let's create a

LinkedList

with the values ​​1, 2, and 37. <pre class="brush:js;toolbar:false;">const myLinkedList = { head: { value: 1 next: { value: 2 next: { value: 37 next: null } } } };</pre><p>现在我们知道了该怎样手动创建 <code>LinkedList，但是还需要编码实现 LinkedList 的方法。

首先要注意的是，LinkedList 只是一堆嵌套对象！

当构造一个 LinkedList 时，我们需要一个 head 和一个 tail，它们最初都会指向头部（因为 head 是第一个也是最后一个）。

class LinkedList {
  constructor(value) {
    this.head = {value, next: null}
    this.tail = this.head
  }
}

第一个要实现的方法是 insert ，该方法用来在链表的末尾插入一个值。

// insert 将添加到链接列表的末尾
insert(value) {
  /* 创建一个节点 */
  const node = {value, next: null}
  /* 把 tail 的 next 属性设置为新节点的引用 */
  this.tail.next = node;
  /* 新节点现在是尾节点 */
  this.tail = node;
}

上面最混乱的一行可能是 this.tail.next = node。之所以这样做，是因为当添加一个新节点时，我们还希望当前的 tail 指向新的 node，该节点将成为新的 tail。第一次插入 node 时，头部的 next 指针将指向新节点，就像在构造函数中那样，在其中设置了 this.tail = this.head。

你还可以到这个网站来查看图形化的演示，这将帮你了解插入的过程（按 esc 摆脱烦人的弹出窗口）。

下一个方法是删除节点。我们首先要决定参数是值（ value） 还是对节点（node）的引用（在面试中，最好先问问面试官）。我们的代码中传递了一个“值”。按值从列表中删除节点是一个缓慢的过程，因为必须要遍历整个列表才能找到值。

我这样做是这样的：

removeNode(val) {
  /* 从 head 开始 */
  let currentNode = this.head
  /* 我们需要保留对上一个节点的引用 */
  let previousNode
  /* 当存在一个节点时，意味着没有到达尾部 */
  while(currentNode) {
     /* 如果发现自己想要的那个值，那么就退出循环 */
     if(currentNode.value === val) {
        break;
     }
    /* 没有找到值就将 currentNode 设置为 previousNode */
    previousNode = currentNode
    /* 得到下一个节点并将其分配给currentNode  */
    currentNode = currentNode.next
  }
  /* 返回undefined，因为没有找到具有该值的节点  */
  if (currentNode=== null) {
    return false;
  }

  // 如果节点是 head ，那么将 head 设置为下一个值
  头节点的
  if (currentNode === this.head) {
    this.head = this.head.next;
    return;
  }
  /* 通过将节点设置为前面的节点来删除节点 */  
  previousNode.next = currentNode.next
}

removeNode 方法使我们对 LinkedList 的工作方式有了很好的了解。

所以再次说明一下，首先将变量 currentNode 设置为 LinkedList 的 head，因为这是第一个节点。然后创建一个名为 previousNode 的占位符变量，该变量将在 while 循环中使用。从条件 currentNode 开始 while 循环，只要存在 currentNode，就会一直运行。

在 while 循环中第一步是检查是否有值。如果不是，则将 previousNode 设置为 currentNode，并将 currentNode 设置为列表中的下一个节点。继续进行此过程，直到找到我需要找的值或遍历完节点为止。

在 while 循环之后，如果没有 currentNode，则返回 false，这意味着没有找到任何节点。如果确实存在一个 currentNode，则检查的 currentNode 是否为 head。如果是的话就把 LinkedList 的 head 设置为第二个节点，它将成为 head。

最后，如果 currentNode 不是头，就把 previousNode 设置为指向 currentNode 前面的 node，这将会从对象中删除 currentNode。

另一个常用的方法（面试官可能还会问你）是 removeTail 。这个方法如其所言，只是去掉了 LinkedList 的尾节点。这比上面的方法容易得多，但工作原理类似。

我建议你先自己尝试一下，然后再看下面的代码（为了使其更复杂一点，我们在构造函数中不使用 tail）：

removeTail() {
  let currentNode = this.head;
  let previousNode;
  while (currentNode) {
    /* 尾部是唯一没有下一个值的节点，所以如果不存在下一个值，那么该节点就是尾部 */
    if (!currentNode.next) {
      break;
    }
    // 获取先前节点的引用
    previousNode = currentNode;
    // 移至下一个节点
    currentNode = currentNode.next;
  }
  // 要删除尾部，将 previousNode.next 设置为 null
  previousNode.next = null;
}

这些就是 LinkedList 的一些主要方法。链表还有各种方法，但是利用以上学到的知识，你应该能够自己实现它们。

哈希表

接下来是强大的哈希表。

哈希表是一种实现关联数组的数据结构，这意味着它把键映射到值。 JavaScript 对象就是一个“哈希表”，因为它存储键值对。

在视觉上，可以这样表示：

在讨论如何实现哈希表之前，需要讨论讨论哈希函数的重要性。哈希函数的核心概念是它接受任意大小的输入并返回固定长度的哈希值。

hashThis('i want to hash this') => 7

哈希函数可能非常复杂或直接。 GitHub 上的每个文件都经过了哈希处理，这使得每个文件的查找都非常快。哈希函数背后的核心思想是，给定相同的输入将返回相同的输出。

在介绍了哈希功能之后，该讨论一下如何实现哈希表了。

将要讨论的三个操作是 insert、get最后是 remove。

实现哈希表的核心代码如下：

class HashTable {
  constructor(size) {
    // 定义哈希表的大小，将在哈希函数中使用
    this.size = size;
    this.storage = [];
  }
  insert(key, value) { }
  get() {}
  remove() {}
  // 这是计算散列密钥的方式
  myHashingFunction(str, n) {
    let sum = 0;
    for (let i = 0; i < str.length; i++) {
      sum += str.charCodeAt(i) * 3;
    }
    return sum % n;
  }
}

现在解决第一个方法，即 insert。insert 到哈希表中的代码如下（为简单起见，此方法将简单的处理冲突问题）：

insert(key, value) {
  // 得到数组中的索引
  const index = this.myHashingFunction(key, this.size);
  // 处理冲突 - 如果哈希函数为不同的键返回相同的索引，
  // 在复杂的哈希函数中，很可能发生冲突
  if (!this.storage[index]) {
    this.storage[index] = [];
  }
  // push 新的键值对
  this.storage[index].push([key, value]);
}

像这样调用 insert 方法：

const myHT = new HashTable(5);
myHT.insert("a", 1);
myHT.insert("b", 2);

你认为我们的哈希表会是什么样的？

你可以看到键值对已插入到表中的索引 1 和 4 处。

现在实现从哈希表中删除

remove(key) {
    // 首先要获取 key 的索引，请记住，
    // 哈希函数将始终为同一 key 返回相同的索引
    const index = this.myHashingFunction(key, this.size);
    // 记住我们在一个索引处可以有多个数组（不太可能）
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      // 遍历该索引处的所有数组
      for (let i = 0; i < arrayAtIndex.length; i++) {
        // get the pair (a, 1)
        let pair = arrayAtIndex[i];
        // 检查 key 是否与参数 key 匹配
        if (pair[0] === key) {
          delete arrayAtIndex[i];
          // 工作已经完成，所以要退出循环
          break;
        }
      }
    }
}

最后是  get 方法。这和 remove 方法一样，但是这次，我们返回 pair 而不是删除它。

 get(key) {
    const index = this.myHashingFunction(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      for (let i = 0; i < arrayAtIndex.length; i++) {
        const pair = arrayAtIndex[i];
        if (pair[0] === key) {
          return pair[1];
        }
      }
    }
  }

我认为不需要执行这个操作，因为它的作用与 remove 方法相同。

你可以认为它并不像最初看起来那样复杂。这是一种到处使用的数据结构，也是是一个很好理解的结构！

二叉搜索树

最后一个数据结构是臭名昭著的二叉搜索树。

在二叉搜索树中，每个节点具有零个、一个或两个子节点。左边的称为左子节点，右边的称为右子节点。在二叉搜索树中，左侧的子项必须小于右侧的子项。

你可以像这样描绘一个二叉搜索树：

树的核心类如下：

class Tree {
   constructor(value) {
     this.root = null
   }

   add(value) {
    // 我们将在下面实现
   }

}

我们还将创建一个 Node 类来代表每个节点。

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

下面实现 add 方法。我已经对代码进行了注释，但是如果你发现使你感到困惑，请记住，我们要做的只是从根开始并检查每个节点的 left 和 right。

add(value) {
    // 如果没有根，那么就创建一个
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    // keep looping
    while (true) {
      // 如果当前值大于传入的值，则向左
      if (current.value > value) {
        // 如果存在左子节点，则再次进行循环
        if (current.left) {
          current = current.left;
        } else {
          current.left = new Node(value);
          return;
        }
      }
      // 值较小，所以我们走对了
      else {
        // 向右
        // 如果存在左子节点，则再次运行循环
        if (current.right) {
          current = current.right;
        } else {
          current.right = new Node(value);
          return;
        }
      }
    }
}

测试新的 add 方法：

const t = new Tree();
t.add(2);
t.add(5);
t.add(3);

现在树看起来是这样：

为了更好的理解，让我们实现一个检查树中是否包含值的方法。

contains(value) {
  // 获取根节点
  let current = this.root;
  // 当存在节点时
  while (current) {
    // 检查当前节点是否为该值
    if (value === current.value) {
      return true; // 退出函数
    }
    // 通过将我们的值与 current.value 进行比较来决定下一个当前节点
    // 如果小则往左，否则往右
    current = value < current.value ? current.left : current.right;
  }
  return false;
}

Add 和 Contains 是二进制搜索树的两个核心方法。对这两种方法的了解可以使你更好地解决日常工作中的问题。

总结

我已经在本文中介绍了很多内容，并且掌握这些知识后在面试中将使你处于有利位置。希望你能够学到一些东西，并能够轻松地通过技术面试（尤其是讨厌的白板面试）。

更多编程相关知识，请访问：编程教学！！

The above is the detailed content of JavaScript implements common data structures (stack, queue, linked list, hash table, tree). For more information, please follow other related articles on the PHP Chinese website!