你必须要知道的JavaScript数据结构与面试题解答

周sir | 2020年4月6日 | web前端技术, 算法 | 0 条评论 | 1083

英文原文 | https://dev.to/educative/7-javascript-data-structures-you-must-know-4k0m

原文作者 | Ryan Thelin和Amanda Fawcett

译文翻译 | web前端开发（web_qdkf）

解决编码问题时，效率至高无上–从编码小时数到运行时间，再到给解决方案的内存量。幸运的是，JavaScript开发人员使用了许多预先建立的数据结构，旨在解决共同的需求和解决实际问题。精通数据结构是分辩新人与经验丰富的开发者之间的一个主要因素。

也许你只是从数据结构入手，或者你已经编码多年，只需要复习一下。今天，我们将带你了解JS开发人员都需要知道的7个JavaScript数据结构。

以下就是我们今天要讲的内容：

什么是数据结构
JS数据结构
数据结构面试题
资源分享

那让我们开始吧。

一、什么是数据结构

高层数据结构是用于存储和组织数据的技术，这些数据使修改，导航和访问变得更加容易。数据结构决定了如何收集数据，我们可以用来访问数据的功能以及数据之间的关系。数据结构几乎用于计算机科学和编程的所有领域，从操作系统到基本的编码再到人工智能。

数据结构使我们能够：

管理和利用大型数据集
从数据库中搜索特定数据
针对特定程序量身定制的设计算法
一次处理来自用户的多个请求
简化并加速数据处理

数据结构对于有效，现实地解决问题至关重要。毕竟，我们组织数据的方式对性能和可用性有很大影响。实际上，大多数顶级公司都需要对数据结构有深刻的了解。这些技能证明你知道如何有效地管理数据。任何想要破解编码面试的人都需要掌握数据结构。

JavaScript具有原始和非原始数据结构。原始数据结构和数据类型是编程语言固有的。这些包括布尔值，空值，数字，字符串等。非原始数据结构不是由编程语言定义的，而是由程序员定义的。这些包括线性数据结构，静态数据结构和动态数据结构，例如队列和链接列表。

现在你已经了解了为什么数据结构那么重要了，接下来我们就来讨论一下每个JavaScript开发人员都需要知道的7种数据结构。

二、你需要知道的JavaScript数据结构

1、Array（数组）

数组是所有数据结构中最基本的，它主要将数据存储在内存中供以后使用。每个数组都有固定数量的单元格（取决于其创建），并且每个单元格都有用于选择其数据的相应数字索引。每当你想要使用数组时，你就可以访问其中的任何数据。

优点

易于创建和使用。
复杂数据结构的基础构建块

缺点

固定尺寸
插入/删除或重新排序值昂贵
排序效率低下

应用领域

基本电子表格
在复杂的结构中，例如哈希表

有关更深入的说明，请参阅有关数组的Edpresso文章！（地址：https://www.educative.io/edpresso/what-are-arrays-in-javascript）

2、Queues（队列）

队列在概念上类似于堆栈。两者都是顺序结构，但按输入顺序而不是最新元素对处理元素进行排队。结果，可以将队列视为堆栈的FIFO（先进先出）版本。这些作为请求的缓冲区很有用，按照接收到的顺序存储每个请求，直到可以处理为止。

为了获得视觉效果，请考虑单车道隧道：第一个进入隧道的汽车，一定是第一个离开的汽车。如果其他汽车希望退出但先停车，则所有汽车都必须等待先退出才能继续。

优点

动态尺寸
按接收顺序订购数据
运行时间短

缺点

只能检索最早的元素

应用领域

在接收频繁数据时作为缓冲区有效
存储订单敏感数据（如存储的语音邮件）的便捷方法
确保最早的数据先被处理

3、 Linked List（链表）

链接列表是一种数据结构，与前三个列表不同，它不使用数据在内存中的物理放置。这意味着链接列表而不是索引或位置，而是使用引用系统：元素存储在包含指向下一个节点的指针的节点中，重复直到所有节点都链接为止。该系统无需重新组织即可有效地插入和取出物品。

优点

有效插入和删除新元素
重组数组简单

缺点

比数组使用更多的内存
检索特定元素效率低下
向后遍历列表效率低下

应用领域

最适合在必须快速连续从未知位置添加和删除数据的情况下使用

有关更深入的说明，请参阅链接列表上的Edpresso文章！（地址：https://www.educative.io/edpresso/what-is-a-linked-list）

4、Tree（树）

树是另一种基于关系的数据结构，专门用于表示层次结构。像链表一样，节点包含数据元素和指示其与直接节点关系的指针。

每棵树都有一个“根”节点，所有其他节点都从该“根”节点分支。根包含对直接在其下的所有元素的引用，这些元素称为“子节点”。随着每个子节点继续分支到更多的子节点。

