掌握了不同数据结构的特点，可以让你在面对不同问题时，采用合适的数据结构处理，达到事半功倍的效果。
所以这次我们详细介绍各类数据结构的特点，希望你可以融会贯通。
精读。数组。
数组非常常用，它是一块连续的内存空间，因此可以根据下标直接访问，其查找效率为o(1)。
但数组的插入、删除效率较低，只有o(n)，原因是为了保持数组的连续性，必须在插入或删除后对数组进行一些操作：比如插入第k个元素，需要将后面元素后移；而删除第k个元素，需要将后面元素前移。
链表。链表是为了解决数组问题而发明出来的，它提升了插入、删除效率，而牺牲了查找效率。
链表的插入、删除效率是o(1)，因为只要将对应位置元素断链、重连就可以完成插入、删除，而无需关心其他节点。
相应的查找效率就低了，因为存储空间不是连续的，所以无法像数组一样通过下标直接查找，而需要通过指针不断搜索，所以查找效率为o(n)。
顺带一提，链表可以通过增加。
prev属性改造为双向链表，也可以通过定义两个。
next形成二叉树（.left
right）或者多叉树（n个。
next）。
栈。栈是一种先入后出的结构，可以用数组模拟。
const stack: number
/入栈。/出栈。
堆。堆是一种特殊的完全二叉树，分为大顶堆与小顶堆。
大顶堆指二叉树根节点是最大的数，小顶堆指二叉树根节点是最小的数。为了方便说明，以下以大顶堆举例，小顶堆的逻辑与之相反即可。
大顶堆中，任意节点都比其叶子结点大，所以根节点是最大的节点。这种数据结构的优势是可以以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)，原因是多次操作后，二叉搜索树可能不再平衡，最后退化为一个链表，就变成了链表的时间复杂度。
更好的方案有**l树、红黑树等，像j**a、c++标准库实现的二叉搜索树都是红黑树。
字典树。字典树多用于单词搜索场景，只要给定一个单独开头，就可以快速查找到后面有几种推荐词。
比如上面的例子，输入"o"，就可以快速查找到后面有"ok"与"ol"两个单词。要注意的是，每个节点都要有一个属性。
isendofword
表示到当前为止是否为一个完整的单词：比如。go与。
good两个都是完整的单词，但。
goo不是，因此第二个。
o与第四个。d都有。
isendofword
标记，表示读到这里就查到一个完整的单词了，叶子结点的标记也可以省略。
并查集。并查集用来解决团伙问题，或者岛屿问题，即判断多个元素之间是属于某个集合。并查集的英文是union and find，即归并与查找，因此并查集数据结构可以写成一个类，提供两个最基础的方法。
union与。
find。其中。
union可以将任意两个元素放在一个集合，而。
find可以查找任意元素属于哪个根集合。
并查集使用数组的数据结构，只是有以下特殊含义，设下标为k：
nums[k]
表示其所属的集合，如果。
nums[k] =k
表示它是这个集合的根节点。
如果要数一共有几个集合，只要数有多少满足。
nums[k] =k
条件的数目即可，就像数有几个团伙，只要数有几个老大即可。
并查集的实现不同，数据也会有微妙的不同，高效的并查集在插入时，会递归将元素的值尽量指向根老大，这样查找判断时计算的快一些，但即便指向的不是根老大，也可以通过递归的方式找到根老大。
布隆过滤器。
bloom filter只是一个过滤器，可以用远远超过其他算法的速度把未命中的数据排除掉，但未排除的也可能实际不存在，所以需要进一步查询。
布隆过滤器是如何做到这一点的呢？就是通过二进制判断。
如上图所示，我们先存储了a、b两个数据，将其转化为二进制，将对应位置改为1，那么当我们再查询a或b时，因为映射关系相同，所以查到的结果肯定存在。
但查询c时，发现有一项是0，说明c一定不存在；但查询d时，恰好两个都查到是1，但实际d是不存在的，这就是其产生误差的原因。
布隆过滤器在比特币与分布式系统中使用广泛，比如比特币查询交易是否在某个节点上，就先利用布隆过滤器挡一下，以快速跳过不必要的搜索，而分布式系统计算比如map reduce，也通过布隆过滤器快速过滤掉不在某个节点的计算。
总结。最后给出各数据结构。
访问、查询、插入、删除”的平均、最差时间复杂度图：
这个图来自。
bigocheatsheet，你也可以点开链接直接访问。
学习了这些基础数据结构之后，希望你可以融会贯通，善于组合这些数据结构解决实际的问题，同时还要意识到没有任何一个数据结构是万能的，否则就不会有这么多数据结构需要学习了，只用一个万能的数据结构就行了。
对于数据结构的组合，我举两个例子：
第一个例子是如何以o(1)平均时间复杂度查询一个栈的最大或最小值。此时一个栈是不够的，需要另一个栈b辅助，遇到更大或更小值的时候才入栈b，这样栈b的第一个数就是当前栈内最大或最小的值，查询效率是o(1)，而且只有在出栈时才需要更新，所以平均时间复杂度整体是o(1)。
第二个例子是如何提升链表查找效率，可以通过哈希表与链表结合的思路，通过空间换时间的方式，用哈希表快速定位任意值在链表中的位置，就可以通过空间翻倍的牺牲换来插入、删除、查询时间复杂度均为o(1)。虽然哈希表就能达到这个时间复杂度，但哈希表是无序的；虽然hashtree是有序的，但时间复杂度是o(logn)，所以只有通过组合hashmap与链表才能达到有序且时间复杂度更优，但牺牲了空间复杂度。
包括最后说的布隆过滤器也不是单独使用的，它只是一个防火墙，用极高的效率阻挡一些非法数据，但没有阻挡住的不一定就是合法的，需要进一步查询。
所以希望你能了解到各个数据结构的特征、局限以及组合的用法，相信你可以在实际场景中灵活使用不同的数据结构，以实现当前业务场景的最优解。
数据结构基础与算法
二叉树的树根是f吧，进行中序遍历就是对二叉树按左中右的顺序遍历，树根为f，这里先写为 f 是没有确定的 那么二叉树的左树就是c连着a,d a连着b b是在左边 d连着h,p 前面说的是按左中右的顺序，所以我们要先遍历左树，将整个二叉树的左树分离出来单独看为一棵二叉树，此二叉树的树根就变味c啦 那遍历...
数据结构常用算法数据结构算法
void union list la,list lb union void mergelist list la,list lb,list lc else while i la len while j lb len mergelist status initlist sq sqlist l elemt...
数据结构与算法基础习题
2.b 是数据的基本单位，即数据集合中的个体。有时一个 b 由若干个 组成，在这种情况下，称 b 为记录。c 是数据的最小单位。而由记录所组成的线性表为 d 3.e 是具有相同特性的数据元素的集合，是数据的子集。4.是带有结构特性数据元素的集合。5.被计算机加工的数据元素不是孤立无关的，它们彼此之间...