算法复习-常用数据结构
数组
⼀组连续的储存结构，⽤来储存同⼀种类型的数据
- 随机访问，O(1)
- 对插入、删除不友好，O(n)
class JSArray: public JSObject {}
JSArray是继承⾃JSObject的，所以在JavaScript中，数组可以是⼀个特殊的对象，内部也是以 key-value形式存储数据，所以JavaScript中的数组可以存放不同类型的值。
JSArray有两种存储方式：
- fast，基于
FixedArray，push和pop时可能会伴随着动态扩容或减容 - slow，基于
HashTable，以数组下标作为key
FixedArray是V8实现的⼀个类似于数组的类，它表示⼀段连续的内存，可以使⽤索引直接定位。新创建的空数组默认就是快数组。当数组满（数组的⻓度达到数组在内存中申请的内存容量最⼤值）的时候，继续push时，JSArray会进⾏动态的扩容，以存储更多的元素。当加⼊的索引值index⽐当前容量 capacity差值⼤于等于1024时（index - capacity >= 1024）或快数组新容量是扩容后的容量3倍之多时，快数组会被转成慢数组
慢数组以哈希表的形式存储在内存空间⾥，它不需要开辟连续的存储空间，但需要额外维护⼀个哈希表，与快数组相⽐，性能相对较差
栈
⼀种遵从后进先出(LIFO / Last In First Out)原则的有序集合
JavaScript使用(调用)栈来管理函数执行上下⽂，它记录了当前函数执⾏的位置，哪个函数正在被执⾏。
JavaScript基本类型保存在栈中
链表
链表不需要连续的内存空间，它是由⼀组零散的内存块通过指针连接⽽成。JavaScript中可以通过数组来模拟栈
链表有不同的结构，常见的有：
单链表，节点有一个
next属性，指向下一个节点。尾节点指向null双链表，节点有
next和pre属性分别指向上一个和下一个节点单循环链表，和单链表类似，不同的是单循环链表的尾节点指向的是头节点
查找：从头节点开始查找，时间复杂度为O(n)
插⼊或删除：在某⼀节点后插⼊或删除⼀个节点（后继节点）的时间复杂度为O(1)
常结合双指针来解决相关问题
队列
和栈类似，遵循先进先出 (FIFO) 原则的有序集合
- 查找：从队头开始查找，从时间复杂度为O(n)
- 插⼊或删除：进栈与出栈的时间复杂度为O(1)
常用来实现滑动窗口来解决实际问题
散列表
解决线性表在查找时的性能问题O(nlgn)~O(n)
通过散列算法，将key转换为散列值，而后通过散列值去散列表中查找
🌰：通过学号010121可以知道对应的同学在1年级1班21号
树
一种非线性结构
BST
二叉搜索树
在⼆叉树的基础上，增加了对⼆叉树上节点存储位置的限制：
- 左子节点值小于父节点的值
- 右节点的值大于父节点的值
在理想情况下，⼆叉树每多⼀层，可以存储的元素都增加⼀倍。也就是说 n 个元素的⼆叉搜索树，对应的树⾼为 O(logn)。所以我们查找元素、插⼊元素的时间也为 O(logn)。当然这是理想情况下，但在实际应⽤中，并不是那么理想，例如⼀直递增或递减的给⼀个⼆叉查找树插⼊数据，那么所有插⼊的元素就会⼀直出现在⼀个树的左节点上，数型结构就会退化为链表结构，时间复杂度就会趋于 O(n)，这是不好的。
AVL树用来解决这个问题
AVL
平衡搜索二叉树
在二叉搜索树的基础上满⾜左右⼦树⾼度不⼤于1
红黑树
红黑树也是一种特殊的二叉搜索树
在二叉搜索树的基础上添加以下限制：
- 节点是红⾊或⿊⾊
- 根节点必须是⿊⾊节点
- 所有的叶⼦节点都必须是值为
NULL的⿊节点 - 如果⼀个节点是红⾊的，则它两个⼦节点都是⿊⾊的
- 从任⼀节点到达它的每个叶⼦节点的所有的路径，都有相同数⽬的⿊⾊节点