算法基础数据结构
导读：精读 数组 数组非常常用，它是一块连续的内存空间，因此可以根据下标直接访问，其查找效率为 O(1 。 但数组的插入、删除效率较低，只有 O(n ，原因是为了保持数组的连续性，必须在插入或删除后对数组进行一些操作：比如插入第 K 个元素...
精读
数组
数组非常常用，它是一块连续的内存空间，因此可以根据下标直接访问，其查找效率为 O(1)。
但数组的插入、删除效率较低，只有 O(n)，原因是为了保持数组的连续性，必须在插入或删除后对数组进行一些操作：比如插入第 K 个元素，需要将后面元素后移；而删除第 K 个元素，需要将后面元素前移。
链表
链表是为了解决数组问题而发明出来的，它提升了插入、删除效率，而牺牲了查找效率。
链表的插入、删除效率是 O(1)，因为只要将对应位置元素断链、重连就可以完成插入、删除，而无需关心其他节点。
相应的查找效率就低了，因为存储空间不是连续的，所以无法像数组一样通过下标直接查找，而需要通过指针不断搜索，所以查找效率为 O(n)。
顺带一提，链表可以通过增加 .prev 属性改造为双向链表，也可以通过定义两个 .next 形成二叉树（.left .right）或者多叉树（N 个 .next）。
栈
栈是一种先入后出的结构，可以用数组模拟。
const stack: number[] = []
// 入栈
stack.push(1)
// 出栈
stack.pop()
堆
堆是一种特殊的完全二叉树，分为大顶堆与小顶堆。
大顶堆指二叉树根节点是最大的数，小顶堆指二叉树根节点是最小的数。为了方便说明，以下以大顶堆举例，小顶堆的逻辑与之相反即可。
大顶堆中，任意节点都比其叶子结点大，所以根节点是最大的节点。这种数据结构的优势是可以以 O(1) 效率找到最大值（小顶堆找最小值），因为直接取 stack[0] 就是根节点。
这里稍微提一下二叉树与数组结构的映射，因为采用数组方式操作二叉数，无论操作还是空间都有优势：第一项存储的是节点总数，对于下标为 K 的节点，其父节点下标是 floor(K / 2)，其子节点下标分别是 K * 2、K * 2 + 1，所以可以快速定位父子位置。
而利用这个特性，可以将插入、删除的效率达到 O(logn)，因为可以通过上下移动的方式调整其他节点顺序，而对于一个拥有 n 个节点的完全二叉树，树的深度为 logn。
哈希表
哈希表就是所谓的 Map，不同 Map 实现方式不同，常见的有 HashMap、TreeMap、HashSet、TreeSet。
其中 Map 和 Set 实现类似，所以以 Map 为例讲解。
首先将要存储的字符求出其 ASCII 码值，再根据比如余数等方法，定位到一个数组的下标，同一个下标可能对应多个值，因此这个下标可能对应一个链表，根据链表进一步查找，这种方法称为拉链法。
如果存储的值超过一定数量，链表的查询效率就会降低，可能会升级为红黑树存储，总之这样的增、删、查效率为 O(1)，但缺点是其内容是无序的。
为了保证内容有序，可以使用树状结构存储，这种数据结构称为 HashTree，这样时间复杂度退化为 O(logn)，但好处是内容可以是有序的。
树 &
二叉搜索树
二叉搜索树是一种特殊二叉树，更复杂的还有红黑树，但这里就不深入了，只介绍二叉搜索树。
二叉搜索树满足对于任意节点，left 的所有节点
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 算法基础数据结构
本文地址： https://pptw.com/jishu/658333.html