数据结构
数组
- 有下标
- 顺序存储
数组的基本操作
1、读取元素
通过下标读取
2、更新元素
通过下标赋值
3、插入元素
- 尾部插入
- 中间插入
- 超范围插入
中间插入需将插入位置后面的元素往后移动，把要插入的元素放到插入位置。
function insert(array, element, index) {
const size = array.length;
if (index < 0 || index > size) {
console.error('超出数组实际元素范围');
}
// 从右向左循环，将元素逐个移动
for (let i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = element;
return array;
}
console.log(insert([1, 2, 3, 4, 5], 1, 2)); // [1, 2, 1, 3, 4, 5]
超范围插入，需要将数组扩容--将数组扩充到原来的2倍，然后将原来的元素复制过去。
4、删除元素
如果删除元素位于数组中间，需要将后面的元素向前移动。
function del(array, index) {
const size = array.length;
if (index < 0 || index > size) {
console.error('超出数组实际元素范围');
}
for (let i = index; i < size; i++) {
array[i] = array[i + 1];
}
array.length--;
return array;
}
console.log(del([1, 2, 3, 4, 5], 2)); // [1, 2, 4, 5]
数组的优势劣势
优势：高效的随机访问能力
劣势：插入、删除元素会导致大量元素移动位置，影响效率。
链表
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点所组成。
单向链表
单向链表的每个节点有两个部分组成：1、存放数据的变量data；2、指向下一个节点的指针 next。
双向链表
双向链表除了有 data 和 next 指针外，还有指向前一个节点的 prev 指针。
链表的基本操作
1、查找节点
查找第三个节点，需要从头节点开始，查找第二个节点，再查找第三个节点。时间复杂度最长为 O(n)。
2、更新节点
不考虑查找节点的过程，链表的更新过程和数组一样简单，直接替换成新数据即可。
3、插入节点
- 尾部插入
- 头部插入
- 中间插入
尾部插入：将最后一个节点的 next 指针指向新插入的节点即可。
头部插入：将新节点的 next 指针指向原来的头节点，把新节点变为链表的头节点。
中间插入：新节点的 next 指针指向插入位置的节点，插入位置的前一个节点的 next 指针指向新节点。
4、删除元素
- 头部删除
- 中间删除
- 尾部删除
尾部删除：将倒数第二个节点的 next 指向空。
头部删除：把原来的头节点的next指针指向的节点设为头节点。
中间删除：把删除位置的前一个节点的next指向删除位置的下一个节点。
数组 vs 链表
数组优势在于能够快速定位元素，对于读操作多，写操作少的场景，数组更适合。
链表相反。
栈和队列
物理结构和逻辑结构
物理结构：内存中实实在在的存储结构。
包括顺序存储结构（数组）、链式存储结构（链表）。
逻辑结构：抽象概念，依赖物理结构存在。
包括线性（顺序表、栈、队列）、非线性（树、图）。
栈
特点：先进后出，后进先出。
最先进的元素位于栈底，最后进的元素位于栈顶。
基本操作：
- 入栈：将新元素放入栈中，不过只能从栈顶放入，新元素的位置成为栈顶。
- 出栈：将元素弹出栈，只能从栈顶弹出，弹出元素的前一个元素的位置成为栈顶。
因为出栈入栈都只影响到最后一个元素，时间复杂度：O(1)。
队列
特点：先进先出，后进后出。
队列的出口端叫队头，队列的入口端叫队尾。
基本操作：
- 入队
- 出队
链表的入队、出队方式和栈基本相同，但是数组不一样。
用数组实现时，为了操作方便，把最后一个元素的下一个位置定位队尾。
数组的入队：只能从队尾加入，新元素的下一个位置变成队尾。
数组的出队：只能在队头一侧移除元素，出队元素的后一个元素成为新的队头。
如果不断出队，队列的容量会变得越来越小，需要采用循环队列的方式来维持队列的容量。
循环队列保留了出队元素的位置，新元素进来时，将队尾指向数组的首位，再进来新元素时，队尾往后一位移动，以此类推，直到 队尾下标+1 % 数组长度 === 0。
循环队列利用了数组的空间，避免了元素的移动。
入队出队的时间复杂度：O(1)
双端队列
既可以先进先出，也可以先进后出。
优先队列
优先级高的先出队。
不属于线性数据结构，基于二叉堆实现的。
散列表
也叫哈希表（hash table）。
提供 key: value 的映射，只要给出一个 key 就能高效找到所匹配的 value。时间复杂度：O(1)
哈希函数
散列表本质上也是一个数组。
通过某种方式，把 key 和数组下标进行转换——哈希函数。
散列表的读写操作
1、写操作
在散列表中插入新的键值对（key-value)。
1）通过哈希函数把 key 转换成数组的下标，比如 5
2) 如果数组下标 5 对应的位置没有元素，就把 value 写入到数组下标 5 的位置。
因为数组长度是有限的，插入的键值对越来越多，不同的 key 通过哈希函数获得的下标有可能是相同的。这种情况叫__哈希冲突__。
哈希冲突解决方法：
- 开放寻址法
- 链表法
开放寻址法：当一个 key 通过哈希函数获得对应的数组下标已被占用时，可以寻找下一个空档的位置。
链表法：
HashMap 数组的每个元素不仅时一个键值对，还是一个链表的头节点。每个键值对的 next 指向下一个键值对。
当新来的键值对映射到与之冲突的数组位置时，只需要插入到对应的链表中。
2、读操作
通过给定的 key，在散列表中查找对应的 value。
- 通过哈希函数把 key 转换成数组的下标，比如 5
- 找到下标为 5 的数组元素，如果对应的 key 是对的，则返回 value，否则继续在链表中查找。
3、扩容
散列表是基于数组的，所以也涉及扩容的问题。
当大量元素拥挤在相同数组下标下，形成很长的链表时，对后续插入和查找性能有很大影响时，需要扩容。
影响扩容的因素：
- Capacity: HashMap 的当前长度
- LoadFactor: HashMap 的负载因子，默认值为 0.75f
衡量是否需要扩容：
HashMap.size >= Capacity * LoadFactor
扩容操作：
1）扩容，创建一个新的 Entry 空数组，长度是原数组的 2 倍。
2）重新 Hash，遍历原 Entry 数组，把所有的 Entry 数组重新 Hash 到新数组中。-- 数组长度改变，Hash 规则随之改变。