精读

 

数组

 

数组非常常用，它是一块连续的内存空间，因此可以根据下标直接访问，其查找效率为 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 的所有节点 < 根节点 < right 的所有节点，注意这里是所有节点，因此在判断时需要递归考虑所有情况。

 

二叉搜索树的好处在于，访问、查找、插入、删除的时间复杂度均为 O(logn)，因为无论何种操作都可以通过二分方式进行。但在最坏的情况会降级为 O(n)，原因是多次操作后，二叉搜索树可能不再平衡，最后退化为一个链表，就变成了链表的时间复杂度。

 

更好的方案有 AVL 树、红黑树等，像 JAVA、C++ 标准库实现的二叉搜索树都是红黑树。

 

字典树

 

字典树多用于单词搜索场景，只要给定一个单独开头，就可以快速查找到后面有几种推荐词。

 

比如上面的例子，输入 "o"，就可以快速查找到后面有 "ok" 与 "ol" 两个单词。要注意的是，每个节点都要有一个属性 isEndOfWord 表示到当前为止是否为一个完整的单词：比如 go 与 good 两个都是完整的单词，但 goo 不是，因此第二个 o 与第四个 d 都有 isEndOfWord 标记，表示读到这里就查到一个完整的单词了，叶子结点的标记也可以省略。