具有链接的子节点的节点称为内部节点，而没有子节点的节点称为外部节点。常见的树类型是“二进制搜索树”，用于轻松搜索存储的数据。这些搜索操作非常高效，因为其搜索持续时间不取决于节点数，而是取决于树下的层数。

这种类型的树由四个严格规则定义：

左子树仅包含元素小于根的节点。
右侧子树仅包含元素大于根的节点。
左和右子树也必须是二叉搜索树。他们必须遵循上述规则并以其树的“根”作为根。
不能有重复的节点，即两个节点不能具有相同的值。

优点

存储分层关系的理想选择
动态尺寸
快速插入和删除操作
在二叉搜索树中，插入的节点会立即排序。
二进制搜索树可以有效地进行搜索；长度仅为0（高度）。

缺点

缓慢重新排列节点
子节点不保留有关其父节点的信息
二进制搜索树不如更复杂的哈希表快
如果未使用平衡子树实现，则二叉搜索树可以退化为线性搜索（扫描所有元素）。

应用领域

存储分层数据，例如文件位置。
二进制搜索树非常适合需要搜索或排序数据的任务。

有关更深入的解释，请参阅有关树木的Edpresso文章！（地址：https://www.educative.io/edpresso/what-is-a-tree）

5、**Graph（图）**

图表是基于关系的数据结构，有助于存储类似Web的关系。在图中称为每个节点或顶点，都有一个标题（A，B，C等），包含的值以及与其他顶点的链接（称为边）列表。

在上面的示例中，每个圆是一个顶点，每条线是一条边。如果是书面形式，则此结构如下所示：

V = {a，b，c，d}

E = {ab，ac，bc，cd}

尽管一开始很难直观显示，但这种结构对于以文本形式传达关系图（从电路到训练网络）的价值而言，都是非常宝贵的。

优点

可以通过文字快速传达视觉效果
可用于建模多种主题，只要它们包含关系结构

缺点

在更高的级别上，将文本转换为图像可能会很耗时。
可能很难看到现有的边或给定顶点已连接多少条边

应用领域

网络表示
建模社交网络，例如Facebook。

有关更深入的说明，请参阅有关图表的Edpresso文章！（地址：https://www.educative.io/edpresso/what-is-a-graph-data-structure）

6、哈希表（地图）

哈希表是一个复杂的数据结构，能够存储大量信息并有效地检索特定元素。该数据结构依赖于键/值对的概念，其中“键”是搜索到的字符串，“值”是与该键配对的数据。

使用预定义的哈希函数，将每个搜索到的键从其字符串形式转换为称为哈希的数值。然后，此哈希指向存储桶-表中较小的子组。然后，它将在存储桶中搜索最初输入的键，并返回与该键关联的值。

优点

键可以采用任何形式，而数组的索引必须为整数
高效的搜索功能
每次搜索的操作次数不变
插入或删除操作的固定成本

缺点

冲突：两个键转换为相同的哈希码或两个哈希码指向相同值时引起的错误。
这些错误可能很常见，并且经常需要对哈希函数进行全面检查。

应用领域

数据库存储
按名称查找地址

从键和值的类型到其哈希函数的工作方式，每个哈希表都可以有很大不同。由于这些差异以及哈希表的多层方面，几乎不可能如此概括。

有关更深入的说明，请参阅有关哈希表的Edpresso文章！（地址：https://www.educative.io/edpresso/what-is-a-hash-table）

继续学习。

学习JavaScript数据结构，而无需遍历视频或文档。Educative的基于文本的课程易于浏览，并具有实时编码环境-使学习快速高效。

JavaScript中的数据结构：面试复习（地址:https://www.educative.io/courses/data-structures-in-javascript-an-interview-refresher)

三、数据结构面试题

对于许多开发人员和程序员而言，数据结构对于破解编程面试至关重要。有关数据结构的问题是现代编程开发面试中的基础。实际上，对于你的应聘能力和入门级职位，有很多话要说。

今天，我们将讨论JavaScript数据结构的七个常见编码面试问题，针对我们上面讨论的每个数据结构。每个人还将基于BigO符号理论讨论其时间复杂度。

1、数组：从数组中删除所有偶数整数

问题陈述：实现一个函数removeEven（arr），该函数在其输入中使用数组arr并从给定数组中删除所有偶数元素。

输入：随机整数数组

[1,2,4,5,10,6,3]

输出：仅包含奇数整数的数组

[1,5,3]

你可以通过两种方式解决面试中的问题。让我们讨论一下。

解决方案1：“手动”执行

此方法从数组的第一个元素开始。如果当前元素不是偶数，它将把该元素推入新数组。如果是偶数，它将移动到下一个元素，重复直到到达数组的末尾。关于时间复杂度，由于必须迭代整个数组，因此此解决方案位于O（n）O（n）中。

