内容目录
java
数据结构概述
数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
常见的数据结构
栈；队列；数组；链表；二叉树；二叉查找树；平衡二叉树；红黑树......
线性表
线性表概述
前驱元素： 若 A 元素在 B 元素的前面，则称 A 为 B 的前驱元素
后继元素： 若 B 元素在 A 元素的后面，则称 B 为 A 的后继元素
线性表特征
线性表的特征：数据元素之间具有一种"一对一"的逻辑关系。
- 第一个数据元素没有前驱，这个数据元素被称为头结点；
- 最后一个数据元素没有后继，这个数据元素被称为尾结点；
- 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
如果把线性表用数学语言来定义，则可以表示为(a1,...ai-1,ai,ai+1,...an)，ai-1 领先于 ai,ai 领先于 ai+1，称 ai-1 是 ai 的前驱元素，ai+1 是 ai 的后继元素
线性表的分类
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
顺序表
顺序表的遍历
一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。
在 java 中，遍历集合的方式一般都是用的是 foreach 循环，如果想让我们的 SequenceList 也能支持 foreach 循环，则需要做如下操作：
- 让 SequenceList 实现 Iterable 接口，重写 iterator 方法；
- 在 SequenceList 内部提供一个内部类 SIterator,实现 Iterator 接口，重写 hasNext 方法和 next 方法；
顺序表的容量可变（扩容）
链表
链表的特点：
- 链表中的元素是在内存中不连续存储的，每个元素节点包含数据值和下一个元素的地址。
- 链表中的元素是游离存储的，每个元素节点包含数据值和下一个元素的地址。
- 链表查询慢，无论查询哪个数据都要从头开始找。
- 链表增删相对快
链表的分类：单向链表和双向链表
单向链表
双向链表
栈
我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。
栈数据结构的执行特点是：
- 后进先出，先进后出
数据进入栈模型的过程称为：压/进栈
数据离开栈模型的过程称为：弹/出栈
队列
数据从后端进入队列模型的过程称为：入队列
数据从前端离开队列模型的过程称为：出队列
数组
- 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。（元素在内存中是连续存储的）；
- 删除效率低：要将原始数据删除，同时后面每个数据前移。
- 添加效率极低：添加位置后的每个数据后移，再添加元素。
二叉树
红黑树
红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。1972 年出现，当时被称之为平衡二叉 B 树。1978 年被修改为如今的"红黑树"。
每一个节点可以是红或者黑；红黑树不是通过高度平衡的，它的平衡是通过"红黑规则"进行实现的。
红黑规则
- 每一个节点或是红色的，或者是黑色的，根节点必须是黑色。
- 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
添加节点
添加的节点的颜色，可以是红色的，也可以是黑色的。但默认使用红色，效率高。
红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的
规则如下：
- 每一个节点或是红色的，或者是黑色的，根节点必须是黑色
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的；
- 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
红黑树增删改查的性能都很好
各种数据结构的特点和作用是什么样的
- 队列：先进先出，后进后出。
- 栈：后进先出，先进后出。
- 数组：内存连续区域，查询快，增删慢。
- 链表：元素是游离的，查询慢，首尾操作极快。
- 二叉树：永远只有一个根节点, 每个结点不超过2个子节点的树。
- 查找二叉树：小的左边，大的右边，但是可能树很高，查询性能变差。
- 平衡查找二叉树：让树的高度差不大于1，增删改查都提高了。
- 红黑树（就是基于红黑规则实现了自平衡的排序二叉树）