WEB开发编程网由Paul Ryan✏️撰写
我们要谈什么？
数据结构经常在JavaScript中被忽略-或更确切地说，我们考虑的不多。忽略数据结构的问题是，对于许多顶级公司而言，通常需要您深刻了解如何管理数据。掌握数据结构也将在您解决问题时为您的日常工作提供帮助。
在本文中，我们将讨论/实现的数据结构是：
- 堆
- 队列
- 链表
- 哈希表
- 树木
堆
我们正在讨论的第一个数据结构是堆栈。这与队列非常相似，并且您之前可能已经听说过调用堆栈，这是JavaScript用于处理事件的方法。
在外观上，堆栈看起来像这样：
因此，当您有堆栈时，您在堆栈上压入的最后一个项目将是第一个被移除的项目。这称为后进先出（LIFO）。Web浏览器中的“后退”按钮就是一个很好的例子：将您查看的每个页面添加到堆栈中，当您单击“返回”时，将从堆栈中弹出当前页面（最后添加的页面）。
那足够理论了。让我们来看一些代码：
class Stack {
constructor() {
// create our stack, which is an empty object
this.stack = {}
}
// this method will push a value onto the top of our stack
push(value) {
}
// this method is responsible for popping off the last value and returning it
pop() {
}
// this will peek at the last value added to the stack
peek() {
}
}
我已经注释了上面的代码，因此希望您与我在一起。我们将要实现的第一个方法是push方法。
因此，让我们考虑一下我们需要这种方法来做的事情：
- 我们需要接受一个价值
- 然后，我们需要将该值添加到堆栈顶部
- 我们还应该跟踪堆栈的长度，以便我们知道堆栈的索引
如果您可以先自己尝试一下，那就太好了，但是如果没有，那么完整的push方法实现如下：
class Stack {
constructor() {
this._storage = {};
this._length = 0; // this is our length
}
push(value) {
// so add the value to the top of our stack
this._storage[this._length] = value;
// since we added a value we should also increase the length by 1
this._length++;
}
/// .....
}
我敢打赌，这比您想象的要容易。我认为，使用许多这样的结构，它们听起来比实际复杂得多。
现在让我们来看看pop方法。该pop方法的目标是删除最后添加到堆栈中的值，然后返回该值。如果可以的话，请先自己尝试，否则继续查看解决方案：
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
}
}
凉！就快到了。我们需要做的最后一件事是该peek函数，它查看堆栈中的最后一项。这是最简单的功能：我们只返回最后一个值。实现是：
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
}
}
因此，这与pop方法非常相似，但是这次，我们不删除最后一项。
是! 那是我们第一个覆盖的数据结构。现在让我们进入队列，它与堆栈非常相似。
队列
队列是我们将要讨论的下一个结构-希望栈在您的大脑中仍然很新鲜，因为队列非常相似。堆栈和队列之间的主要区别在于队列是先进先出（FIFO）。
在视觉上，我们可以这样表示：
因此，两个大动作是enqueue和dequeue。我们添加到背面并从正面移除。让我们开始实施队列以更好地理解。
我们代码的核心结构将如下所示：
class Queue {
constructor() {
// similar to above we have an object for our data structure
// and we also have a variable to keep track of the length
this.queue = {}
this.length = 0
// this is a new variable which tracks the head
this.head = 0
}
enqueue(value) {
}
dequeue() {
}
peek() {
}
}
因此，让我们首先实现我们的enqueue方法。其目的是向队列的后面添加一个项目。
enqueue(value) {
// add a key of our length + head to our object with the value param
this.queue[this.length + this.head] = value;
this.length++
}
这是一个非常简单的方法，可以在队列末尾添加一个值，但是您可能会对感到困惑this.queue[this.length + this.head] = value;。
假设我们的队列看起来像这样{14 : 'randomVal'}。在添加此内容时，我们希望我们的下一个键是15，因此它将是length（1）+ head（14），这给了我们15。
下一个要实现的dequeue方法是：
dequeue() {
// get a reference to our first val so we can return it
const firstVal = this.queue[this.head]
// now delete this from our queue
delete this.queue[this.head]
// decrement our lenght
this.length--;
// finally increment our head to be the next node
this.head++;
}
最终要实现的peek方法是一种简单的方法：
peek() {
// simply return the value at our head
return this.queue[this.head];
}
队列就是这样-让我们继续Linked List数据结构。
链表
因此，让我们讨论强大的链表。这比上面的结构要复杂得多，但是我们可以一起弄清楚。
您可能遇到的第一个问题是为什么我们要使用链表？链表主要用于没有动态大小调整数组的语言。链接列表按顺序组织项目，每个项目指向下一个项目。
链表中的每个节点都有一个data值和一个next值。下面5是数据值，该next值指向下一个节点，即具有value的节点10。
在视觉上，它看起来像这样：
作为附带说明，先前的指针称为双向链接列表。
在一个对象中，以上内容LinkedList类似于以下内容
您会看到最后一个值1的next值为null，因为这是我们的结尾LinkedList。
那么现在，我们将如何实施呢？
让我们创建一个LinkedList具有价值1，2和37。
const myLinkedList = {
head: {
value: 1
next: {
value: 2
next: {
value: 37
next: null
}
}
}
};
因此，我们知道如何手动创建LinkedList，但是让我们采用编写将实现的方法LinkedList。
我们应该注意的第一件事是a LinkedList只是一堆嵌套对象！
构造a时LinkedList，我们需要a head和a tail，它们最初将指向我们的头部（因为第head一个和最后一个）。
class LinkedList {
constructor(value) {
this.head = {value, next: null}
this.tail = this.head
}
}
我们将要实现的第一个方法是insert方法，它将在链接列表的末尾插入一个值。
// insert will add to the end of our linked list
insert(value) {
/* create the node */
const node = {value, next: null}
/* set the next property of the tail = to the new node */
this.tail.next = node;
/* the new node is now the tail */
this.tail = node;
}
上面最令人困惑的行可能是this.tail.next = node。我们这样做是因为当我们添加一个新的节点上，我们也希望当前tail的新点node，这将成为新的tail。第一次插入a时node，next头部的指针将指向新节点-就像在我们已设置的构造函数中一样this.tail = this.head。
您也可以通过访问此网站来直观地看到此内容，这将帮助您了解插入的过程（按此esc按钮可以消除烦人的弹出窗口）。
我们将实现的下一个方法是删除节点。我们必须决定的第一件事是我们的参数是a value还是对a的引用node（在采访中，最好向采访者问这个）。为了我们的缘故，我们将说a value已通过。按值从列表中删除节点是一个缓慢的过程，因为我们必须遍历整个列表才能找到值。
我们这样做是这样的：
removeNode(val) {
/* begin at the head */
let currentNode = this.head
/* we need to hold reference to the previous node */
let previousNode
/* while we have a node i.e. not passed the tail */
while(currentNode) {
/* if we find our value then break out */
if(currentNode.value === val) {
break;
}
/* with no value found currentNode we set this to previousNode */
previousNode = currentNode
/* we get the next node and assign it to currentNode */
currentNode = currentNode.next
}
/* we return undefined as we have found no node with that value */
if (currentNode=== null) {
return false;
}
// if the node is the head then we set our head to the next value
// of the head node
if (currentNode === this.head) {
this.head = this.head.next;
return;
}
/* so we remove our node by setting the node before it to the node in front of it */
previousNode.next = currentNode.next
}
该removeNode方法使我们对LinkedList工作原理有了很好的了解。
因此，只要再解释，我们是我们的第一个变量设置currentNode到head我们LinkedList，因为这是我们的第一个节点。然后，我们创建一个名为的占位符变量previousNode，该变量将在while循环中使用。我们从while条件开始循环currentNode-只要有条件，它将一直运行currentNode。
while循环中的第一个检查是检查我们是否具有价值。如果不这样做，则将我们设置previousNode为currentNode，并将我们currentNode设置为列表中的下一个节点。我们继续进行此过程，直到找到我们的价值或节点用完为止。
在后while循环，如果我们没有currentNode，我们返回false，这表明已无节点检出的用户。如果确实有一个currentNode，则检查是否currentNode是我们的头。如果是，我们设置head我们的LinkedList是第二点，这将成为head。
最后，如果我们currentNode不是我们的头，我们将设置previousNode为指向node我们前面的currentNode，这会将我们currentNode从对象中删除。
另一种非常流行的方法（面试官也可能会问您）是该removeTail方法。这种方法可以做到在锡罐上说的话，只需去除锡罐的尾巴即可LinkedList。可以想象，这比上面的方法容易得多，但工作原理类似。
我建议您先自己尝试一下，然后再看下面的代码（要使它更复杂一点，我们将不在tail构造函数中使用）：
removeTail() {
let currentNode = this.head;
let previousNode;
while (currentNode) {
/* the tail is the only node without a `next` value, so if no next value is present, then this must be our tail */
if (!currentNode.next) {
break;
}
// get a reference to our previous node
previousNode = currentNode;
// move onto the next node
currentNode = currentNode.next;
}
// to remove the tail, we set the previousNode.next to null
previousNode.next = null;
}
那是的一些主要方法LinkedList。您可能会遇到各种各样的方法，但是利用从以上中学到的知识，您应该能够管理所有这些方法。
哈希表
因此，我们要处理的倒数第二个数据结构是强大的哈希表。我故意将其放置在LinkedList解释之后，因为它们之间相距一百万英里。
哈希表是一种实现关联数组的数据结构，这意味着它将键映射到值。JavaScript对象是hash table，因为它存储键值对。
在视觉上，可以这样表示：
在开始讨论如何实现哈希表之前，我们需要讨论哈希函数的重要性。哈希函数的核心概念是，它接受任意大小的输入并返回固定大小的哈希码标识符。
hashThis('i want to hash this') => 7
哈希函数可能非常复杂或直接。GitHub上的每个文件都经过哈希处理，这使得每个文件的查找都非常快。散列函数背后的核心思想是，给定相同的输入将返回相同的输出。
涵盖了散列函数之后，该讨论如何实现散列表了。
三项行动，我们将讨论的insert，get和，最后，remove。
实现哈希表的核心代码如下：
class HashTable {
constructor(size) {
// define the size of our hash table, which will be used in our hashing function
this.size = size;
this.storage = [];
}
insert(key, value) { }
get() {}
remove() {}
// this is how we will hash our keys
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) {
// will give us an index in the array
const index = this.myHashingFunction(key, this.size);
// handle collision - hash function returns the same
// index for a different key - in complicated hash functions it is very unlkely
// that a collision would occur
if (!this.storage[index]) {
this.storage[index] = [];
}
// push our new key value pair
this.storage[index].push([key, value]);
}
因此，如果我们像这样调用insert方法：
const myHT = new HashTable(5);
myHT.insert("a", 1);
myHT.insert("b", 2);
您认为我们的哈希表会是什么样？
您可以看到我们的键值对已插入到索引为1和的表中4。
现在我们如何从哈希表中删除？
remove(key) {
// first we get the index of our key
// remember, the hashing function will always return the same index for the same
// key
const index = this.myHashingFunction(key, this.size);
// remember we could have more than one array at an index (unlikely)
let arrayAtIndex = this.storage[index];
if (arrayAtIndex) {
// let's loop over all the arrays at that index
for (let i = 0; i < arrayAtIndex.length; i++) {
// get the pair (a, 1)
let pair = arrayAtIndex[i];
// check if the key matches the key param
if (pair[0] === key) {
// delete the arrayatindex
delete arrayAtIndex[i];
// job done, so break out of the loop
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 the value
return pair[1];
}
}
}
}
我认为没有必要去做，因为它的作用与remove方法相同。
这是对哈希表的出色介绍，并且您可以说，它并不像最初看起来那样复杂。这是一种在各处使用的数据结构，因此是一个很好理解的结构！
二叉搜索树
可悲的是（或者可能是幸运的），这是我们要处理的最后一个数据结构-臭名昭著的二进制搜索树。
当我们想到二进制搜索树时，我们应该想到的三件事是：
- 根：这是树形结构的最高节点，没有父级
- 父级：它是节点的子级，也是节点的父级
- 子节点：此节点是节点的子节点，不一定有子节点
在二叉搜索树中，每个节点具有零个，一个或两个子代。左边的孩子称为左孩子，右边的孩子称为右孩子。在二叉搜索树中，左侧的子项必须小于右侧的子项。
在视觉上，您可以像这样描绘一个二进制搜索树：
一棵树的核心类如下：
class Tree {
constructor(value) {
this.root = null
}
add(value) {
// we'll implement this below
}
}
我们还将创建一个Node类来表示我们的每个节点。
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
好的，让我们实现该add方法。我对代码的注释非常好，但是如果您发现它令人困惑，请记住，我们所做的只是从根开始并检查每个节点的left和right。
add(value) {
// if we do not have a root, then we create one
if (this.root === null) {
this.root = new Node(value);
return;
}
let current = this.root;
// keep looping
while (true) {
// go left if our current value is greater
// than the value passed in
if (current.value > value) {
// if there is a left child then run the
// loop again
if (current.left) {
current = current.left;
} else {
current.left = new Node(value);
return;
}
}
// the value is smaller, so we go right
else {
// go right
// if there is a left child then run the
// loop again
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) {
// get the root
let current = this.root;
// while we have a node
while (current) {
// check if our current node has the value
if (value === current.value) {
return true; // leave the function
}
// we decide on the next current node by comparing our value
// against current.value - if its less go left else right
current = value < current.value ? current.left : current.right;
}
return false;
}
Add和Contains是二分搜索树的两种核心方法。对这两种方法的了解可以使您更好地了解如何解决日常工作中的问题。
结论
哇，这是一个很长的时间。我们已经在本文中介绍了很多内容，并且接受有关此知识的采访将使您处于有利位置。我真的希望您学到了一些东西（我知道我知道），并且希望您能更轻松地进行技术面试（尤其是讨厌的白板面试）。
编者注：这篇文章有什么问题吗？您可以在此处找到正确的版本。
插件：LogRocket，用于Web应用程序的DVR
LogRocket是一个前端日志记录工具，可让您像在您自己的浏览器中一样重播问题。LogRocket无需猜测错误发生的原因，也不要求用户提供屏幕截图和日志转储，而是让您重播会话以快速了解出了什么问题。无论框架如何，它都能与任何应用完美配合，并具有用于记录来自Redux，Vuex和@ ngrx / store的其他上下文的插件。
除了记录Redux动作和状态外，LogRocket还记录控制台日志，JavaScript错误，堆栈跟踪，带有标头+正文，浏览器元数据和自定义日志的网络请求/响应。它还使用DOM来记录页面上的HTML和CSS，甚至可以为最复杂的单页面应用程序重新创建像素完美的视频。
免费试用。
“ 了解您的JavaScript数据结构”一文首先出现在LogRocket博客上。
