JavaScript数据结构总结
⼀、什么是数据结构⾼层数据结构是⽤于存储和组织数据的技术，这些数据使修改，导航和访问变得更加容易。数据结构决定了如何收集数据，我们可以⽤来访问数据的功能以及数据之间的关系。数据结构⼏乎⽤于计算机科学和编程的所有领域，从操作系统到基本的编码再到⼈⼯智能。数据结构使我们能够：
管理和利⽤⼤型数据集
从数据库中搜索特定数据
针对特定程序量⾝定制的设计算法
⼀次处理来⾃⽤户的多个请求
简化并加速数据处理
数据结构对于有效，现实地解决问题⾄关重要。毕竟，我们组织数据的⽅式对性能和可⽤性有很⼤影响。实际上，⼤多数顶级公司都需要对数据结构有深刻的了解。这些技能证明你知道如何有效地管理数据。任何想要破解编码⾯试的⼈都需要掌握数据结构。JavaScript具有原始和⾮原始数据结构。原始数据结构和数据类型是编程语⾔固有的。这些包括布尔值，空值，数字，字符串等。⾮原始数据结构不是由编程语⾔
定义的，⽽是由程序员定义的。这些包括线性数据结构，静态数据结构和动态数据结构，例如队列和链接列表。现在你已经了解了为什么数据结构那么重要了，接下来我们就来讨论⼀下每个JavaScript开发⼈员都需要知道的7种数据结构。⼆、你需要知道的JavaScript数据结构
1、Array（数组）
数组是所有数据结构中最基本的，它主要将数据存储在内存中供以后使⽤。每个数组都有固定数量的单元格（取决于其创建），并且每个单元格都有⽤于选择其数据的相应数字索引。每当你想要使⽤数组时，你就可以访问其中的任何数据。
优点
易于创建和使⽤。
复杂数据结构的基础构建块
缺点
固定尺⼨
插⼊/删除或重新排序值昂贵
排序效率低下
应⽤领域
基本电⼦表格
在复杂的结构中，例如哈希表
2、Queues（队列）
队列在概念上类似于堆栈。两者都是顺序结构，但按输⼊顺序⽽不是最新元素对处理元素进⾏排队。结果，可以将队列视为堆栈的FIFO（先进先出）版本。这些作为请求的缓冲区很有⽤，按照接收到的顺序存储每个请求，直到可以处理为⽌。
为了获得视觉效果，请考虑单车道隧道：第⼀个进⼊隧道的汽车，⼀定是第⼀个离开的汽车。如果其他汽车希望退出但先停车，则所有汽车都必须等待先退出才能继续。优点
动态尺⼨
按接收顺序订购数据
运⾏时间短
缺点
只能检索最早的元素
应⽤领域
在接收频繁数据时作为缓冲区有效
存储订单敏感数据（如存储的语⾳邮件）的便捷⽅法
确保最早的数据先被处理
3、 Linked List（链表）
链接列表是⼀种数据结构，与前三个列表不同，它不使⽤数据在内存中的物理放置。这意味着链接列表⽽不是索引或位置，⽽是使⽤引⽤系统：元素存储在包含指向下⼀个节点的指针的节点中，重复直到所有节点都链接为⽌。该系统⽆需重新组织即可有效地插⼊和取出物品。
优点
有效插⼊和删除新元素
重组数组简单
缺点
⽐数组使⽤更多的内存
检索特定元素效率低下
向后遍历列表效率低下
应⽤领域
最适合在必须快速连续从未知位置添加和删除数据的情况下使⽤
4、Tree（树）
树是另⼀种基于关系的数据结构，专门⽤于表⽰层次结构。像链表⼀样，节点包含数据元素和指⽰其与直接节点关系的指针。每棵树都有⼀个“根”节点，所有其他节点都从该“根”节点分⽀。根包含对直接在其下的所有元素的引⽤，这些元素称为“⼦节点”。随着每个⼦节点继续分⽀到更多的⼦节点。具有链接的
⼦节点的节点称为内部节点，⽽没有⼦节点的节点称为外部节点。常见的树类型是“⼆进制搜索树”，⽤于轻松搜索存储的数据。这些搜索操作⾮常⾼效，因为其搜索持续时间不取决于节点数，⽽是取决于树下的层数。
这种类型的树由四个严格规则定义：
左⼦树仅包含元素⼩于根的节点。
右侧⼦树仅包含元素⼤于根的节点。
左和右⼦树也必须是⼆叉搜索树。他们必须遵循上述规则并以其树的“根”作为根。
不能有重复的节点，即两个节点不能具有相同的值。
优点
存储分层关系的理想选择
动态尺⼨
快速插⼊和删除操作
在⼆叉搜索树中，插⼊的节点会⽴即排序。
⼆进制搜索树可以有效地进⾏搜索；长度仅为0（⾼度）。
缺点
缓慢重新排列节点
⼦节点不保留有关其⽗节点的信息
⼆进制搜索树不如更复杂的哈希表快
如果未使⽤平衡⼦树实现，则⼆叉搜索树可以退化为线性搜索（扫描所有元素）。
应⽤领域
存储分层数据，例如⽂件位置。
⼆进制搜索树⾮常适合需要搜索或排序数据的任务。
5、Graph（图）
图表是基于关系的数据结构，有助于存储类似Web的关系。在图中称为每个节点或顶点，都有⼀个标题（A，B，C等），包含的值以及与其他顶点的链接（称为边）列表。
在上⾯的⽰例中，每个圆是⼀个顶点，每条线是⼀条边。如果是书⾯形式，则此结构如下所⽰：V = {a，b，c，d}E = {ab，ac，bc，cd}尽管⼀开始很难直观显⽰，但这种结构对于以⽂本形式传达关系图（从电路到训练⽹络）的价值⽽⾔，都是⾮常宝贵的。优点
可以通过⽂字快速传达视觉效果
可⽤于建模多种主题，只要它们包含关系结构
缺点
在更⾼的级别上，将⽂本转换为图像可能会很耗时。
可能很难看到现有的边或给定顶点已连接多少条边
应⽤领域
⽹络表⽰
建模社交⽹络，例如Facebook。
6、哈希表（地图）
哈希表是⼀个复杂的数据结构，能够存储⼤量信息并有效地检索特定元素。该数据结构依赖于键/值对的概念，其中“键”是搜索到的字符串，“值”是与该键配对的数据。
使⽤预定义的哈希函数，将每个搜索到的键从其字符串形式转换为称为哈希的数值。然后，此哈希指向存储桶-表中较⼩的⼦组。然后，它将在存储桶中搜索最初输⼊的键，并返回与该键关联的值。优点
键可以采⽤任何形式，⽽数组的索引必须为整数
⾼效的搜索功能
每次搜索的操作次数不变
插⼊或删除操作的固定成本
缺点
冲突：两个键转换为相同的哈希码或两个哈希码指向相同值时引起的错误。
这些错误可能很常见，并且经常需要对哈希函数进⾏全⾯检查。
应⽤领域
数据库存储
按名称查地址
三、数据结构⾯试题
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
js的基本数据类型
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;
for (var i = 0; i < n; i++) {
result.push(myQueue.dequeue());
s1 = result[i] + "0";
s2 = result[i] + "1";
}
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 = Head(); // The current node
let nextNode = null; // The next node in the list
//Reversal
while (currentNode != null) {
nextNode = Element;
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())
输出：