# 数据结构

# 数组

初始化一个数组，不知道它内部元素的情况下，推荐使用构造函数创建数组的方法

//不传任何参数，得到一个空数组
const arr = new Array()
//指定长度数组
const arr = new Array(7)
//指定长度，指定元素的数组
const arr = new Array(7).fill(7)

# 遍历数组

从性能上看，for循环遍历起来是最快的

# 矩阵

# 定义

二维数组，也就是数组套数组

在数学中，形如这样长方阵列排列的复数或实数集合，被称为“矩阵”。因此二维数组的别名就叫“矩阵”。

# 创建二维数组

# 错误写法

fill入参是引用类型，指向同一个堆内存空间，改变其中一个数组，其他的都会跟着改变

const arr =(new Array(7)).fill([])

# 正确写法

const len = arr.length
for(let i=0;i<len;i++) {
    // 将数组的每一个坑位初始化为数组
    arr[i] = []
}

# 二维数组的访问

两层for循环，依次类推，N 维数组需要 N 层循环来完成遍历。

// 缓存外部数组的长度
const outerLen = arr.length
for(let i=0;i<outerLen;i++) {
    // 缓存内部数组的长度
    const innerLen = arr[i].length
    for(let j=0;j<innerLen;j++) {
        // 输出数组的值，输出数组的索引
        console.log(arr[i][j],i,j)
    }
}

# 栈和队列

栈和队列的实现一般都依赖于数组

# 栈（Stack）

后进先出(LIFO，last in first out)的数据结构

最先出来的称为栈顶元素，主要关心栈顶元素

只用pop和push完成增删的数组

只允许从尾部添加元素
只允许从尾部取出元素

形象记忆：拿东西，后放进去的在表层，可以最先拿出来

# 队列（Quene）

先进先出（FIFO,First in first out）的数据结构

最先出来的称为队头元素，主要关心队头元素

只用push和shift完成增删的数组

只允许从尾部添加元素
只允许从头部移除元素

形象记忆：排队吃饭，先进先出

# 队列 vs 栈

特性	队列	栈
添加元素方法	push()	push()
删除元素方法	shift()	pop()
最先出来的	队头元素	栈顶元素
出入方式	先进先出	后进先出

# 链表

和数组相似，又是有序的列表，都是线性结构（有且只有一个前驱，有且只有一个后继）

# 不同点

数据单位的名称叫做“结点”，结点和结点的分布，在内存中可以是离散的

在链表中，每一个结点的结构都包括了两部分内容：

数据域(存储的是当前结点所存储的数据值)
指针域(代表下一个结点-后继结点的引用)

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

function ListNode(val) {
    this.val = val;
    this.next = null;
}

链表的结点间关系是通过 next 指针来维系的。因此，链表元素的添加和删除操作，本质上都是在围绕 next 指针做文章。

# 链表的删除

重点:定位目标结点的前驱结点

const target = node1.next
node1.next = target.next

# 链表节点的创建

在使用构造函数创建结点时，传入 val （数据域对应的值内容）、指定 next （下一个链表结点）即可：

const node = new ListNode(1)
node.next = new ListNode(2)

# 链表节点的插入

// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3

# 链表和数组的辨析

	链表	数组
增删时间复杂度	常数级别的复杂度，O(1)	随着数组长度 n 的增大而增大，呈一个线性关系。O(n)
查找时间复杂度	当我们试图读取某一个特定的链表结点时，必须遍历整个链表来查找它，呈线性规律，O(n)	直接访问索引、可以做到一步到位，这个操作的复杂度会被降级为常数级别O(1)
效率	插入/删除效率较高，访问效率较低	访问效率较高，而插入效率较低

JS数组未必是真正的数组 数组定义了不同类型的元素，对应的是一段非连续的内存，JS数组在此时不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现。

const arr = ['haha',1,{a:1}]

真正的数组：“存储在连续的内存空间里”这样的必要条件

链表明显的优点： 添加和删除元素都不需要挪动多余的元素。

# 树

度：一个结点开叉出去多少个子树，被记为结点的“度”
叶子结点：度为0的结点
树的高度：叶子结点高度为1，每向上一层高度加一，逐层向上累加至目标结点，所得的的值就是目标结点的高度，树中结点的最大高度称为“树的高度”
根结点所在的为第一层，子结点所在的为第二层

# 二叉树

# 条件

可以没有根结点，作为一棵空树存在
如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

# 结构

在 JS 中，二叉树使用对象来定义。它的结构分为三块：

数据域
左侧子结点（左子树根结点）的引用
右侧子结点（右子树根结点）的引用

# 创建

左右侧子节点预置为空

// 二叉树结点的构造函数
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
// 二叉树创建
const node  = new TreeNode(1)

# 遍历方式

按遍历顺序分为：

先序遍历
中序遍历
后序遍历
层次遍历

按实现方式分为：

递归遍历（先、中、后序遍历）
迭代遍历（层次遍历）

先序遍历：根结点 -> 左子树 -> 右子树 中序遍历：左子树 -> 根结点 -> 右子树 后序遍历：左子树 -> 右子树 -> 根结点

方便记忆：对于根结点遍历的位置来定的

# 遍历实现

// 先序遍历
function preOrder(root) {
  if(!root){
    return
  }
  // 当前遍历节点
  console.log(root.val)
  // 左子树
  preOrder(root.left)
  // 右子树
  preOrder(root.right)

}

数组的应用 →