#  javaScript-data-structures-and-algorithms

**Repository Path**: borealRoc/java-script-data-structures-and-algorithms

## Basic Information

- **Project Name**:  javaScript-data-structures-and-algorithms
- **Description**:  JavaScript 数据结构和算法
- **Primary Language**: JavaScript
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-04-06
- **Last Updated**: 2022-07-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#  javaScript-data-structures-and-algorithms

## javaScript 语法
### 1. 数据类型
- 基础数据类型：String, Number, Boolean, Null, Undefined, Symbol(), Bigint()
- 引用数据类型：Object(普通对象, Array, Function, Set, Map, JSON, 正则， Date, Math, Window……)
- 类型转换
    - 显式转换
    - 隐式转换
    - "+" 号转换规则
        - val + 字符串：val 转字符串
        - val1 + val2, 没有一边是字符串，则 val1 和 val2 都转数字
    - "==" 转换规则：
        - null == undefined, 其它与 null 和 undefined 都不相等
        - NaN 和任意值都不相等
        - 对象 == 字符串，对象转字符串
        - val1 == val2, 如果 val1 和 val2 类型不相同，都转换成数字后再进行比较
### 2. 内存空间
- 堆：引用数据类型的值
- 栈
    - 基础数据类型的声明和值
    - 引用数据类型的地址
    - **执行上下文 ECStack**：代码执行时所处的环境
        - 全局执行上下文 EC(G)
            1. 生成全局变量对象 VO(G)：存放全局变量
            2. EC(G)进栈
                - 词法分析
                - 变量提升：var 声明的变量（提升声明）；function 声明的函数（提升声明+定义）
                - 执行代码：自上而下执行（遇到函数执行语句，则EC(FN)进栈）
            3. EC(G)出栈：关闭窗口
        - 函数执行上下文 EC(FN)
            1. 生成函数活动对象 AO(FN)：存放函数局部变量+函数参数
            2. EC(FN)进栈
                - 初始化作用域链（声明时确定）
                    - **作用域链**：一个变量能取到值的范围（向上查找）
                    - **作用域**：一个变量能被渠道值得范围（向下查找）
                - 初始化 this：函数执行的主体（执行时确定）
                    1. 事件绑定：E
                    2. 普通函数
                        - obj.fn：有`.`，指向`.`前面的对象
                        - fn：没有`.`，非严格模式下指向 window
                            - 自执行函数
                            - 定时器中的函数
                            - 回调函数
                    3. 构造函数：实例
                    4. call/apply/bind：第一个参数
                    5. 箭头函数：没有自己的this，指向外部的this
                - 初始化实参：实参集合（arguments类数组：`arguments = [0: xx, 1: xx, ……]`）
                - 形参赋值：按值传递
                - 变量提升：var 声明的变量（提升声明）；function 声明的函数（提升声明+定义）
                - 执行代码：自上而下执行（遇到新的函数执行语句，则新的EC(FN)进栈）
            3. EC(FN)出栈：函数执行完毕（除非遇到**闭包**）
                - 表面上：函数内部的子函数引用函数内部的变量，就是闭包；
                - 实际上：
                    - 首先：函数在执行时，会形成一个私有的上下文，这个私有的上下文，*保护*了内部的变量和值不被外部影响；
                    - 其次：一般来说，函数在执行完后，因为垃圾回收机制，内部的变量和值会被释放掉；但是，如果此函数执行上下文中的变量和值在别的执行上下文被需要，导致它在执行完后无法释放，即内部的变量和值得到了*保存*；
                    - 以上：“保护”+“保存”的机制合起来，才是严格意义上的闭包。
        - eval
### 3. 面向对象
### 4. 事件循环
### 5. 模块化

## 二、算法复杂度 -- 大 O 表示法
- 概念：大概度量算法的效率；算法复杂度是相对于具体数据量(n)而言的。
- 常见形式
    - O(1)：常数
    - O(n)：线性
    - O(log(n))：对数
    - O(n*log(n))：线性 * 对数
    - O(n^2)：平方
    - O(2^n)：指数
    - O(n!)：阶乘

## 三、数据结构
### 1. 栈 Stack
- 先进后出，或后进先出；进栈或出栈只发生在栈顶（JS函数调用栈）
### 2. 队列 Queue
- 普通队列：先进先出，进队发生在队尾，出队发生在队首（JS异步任务队列）
- 双端队列：队首和队尾都能进队和出队
- 循环队列：队首出队后移到队尾进队（击鼓传花）
- 优先级队列：优先级高的元素在进队时要排在优先级低的元素的前面（vip客人优先登机）
### 3. 链表 LinkedList
- 单向链表：每个元素由一个存储自身元素的节点和指向下一个元素的引用组成：`head->node(e, next)->...->null`
    - 想比数组的优点：添加和移除元素很快 -- 不需要移动其它元素，时间复杂度为O(1)
    - 想比数组的缺点：查找元素慢 -- 在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素
- 双向链表：每个元素由一个存储自身元素的节点和指向下一个元素的引用以及上一个元素的引用组成：`head->node(prev, e, next)->...->tail->null`
    - 想比单向链表的优点：可以快速获取尾部元素；若想访问双向链表中的一个元素，如果 position > length/2，从尾部迭代可以加快查找速度
- 循环链表：（可单向，可双向）最后一个元素指向第一个元素，而不是 null：`head->node(prev, e, next)->...->tail->head`
### 4. 哈希表 HashTable
- 集合 vs 字典 vs 散列表
    - 集合 Set：无序，不重复的值组成，以 [值，值] 的形式存储数据 -- `{val1: val1, val2: val2, ...}`
    - 字典 Dictionary：无序，不重复的值组成，以 [键，值] 的形式存储数据 -- `{ke1: [ke1, val1], ke2: [key2, val2], ...}`
    - 散列表/哈希表：HashTable：字典的一种散列表实现方式，散列函数的作用是给定一个键，返回值在表中的地址，从而能快速检索到该键对应的值 -- `{hash(key1): [key1, val1], hash(key2): [key2, val2], ...}`
        - 好的散列函数：快速的计算，均匀的分布
- 特征
    - 优点：新增，删除，查找元素的速度很快：O(1)
    - 缺点：
        - 空间复杂度比较大，哈希表的空间利用率不高，底层使用的是数组，某些位置是没被利用到的
        - 元素无序，不能快速找出最大值/最小值等这些特殊的值
- 处理散列表中的冲突
    - 链地址法：为散列表的每一个位置创建一个 ***数组或链表*** 并将元素存储在里面
    - 开放地址法
        - 线性探查：元素直接存储在表中，如果 pos 被占了，则存到 pos + 1, +2 ...（直到不冲突）的位置
        - 二次探测：在线性探测的基础上进行了优化，x+1^2^、x+2^2^、x+3^3^……
        - 再哈希法：素直接存储在表中，如果 pos 被占了，则对 key 再次哈希化，且用的是和之前不同的哈希算法
### 5. 树 Tree