Table of Contents generated with DocToc
- 栈，又称堆栈，是一种后进先出（LIFO, Last in first out）的有序集合
- 堆，又称队列，是一种先进先出（FIFO, First in first out）的有序集合
链表储存有序的元素集合，其中的元素在内存中不是连续放置的。对于单向链表，每个元素由一个储存元素本身的节点和一个指向下一个元素的引用组成；而双向链表中的各元素则多了一个指向上一个元素的引用
链表的存在有什么意义呢？
对于传统的数组而言，我们增加或删除一个元素时，需要移动其之后的元素。比如删除了 index 为 10 的元素，那么之前 index 为 11 的元素需要向前挪动一位；同理，后面的每一个元素都要向前挪动一位。
除此以外，链表和数组的又一个差别是，数组可以直接通过 array[index] 访问到 index 位上的元素；而对于链表而言，需要从头开始遍历到目标元素。
由此可知，当我们在单向链表中某个位置上插入一个元素 node 时：
- 遍历查找到位于
index的元素current，以及它的上一位元素previous - 将
previous的next指向node - 将
node的next指向current
同理，删除某个位置上的元素，即是将该位置的上一个元素的 next 指向了该位置的下一位元素。
对于双向链表而言，则多了设置 pre 指向上一个元素的一步。
集合中的元素无序且唯一。可以按照插入元素的顺序来迭代集合中的各元素。
在 ES6 原生 API 中，支持了 Set 和 WeakSet。但要注意的一点是，尽管 Set 中的值是唯一的，且 JS 中 NaN !== NaN ，但在 Set 里 NaN 仍被认为是相同的值。除此以外，集合中以 value, value 的形式储存数据，即保存的 value 也会作为它本身的 key 便于索引查找。
与 Set 中 value 做 key 不同，字典 Map 需要给 value 制定一个 key 。它也用来储存不重复的数据。
在 ES6 原生 API 中，有 Map 以及 WeakMap 两种字典。
Set、 Map 相对于列表的优点在于，当需要储存较多数据时，不会因为其中某个元素的增删而影响到后面其他元素的索引（这一点优势链表也具有），同时，如果需要查找是否存在某个元素，则 Set、 Map 可以很快的进行判断，而列表则需要对元素进行遍历。
在 lodash 中，有 SetCache 对象。当数据元素个数大于设定的一定值时，会将数组转化到 SetCache 中，在底层其实就是将数组转换为了 key: value 的键值对，可以大大增快其索引速度。
WeakMap 和 WeakSet 相比较于 Map 和 Set 而言：
WeakMap和WeakSet对象中只能存放对象值, 不能存放原始值, 而Map和Set都可以WeakMap和WeakSet对象中存储的对象值都是被弱引用的, 如果没有其他的变量或属性引用这个对象值, 则这个对象值会被当成垃圾回收掉。- 因此，
WeakMap和WeakSet对象是无法被枚举的, 没有办法拿到它包含的所有元素
HashTable（或 HashMap ）。对散列中的元素而言，拥有一个特殊的键值（通常通过元素的 ASCII 码获取到），以此来增加索引的速度。除此以外，在删除某个元素以后，散列对该键的索引值将指向 undefined ，也就因此避免了改变其他元素的位置。
但其实有时候，不同元素计算得到的 key 依旧会有重复。如果是不加处理的普通散列，则当 key 重复时，后加入的元素会覆盖原有的元素。但我们可以通过分离链接 或者 线性探索 的方法解决这个问题。
- 分离链接
散列中的每一个 key 都指向一个链表；对于每个新增的元素，都会 push 到相对应的引用中去。这也就避免了元素 key 重复的问题，但很显然：占用了多余的储存空间。
- 线性探索
当想向表中某位置加入一个新元素时，如果索引为 index 的位置已经被其他元素占据了，则尝试 index + 1 的位置。如果仍然被占据，则继续尝试 index + 2 的位置；以此类推。
如其名，是一个树状的数据结构，由很多节点组成，各节点可以有祖先节点（父节点等）和后代节点（子节点等）。节点的深度取决于它祖先节点的数量；树的深度则取决于所有节点深度的最大值。
二叉树的一种。只允许在节点的左侧储存比父节点小的值，在右侧储存比父节点大的值。由此可知：
- 遍历 BST，每个节点只取其左侧的子节点进行递归，直至没有子节点。最终所得的数是树中的最小值。
- 遍历 BST，每个节点只取其右侧的子节点进行递归，直至没有子节点。最终所得的数是树中的最大值。
- 中序遍历
按照从最小到最大的顺序访问二叉树中的各节点。即左子节点 -> 父节点 -> 右子节点
- 先序遍历
先访问父节点，再访问其所有子节点。即父节点 -> 左子节点 -> 右子节点
- 后序遍历
先访问所有子节点，再访问父节点。即左子节点 -> 右子节点 -> 父节点
图是一种由边连接的节点（或顶点）。
- 相邻顶点：由一条边连接在一起的两个顶点
- 顶点的度：该顶点相邻顶点的数量
- 简单路径：不包含重复顶点的路径
- 环：简单路径的一种，表示从某顶点起始，不经过重复顶点，仍能回到初始顶点
- 无环：图中不存在环
- 连通：图中每两个顶点间都存在路径
- 强连通：图中每两个顶点间在双向上都存在路径
图可以通过邻接表这样的数据结构来表示。在邻接表中，用列表、链表或者散列来储存所有的顶点，并可以使用字典来储存顶点: [顶点所有的邻接顶点]
图的遍历思想是，追踪每一个第一次访问的节点，并且追踪有哪些节点还没被完全探索过（该顶点的每条边都被查看过则算完全探索）。
- 一开始，所有顶点被储存至待访问顶点列表中，并被标记为未查看。
- 每经过一个顶点，将其标记为已查看，未完全探索。
- 待与该顶点相连的所有变都经过以后，将该顶点标记为已完全探索。
- 每个顶点至多访问两次（未查看 -> 已查看，已查看 -> 已完全探索）
两者基本相同，但待访问顶点列表的数据结构不同。
- 深度优先搜索
Depth-First-Search：栈的形式储存待访问顶点，元素先入后出。
从指定的第一个顶点开始遍历图，沿着某路径直到最后一个顶点；然后原路退回后搜索下一个路径。即先深入访问，再增加广度。
基本搜索过程：
-
从某顶点（V）开始搜索，并标注为已查看，未完全探索
-
获取其所有未访问邻节点，放入栈中
2.1. 依次访问邻节点，后入的邻节点先被取出
2.2. 对每个邻节点重复 1 的操作（递归）
-
邻节点访问完毕之后，标注 V 为已完全探索
- 广度优先搜索
Breadth-First-Search：队列的形式储存待访问顶点，元素先入先出。
从指定的第一个顶点开始遍历图，先访问所有的相邻点，即访问图的一层，然后深入到下一层进行递归。
基本搜索过程：
-
创建队列 Queue
-
将某节点（V）放入队列
2.1. 按照先入先出的顺序，取出节点 V
2.2. 将节点 V 标注为已查看，未完全探索
2.3. 取出 V 的所有未访问邻节点，放入队列
2.4. 将 V 标注为已完全探索
通常，我们会综合考虑 CPU 占用、内存占用、硬盘占用、网络占用等多种情况来判断一个算法的好坏。综合起来后，使用时间复杂度这个概念来代表算法执行速度，以此进行衡量。
但一个算法的执行时间并不是固定的。总会有最佳、平均、最坏情况出现。而时间复杂度则代表其最坏情况下的运行时间。理由呢？参考微积分的一条基本概念就知道了：对于一个多项式，随着 x 变量的无限增大，其极限趋近于首项的值。例如，Y(x) = x^3 + x^2 + x 的值会在 x 趋向于无穷大时近似于 x^3。
在算法中，常见的时间复杂度的表示有（C 为常量）：
- O(b): 复杂度为 Cb，其中 b 是常量
- O(n)：当 n 很大时复杂度趋向于 Cn
- O(n^2)：当 n 很大时复杂度趋向于 Cn^2
- ...依次类推
具体什么意思呢？
假设有一个函数：
const add = (a, b) => a + b;不管执行时 a, b 参数是多少，它的执行时间是恒定可预测的，即时间与参数无关。我们就可以说它的时间复杂度是 O(1)。
同样是一个求和函数，扩展一下其可接受的参数：
const add = (...args) => args.reduce((p, c) => p + c, 0);让其接受的参数不限，利用 reduce 遍历求和。此时，该函数的时间复杂度变为 O(n)，其中 n 代表参数个数。
再来一个更复杂一点的，假设我们会接受一个嵌套的数组，需要依次取出里面的每一个元素，通过某种方法 format 以后，将其扁平化到一个数组中返回：
/*
* 接受形如 [[1, 2, 3], [4, 5, 6]] 的嵌套数组，返回
* [format(1), ..., format(6)]
* 其中 format 代表对每个参数都进行了特殊处理
*/
const flatArray = (arg) => {
const result = [];
const format = (item) => {
// do something special
};
arg.forEach((array) => {
array.forEach(item => result.push(format(item)));
});
return result;
};很傻的函数吧？反正只是为了学习。在这个函数里，我们有两层嵌套循环，因此，算法的时间复杂度为 O(n^2)。
同理，当函数有三层嵌套循环时，我们可以认为其时间复杂度为 O(n^3)，以此类推。
附一些可以参考的资料：