数据结构
Array
创建数组
const arr = new Array(10);
const arr = new Array(10).fill(1);
数组的访问与遍历
arr[0];
for (let i = 0; i < arr.length; i++) {}
arr.forEach((item, index) => {});
arr.map((item, index) => {});
二位数组初始化
const arr = new Array(10).fill([]); // !error 会变成十个一样的引用。 fill的机制：入参为引用类型时填充的是引用
const arr = new Array(10);
for (let i = 0; i < arr.length; i++) {
arr[i] = [];
}
const arr = new Array(10).fill(0).map(() => []);
增加元素
arr.push(1);
arr.unshift(1);
const arr = [1,2] arr.splice(1, 0, 3); //start,delete,add [1,3,2]
删除元素
arr.pop();
arr.shift();
arr.splice(1, 1);
Stack 栈
后进先出（LIFO,Last In First Out）
例子：往冰箱放东西和取东西
特征：
-
只允许从尾部添加元素 push
-
只允许从尾部删除元素 pop
Queue 队列
先进先出（FIFO,First In First Out）
例子：排队买东西
特征：
- 只允许从尾部添加元素 push
- 只允许从头部移除元素 shift
链表
链表也是有序的列表，类似数组也是线性结构，每个元素称为一个节点，有一个前驱和一个后继。不同的是链表节点在内存中可以是离散不连续的。
数组：数组在内存中一般对应一段连续的内存空间。所有每个元素的内存地址可以根据索引距 离数组头部距离计算出来，每个元素都可以通过数组的索引下标定位。 链表：节点不连续。所以需要节点与节点间的关联。无法通过索引直接访问链表中的元素。如果要访问某个节点，需要从头开始逐个访问next，直到找到该节点。为了确保起点节点是可抵达的，我们有时还会设定一个 head 指针来专门指向链表的开始位置：
{
val:1,
next: {
val:2,
next:...
}
}
链表的插入与删除
尾部插入
- 最后一个节点的next指向新节点
中间节点插入：
- 构建新节点
- 新节点的next指向后面的节点
- 前一个节点的next指向新节点
删除：
- 前一个节点的next指向要删除节点的下一个节点（跳过要删除的节点即可）
大多数计算机语言中，数组都对应着一段连续的内存空间，而链表则不对应连续的内存空间。JS 中不一定是，如果数组中元素存在不同的类型，对应的就是非连续的内存。此时 JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。
数组的定义：存储在连续内存空间的相同类型的元素集合。 JS数组未必是真正的数组。
假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的复杂度就是 O(n)。 链表增加/删除操作对应的复杂度是 O(1)。只需要改变目标节点/前驱节点/后继节点的指针指向，所以是常数级别复杂度。
数组的访问可以直接访问索引，复杂度是O(1)。 链表的访问必须遍历整个链表，遍历的复杂度是O(n)。
Tree 树
树是一种非线性结构，树节点可以有多个子节点，每个子节点可以继续拥有子节点。
树的层次：根节点所在的那一层记为第一层，其子节点所在的就是第二层，以此类推。
节点的高度与树的高度：叶子节点高度记为1，每向上一层高度加1，直至目标节点即为节点的高度。树中节点的最大高度被称为树的高度。
度的概念：一个节点开叉出去多少个子树，被记为节点的“度”。比如我们上图中，根节点的“度”就是3。
叶子节点：叶子节点就是度为0的节点。在上图中，最后一层的节点的度全部为0，所以这一层的节点都是叶子节点。
二叉树
- 如果没有根节点，可以是一棵空树
- 如果不是空树，必须由根节点、左子树、右子树组成，且左右子树都是二叉树。（普通的树不会区分左子树和右子树。但在二叉树中左右子树的位置是严格约定、不能交换的）