解决方案2：使用filter（）和lambda函数

此解决方案也从第一个元素开始，并检查它是否为偶数。如果是偶数，它将滤除此元素。如果不是，则跳到下一个元素，重复此过程，直到到达数组末尾。

过滤器函数使用lambda或arrow函数，它们使用更短，更简单的语法。过滤器过滤掉lambda函数为其返回false的元素。其时间复杂度与先前解决方案的时间复杂度相同。

2、堆栈：使用堆栈检查括号是否平衡

问题陈述：实现isBalanced（）函数以仅包含大括号{}，方括号[]和圆括号（）的字符串。该函数应告诉我们字符串中的所有括号是否平衡。这意味着每个开头括号都将有一个结尾括号。例如，{[]}是平衡的，而{[}]不是平衡的。

输入：仅由（，），{，}，[和]组成的字符串

exp = "{[({})]}"

输出：如果表达式没有平衡的括号，则返回False。如果是，则该函数返回True。

True

为了解决这个问题，我们可以简单地使用一堆字符。在下面的代码中查看其工作方式。

"use strict";
const Stack = require('./Stack.js');

function isBalanced(exp) {
var myStack = new Stack();
//Iterate through the string exp
for (var i = 0; i < exp.length; i++) {
//For every closing parenthesis check for its opening parenthesis in stack


if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {

if (myStack.isEmpty()) {

return false
            }
let output = myStack.pop();
//If you can't find the opening parentheses for any closing one then returns false.
if (((exp[i] == "}") && (output != "{")) || ((exp[i] == ")") && (output != "(")) || ((exp[i] == "]") && (output != "["))) {
return false;
            }

        } else {
//For each opening parentheses, push it into stack
            myStack.push(exp[i]);
        }

    }
//after complete traversal of string exp, if there's any opening parentheses left
//in stack then also return false.
if (myStack.isEmpty() == false) {
return false
    }
//At the end return true if you haven't encountered any of the above false conditions.
return true
}


var inputString = "{[()]}"
console.log(inputString)
console.log(isBalanced(inputString))

inputString = "{[([({))]}}"
console.log(inputString)
console.log(isBalanced(inputString))

输出：

{[（）]}

真正

{[（[（（（））]}}

假

要查看此解决方案的其余代码，请转到Educative.io在嵌入式环境中运行代码。

此过程将一次遍历字符串一个字符。我们可以根据两个因素确定字符串不平衡：

堆栈为空。

堆栈中的顶部元素不是正确的类型。

如果这些条件之一成立，则返回False。

如果括号是开括号，则将其推入堆栈。如果最终所有平衡，则堆栈将为空。如果不为空，则返回False。由于我们仅遍历字符串exp一次，因此时间复杂度为O（n）。

3、队列：生成从1到n的二进制数

问题陈述：实现一个函数findBin（n），该函数将使用队列以字符串形式生成从1到n的二进制数。

输入：正整数n

n = 3

输出：以1到n的字符串形式返回二进制数

result = ["1","10","11"]

解决此问题的最简单方法是使用队列从以前的号码生成新号码。让我们分解一下。

"use strict";
const Queue = require('./Queue.js');
function findBin(n) {
let result = [];
let myQueue = new Queue();
var s1, s2;
    myQueue.enqueue("1");
for (var i = 0; i < n; i++) {

        result.push(myQueue.dequeue());
        s1 = result[i] + "0";
        s2 = result[i] + "1";

        myQueue.enqueue(s1);
        myQueue.enqueue(s2);

    }

return result;
}

console.log(findBin(10))

输出：

['1'，'10'，'11'，'100'，'101'，'110'，'111'，'1000'，'1001'，'1010']

要查看此解决方案的其余代码，请转到Educative.io在嵌入式环境中运行代码。

关键是通过将0和1附加到先前的二进制数来生成连续的二进制数。澄清，

如果将0和1附加到1，则可以生成10和11。

如果将0和1附加到10，则会生成100和101。

一旦我们生成了一个二进制数，它将被排队到队列中，这样，当我们将0和1附加到队列中时，如果我们附加了0和1，就可以生成新的二进制数。由于队列遵循“先进先出”属性，因此将排队的二进制数出队，以使所得数组在数学上正确。

看上面的代码。在第7行，将1排队。为了生成二进制数字序列，将数字出队并存储在数组结果中。在第11-12行，我们将0和1附加起来以产生下一个数字。这些新数字也排在第14-15行。队列将采用整数值，因此它将在排队时将字符串转换为整数。

该解决方案的时间复杂度为O（n）O（n），因为恒定时间操作执行了n次。

4、链接列表：反向链接列表

问题陈述：编写反向函数以获取一个单链列表并将其反向定位。

