Java中常见的数据结构 - 左手拿经，右手持剑
Java中常见的数据结构
数据存储的常用结构有：栈、队列、数组、链表和红黑树；
栈
stack,又称堆栈， 栈（stack）是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为先进后出的线性表 。
存取特点：
1、先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。例如，子弹压进弹夹，先压进去的子弹在下面，后压进去的子弹在上面，当开枪时，先弹出上面的子弹，然后才能弹出下面的子弹。
2、栈的入口、出口的都是栈的顶端位置。
如图：
3、压栈：存元素
4、弹栈：取元素
队列
queue,简称队， 队列是一种特殊的线性表，是运算受到限制的一种线性表，只允许在表的一端进行插入，而在另一端进行删除元素的线性表。队尾(rear)是允许插入的一端。队头(front)是允许删除的一端。空队列是不含元素的空表。
存取特点：
1、先进先出（即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山洞，车头先进去，车尾后进去；车头先出来，车尾后出来。
2、队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口。
如图：
数组
Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。
存取特点：
1、查找元素快：通过索引，可以快速访问指定位置的元素
2、增删元素慢
指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。
指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。
如下图：
链表
linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表常用的有 3 类： 单链表、双向链表、循环链表。
链表的核心操作集有 3 种：插入、删除、查找(遍历）
单链表
单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构(链尾除外），内存结构由数据域和 Next 指针域组成。
Data 数据 + Next 指针，组成一个单链表的内存结构 ；
第一个内存结构称为 链头，最后一个内存结构称为 链尾；
链尾的 Next 指针设置为 NULL [指向空]；
单链表的遍历方向单一（只能从链头一直遍历到链尾）
单链表操作集：
双向链表
双向链表 [Double Linked List]：由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构(链头没有前驱，链尾没有后继），内存结构由数据域、Prev 指针域和 Next 指针域组成。
Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构；
第一个内存结构称为 链头，最后一个内存结构称为 链尾；
链头的 Prev 指针设置为 NULL， 链尾的 Next 指针设置为 NULL；
Prev 指向的内存结构称为 前驱， Next 指向的内存结构称为 后继；
双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向；
双向链表操作集：
循环链表
单向循环链表 [Circular Linked List] : 由各个内存结构通过一个指针 Next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成。
双向循环链表 [Double Circular Linked List] : 由各个内存结构通过指针 Next 和指针Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、Prev 指针域和 Next 指针域组成。
循环链表分为单向、双向两种；
单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；
双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev指针指向链尾，形成一个闭环；
循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；
循环链表操作集：
二叉树
binary tree ,是每个结点不超过2的有序树（tree） 。就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。
二叉树：
二叉树的种类
1、斜树：所有结点都只有左子树，或者右子树。
2、满二叉树：所有的分支节点都具有左右节点。
3、完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h层所有的结点都连续集中在最左边，这就是完全二叉树。
二叉树的一些性质
二叉树第 i 层上的结点数目最多为 2^(i-1) (i≥1)
深度为 h 的二叉树至多有 2^h-1 个结点(h≥1)
包含 n 个结点的二叉树的高度至少为 log2 (n+1)
在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1
二叉树的遍历方式
二叉树的遍历方式，一般分为先序遍历，中序遍历，后序遍历。
先序遍历
先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
中序遍历
先访问左节点，然后访问根节点，最后访问右节点(左->根->右)
后序遍历
先访问左节点，然后访问右节点，最后访问根节点(左->右->根)
先序遍历(根-左-右):1-2-4-8-9-5-10-3-6-7
中序遍历:(左-根-右):8-4-9-2-10-5-1-6-3-7
后序遍历(左-右-根):8-9-4-10-5-2-6-7-3-1
二叉树的一种比较有意思的叫做红黑树
红黑树：红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。
红黑树的约束:
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
红黑树的特点:
速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍
posted on
2021-03-16 22:54
左手拿经，右手持剑
阅读(47)
评论(0)
编辑
收藏
举报
以上是 Java中常见的数据结构 - 左手拿经，右手持剑 的全部内容， 来源链接： utcz.com/z/395004.html
