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

首先要注意的是，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!