输入：单链接列表

LinkedList = 0->1->2->3-4

输出：反向链接列表

LinkedList = 4->3->2->1->0

解决此问题的最简单方法是使用迭代指针操作。让我们来看看。

"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');

function reverse(list) {
  let previousNode = null;
  let currentNode = list.getHead(); // The current node
  let nextNode = null; // The next node in the list

  //Reversal
  while (currentNode != null) {
    nextNode = currentNode.nextElement;
    currentNode.nextElement = previousNode;
    previousNode = currentNode;
    currentNode = nextNode;
  }

  //Set the last element as the new head node
  list.setHead(previousNode);

}

let list = new LinkedList();
list.insertAtHead(4);
list.insertAtHead(9);
list.insertAtHead(6);
list.insertAtHead(1);
list.insertAtHead(0);
list.printList();
reverse(list);
list.printList();

输出：

0-> 1-> 6-> 9-> 4->空

4-> 9-> 6-> 1-> 0->空

要查看此解决方案的其余代码，请转到Educative.io在嵌入式环境中运行代码。

我们使用循环遍历输入列表。对于当前节点，其与先前节点的链接被反向。然后，next将下一个节点存储在列表中。让我们按行细分。

第22行-将当前节点的nextElement存储在next中

第23行-将当前节点的nextElement设置为Previous

第24行-将当前节点设为新的上一个节点，以进行下一次迭代

第25行-使用next转到下一个节点

第29行-我们将头指针重置为指向最后一个节点

由于列表仅被遍历一次，因此该算法以O（n）运行。

5、树：在二分搜索树中找到最小值

问题陈述：使用findMin（root）函数在二进制搜索树中查找最小值。

输入：二叉搜索树的根节点

bst = {
6 -> 4,9
4 -> 2,5
9 -> 8,12
12 -> 10,14
}
where parent -> leftChild,rightChild

输出：该二进制搜索树中的最小整数值

2

让我们看一个解决这个问题的简单方法。

解决方案：迭代findMin（）

该解决方案首先检查根是否为空。如果是，则返回null。然后，它移动到左侧子树，并继续每个节点的左侧子级，直到到达最左侧的子级。

"use strict";
const BinarySearchTree = require('./BinarySearchTree.js');
const Node = require('./Node.js');

function findMin(rootNode)
{
if(rootNode == null)
return null;
else if(rootNode.leftChild == null)
return rootNode.val
else
return findMin(rootNode.leftChild)
}  
var BST = new BinarySearchTree(6)
BST.insertBST(20)
BST.insertBST(-1)

console.log(findMin(BST.root))

输出：

-1

要查看此解决方案的其余代码，请转到Educative.io在嵌入式环境中运行代码。

6、图：移除边缘

问题陈述：实现removeEdge函数以将源和目标作为参数。它应该检测它们之间是否存在边缘。

输入：图形，源和目标

输出：去除了源和目标之间的边缘的图形。

removeEdge(graph, 2, 3)

这个问题的解决方案非常简单：我们使用索引和删除。看一看.

"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
const Graph = require('./Graph.js');
function removeEdge(graph, source, dest)
{
if(graph.list.length == 0)
{
return graph;  
}
if(source >= graph.list.length || source < 0){
return graph;  }
if(dest >= graph.list.length || dest < 0){
return graph;  
}  
graph.list.deleteVal(dest);
return graph;}let g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(4, 0);
console.log("Before removing edge")g.printGraph();
removeEdge(g, 1, 3);
console.log("\nAfter removing edge")g.printGraph();

要查看此解决方案的其余代码，请转到Educative.io在嵌入式环境中运行代码。

由于我们的顶点存储在数组中，因此我们可以访问源链接列表。然后，我们为链接列表调用delete函数。该解决方案的时间复杂度为O（E），因为我们可能必须遍历E边。

7、哈希表：将最大堆转换为最小堆

问题陈述：实现函数convertMax（maxHeap）将二进制最大堆转换为二进制最小堆。maxHeap应该是maxHeap格式的数组，即父级大于子级。
输入：最大堆

maxHeap = [9,4,7,1,-2,6,5]

输出：返回转换后的数组

result = [-2,1,5,9,4,6,7]

为了解决这个问题，我们必须最小化所有父节点。看一看。

我们将maxHeap视为常规数组，然后对其重新排序以准确表示最小堆。您可以在上面的代码中看到完成此操作。然后，convertMax（）函数通过调用minHeapify（）函数从最低父节点还原所有节点上的堆属性。关于时间复杂度，此解决方案花费O（nlog（n））O（nlog（n））时间。

四、资源

当涉及到JavaScript中的数据结构时，显然有很多东西要学习。因此，我们整理了此资源列表，以使您快速了解所需的信息。

文章