程序员应知应会之数据结构简述

对于大部分程序员而言，数据结构是最基础的知识了。所谓数据结构，其实本质上就是数据不同的组织方式。同样的一堆数据，组织方式不同，效果也就有了很大差异。

不仅数据如此，在所有的社会组织中，组织结构都是非常重要的一个部分。同样的一些事物，通过不同的组织方式组织起来，就有了完全不同的作用和能力。

就比如同样的一个人晃着手电筒，大部分时间都没有什么意义。但是一旦这个晃的节奏与摩尔斯电码联系起来，那么就拥有了传递信息的能力。

在国共战争时，很多人会发现一个很有意思的特点。共军的战术很灵活，通常是几个人的小分队绕后都能打出很惊艳的战果。中印边境战时庞国兴战斗小组的事例就很好的说明了这一点，与大部队失散的几名士兵，能够自发的组织起来获取极大的战功。这在很多军队里是完全不可能的事情。像国军就打不出来这样的仗。为什么呢？很多军事史专家做过研究，他们发现大部分国军士兵不能脱离指挥官的指挥体系单独作战。一旦脱离了，可能就直接当了逃兵了。所以很多时候，国军不得不老老实实的打阵地战。

这就是组织度的重要性。

而数据结构，则是数据的组织度的一种体现。在合适的场合中，应用有效的数据结构，会使得很多问题变得非常简单。

例如说对于知识图谱数据的存储，如果用图数据库代替结构化数据库的话，效率可以提高数十倍。类似的，B+树能够更加充分的利用节点空间，使得查询数据的效率更加稳定，速度完全趋近于二分查找。

这种事例还有很多，所以对于一名合格的程序员而言，熟练地掌握各种数据结构的优缺点，在不同的应用场景中，快速选择出正确的基础数据结构，是非常重要的基础素质之一。

常见的一些数据结构特点如下。

一、顺序表

优点：访问元素效率高O(1)。

缺点：扩展开销大，插入和删除开销大O(n)。

使用场景：需要大量访问元素而少量增加和删除的程序。

二、链表

优点：插入和删除节点十分高效O(1)，不需要扩容。

缺点：查找元素开销大O(n).

使用场景：适用于需要进行大量增加和删除元素操作而对访问元素无要求的程序。

三、二叉排序树

特点：左小右大，查找效率O(logn)，极端情况下为O(n)。

插入：递归实现，新插入的节点一定是叶子节点。

删除：叶子节点：直接删除。删除节点只有左子树或右子树：用左子树或右子树代替自己。删除节点左子树右子树都有：与中序遍历的直接后继交换位置，并删除自己。

四、平衡二叉树

特点：左小右大，无重复值。为了解决二叉排序树退化成链表而诞生。

优点：平衡二叉树查询效率与高度成反比，h越小，查询越快O(logn)。

缺点：插入删除会破坏平衡，需要不定次左旋右旋恢复平衡，频繁的插入删除会影响效率。

五、红黑树

特点：根节点始终为黑色，没有相邻的红色节点，根节点到任意后代为NULL的节点的路径中，黑色节点数相同，每个叶子节点都为黑色。

优点：红黑树放弃了追求完全平衡，追求大致的平衡，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更简单O(logn)。

缺点：查找比AVL树慢(高度高），但删除效率大大提高。

六、B树

特点：树的节点关键字增多后层级比原来少了，减少数据查找的次数和复杂度。

应用：数据库索引技术，文件系统。

七、哈夫曼树

特点：权重越大的节点离根节点越近。

应用：最小代价问题的决策。哈夫曼编码，数据压缩，加密解密，文件传输。

八、堆

特点：堆是一颗完全二叉树，也成为二叉堆。堆中任意节点总是不大于／不小于其子节点的值。由于堆是完全二叉树，因此根据二叉树的性质，完全二叉树能够完美的映射到数组结构中去。

应用：堆常被用于实现优先队列，优先队列可以自由添加数据，但取出数据时要从最小值开始按顺序取出。堆还用于实现堆排序。

九、栈

特点：后进先出

应用：数的任意进制转换，括号匹配检验，表达式求值，二叉树遍历等。

十、队列

特点：先进先出

应用：利用其先进先出的特性，解决具体业务场景如消息通知，订单处理，异步处理等。

十一、哈希表

定义：底层是一个数组结构，数组中每一项对应一个链表

应用：适合查找性能要求高，数据元素之间无逻辑关系的情况。

喜欢本文的话，欢迎关注活在信息时代哦：）