图解！24张图彻底弄懂九⼤常见数据结构！
数据结构想必⼤家都不会陌⽣，对于⼀个成熟的程序员⽽⾔，熟悉和掌握数据结构和算法也是基本功之⼀。数据结构本⾝其实不过是数据按照特点关系进⾏存储或者组织的集合，特殊的结构在不同的应⽤场景中往往会带来不⼀样的处理效率。
常⽤的数据结构可根据数据访问的特点分为线性结构和⾮线性结构。线性结构包括常见的链表、栈、队列等，⾮线性结构包括树、图等。数据结构种类繁多，本⽂将通过图解的⽅式对常⽤的数据结构进⾏理论上的介绍和讲解，以⽅便⼤家掌握常⽤数据结构的基本知识。
本⽂提纲：
1  数组
数组可以说是最基本最常见的数据结构。数组⼀般⽤来存储相同类型的数据，可通过数组名和下标进⾏数据的访问和更新。数组中元素的存储是按照先后顺序进⾏的，同时在内存中也是按照这个顺序进⾏连续存放。数组相邻元素之间的内存地址的间隔⼀般就是数组数据类型的⼤⼩。
2  链表
链表相较于数组，除了数据域，还增加了指针域⽤于构建链式的存储数据。链表中每⼀个节点都包含此节点的数据和指向下⼀节点地址的指针。由于是通过指针进⾏下⼀个数据元素的查和访问，使得
链表的⾃由度更⾼。
这表现在对节点进⾏增加和删除时，只需要对上⼀节点的指针地址进⾏修改，⽽⽆需变动其它的节点。不过事物皆有两极，指针带来⾼⾃由度的同时，⾃然会牺牲数据查的效率和多余空间的使⽤。
⼀般常见的是有头有尾的单链表，对指针域进⾏反向链接，还可以形成双向链表或者循环链表。
链表和数组对⽐
redis五种数据结构链表和数组在实际的使⽤过程中需要根据⾃⾝的优劣势进⾏选择。链表和数组的异同点也是⾯试中⾼频的考察点之⼀。这⾥对单链表和数组的区别进⾏了对⽐和总结。
3  跳表
从上⾯的对⽐中可以看出，链表虽然通过增加指针域提升了⾃由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产⽣就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的⽅式可以让查询的时间复杂度从O(n)提升⾄O(logn)。
跳表通过增加的多级索引能够实现⾼效的动态插⼊和删除，其效率和红⿊树和平衡⼆叉树不相上下。⽬前redis和levelDB都有⽤到跳表。
从上图可以看出，索引级的指针域除了指向下⼀个索引位置的指针，还有⼀个down指针指向低⼀级的链表位置，这样才能实现跳跃查询的⽬的。
4  栈
栈是⼀种⽐较简单的数据结构，常⽤⼀句话描述其特性，后进先出。栈本⾝是⼀个线性表，但是在这个表中只有⼀个⼝⼦允许数据的进出。这种模式可以参考腔肠动物...即进⾷和排泄都⽤⼀个⼝...
栈的常⽤操作包括⼊栈push和出栈pop，对应于数据的压⼊和压出。还有访问栈顶数据、判断栈是否为空和判断栈的⼤⼩等。由于栈后进先出的特性，常可以作为数据操作的临时容器，对数据的顺序进⾏调控，与其它数据结构相结合可获得许多灵活的处理。
5  队列
队列是栈的兄弟结构，与栈的后进先出相对应，队列是⼀种先进先出的数据结构。顾名思义，队列的数据存储是如同排队⼀般，先存⼊的数据先被压出。常与栈⼀同配合，可发挥最⼤的实⼒。
6  树
树作为⼀种树状的数据结构，其数据节点之间的关系也如⼤树⼀样，将有限个节点根据不同层次关系进⾏排列，从⽽形成数据与数据之间的⽗⼦关系。常见的数的表⽰形式更接近“倒挂的树”，因为它将根朝上，叶朝下。
树的数据存储在结点中，每个结点有零个或者多个⼦结点。没有⽗结点的结点在最顶端，成为根节点；没有⾮根结点有且只有⼀个⽗节点；每个⾮根节点⼜可以分为多个不相交的⼦树。
这意味着树是具备层次关系的，⽗⼦关系清晰，家庭⾎缘关系明朗；这也是树与图之间最主要的区别。
别看树好像很⾼级，其实可看作是链表的⾼配版。树的实现就是对链表的指针域进⾏了扩充，增加了多个地址指向⼦结点。同时将“链表”竖起来，从⽽凸显了结点之间的层次关系，更便于分析和理解。
树可以衍⽣出许多的结构，若将指针域设置为双指针，那么即可形成最常见的⼆叉树，即每个结点最多有两个⼦树的树结构。⼆叉树根据结点的排列和数量还可进⼀度划分为完全⼆叉树、满⼆叉树、平衡⼆叉树、红⿊树等。
完全⼆叉树：除了最后⼀层结点，其它层的结点数都达到了最⼤值；同时最后⼀层的结点都是按照从左到右依次排布。
满⼆叉树：除了最后⼀层，其它层的结点都有两个⼦结点。
平衡⼆叉树
平衡⼆叉树⼜被称为AVL树，它是⼀棵⼆叉排序树，且具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。
⼆叉排序树：是⼀棵空树，或者：若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；它的左、右⼦树也分别为⼆叉排序树。
树的⾼度：结点层次的最⼤值
平衡因⼦：左⼦树⾼度 - 右⼦树⾼度
⼆叉排序树意味着⼆叉树中的数据是排好序的，顺序为左结点<；根节点<；右结点，这表明⼆叉排序树的中序遍历结果是有序的。（还不懂⼆叉树四种遍历⽅式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习！）
平衡⼆叉树的产⽣是为了解决⼆叉排序树在插⼊时发⽣线性排列的现象。由于⼆叉排序树本⾝为有序，当插⼊⼀个有序程度⼗分⾼的序列时，⽣成的⼆叉排序树会持续在某个⽅向的字数上插⼊数据，导致最终的⼆叉排序树会退化为链表，从⽽使得⼆叉树的查询和插⼊效率恶化。
平衡⼆叉树的出现能够解决上述问题，但是在构造平衡⼆叉树时，却需要采⽤不同的调整⽅式，使得⼆叉树在插⼊数据后保持平衡。主要的四种调整⽅式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。这⾥先给⼤家介绍下简单的单旋转操作，左旋和右旋。LR和RL本质上只是LL和RR的组合。
在插⼊⼀个结点后应该沿搜索路径将路径上的结点平衡因⼦进⾏修改，当平衡因⼦⼤于1时，就需要进⾏平衡化处理。从发⽣不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在⼀条直线上，则采⽤单旋转进⾏平衡化，如果这三个结点位于⼀条折线上，则采⽤双旋转进⾏平衡化。
左旋：S为当前需要左旋的结点，E为当前结点的⽗节点。
左旋的操作可以⽤⼀句话简单表⽰：将当前结点S的左孩⼦旋转为当前结点⽗结点E的右孩⼦，同时将⽗结点E旋转为当前结点S的左孩⼦。可⽤动画表⽰：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。