就是一种程序设计优化的方法，研究数据的逻辑结构和物理结构，以及他们相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度，减少内存占用空间

数据之间的逻辑关系

集合结构

结构中的元素之间除了同属一个集合的相互关系，别无其他关系。集合元素之间没有逻辑关系

线性结构

数据结构中的元素存在一对一的相互关系。结构中必须存在唯一的首元素和唯一的尾元素。体现为：一维数组、链表、栈、队列

树形结构

数据结构中的元素存在一对多的相互关系。比如：家谱、文件系统、组织架构

图形结构

数据结构中的元素存在多对多的相互关系。比如：全国铁路网、地铁图

数据的存储结构（物理结构）

顺序结构
链式结构
索引结构
散列结构

开发中理解以上存储结构

线性表（一对一关系）：一维数组、单向链表、双向链表、栈、队列
树（一对多关系）：各种树（二叉树、B+树）
图（多对多关系）
哈希表：HashMap、HashSet

运算结构

分配资源，建立结构，释放资源
插入和删除
获取和遍历
修改和排序

java常见存储结构

数组

可以理解为真实的数据结构，内存中真实存在的一个结构

链表

可以理解为真实的数据结构，内存中真实存在的一个结构
链表中的基本单位是：节点（Node）

单向链表

他的Node结构中包含两个属性，一个数据和一个下一条数据的指针
新增一条数据后需要将他的指针赋值给上一条数据的指针属性
删除时需要将上一条数据的指针重新赋值，赋值为删除数据的下一条数据的指针

双向链表

他的Node结构中包含三个属性，一个数据和一个下一条数据的指针和一个上一条数据的指针
新增一条数据后需要将他的指针赋值给上一条数据的下一条数据指针属性，并指定本条数据的上一条数据指针为上一条数据
删除时需要将上一条数据的指针重新赋值，赋值为删除数据的下一条数据的指针；且需要将删除数据的下一条数据的上一条数据指针属性重新赋值，赋值为删除数据的上一条数据的指针

二叉树

基于链表衍生出来的
他的结构中包含三个属性，一个数据和一个左边一条数据的指针和一个右边一条的指针
在左边新增一条数据后需要将他的指针赋值给前一条数据的左边一条数据指针属性
在右边新增一条数据后需要将他的指针赋值给前一条数据的右边一条数据指针属性

前序遍历（中左右）（根左右）

即先访问根节点，在前序遍历左子树，最后在前序遍历右子树。前序遍历运算访问二叉树各节点是以根、左、右的顺序进行访问的

中序遍历（左中右）（左根右）

即先中前序遍历左子树，然后在访问根节点，最后在中序遍历右子树。中序遍历运算访问二叉树各节点是以左、根、右的顺序进行访问的

后序遍历（左右中）（左右根）

即先后序遍历左子树，然后在后序遍历右子树，最后在访问根节点。后序遍历运算访问二叉树各节点是以左、右、根的顺序进行访问的

经典二叉树

二叉排序树(二叉查找树)（BST）

平衡二叉树（AVL）

BST的一种，左右两个子树的的高度差的绝对值不能超过1

红黑树

BST的一种
特点
	每个节点是红色或黑黑色
	根节点是黑色
	每个叶子节点是黑色（为空或NULL的叶子节点）
	每个红色节点的两个字节点都是黑色的（从每个叶子到根的所有路径不能有两个连续的红色节点）
	从任一结点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其它路径长出两倍）

栈（stack，先进后出）

属于抽象数据类型（ADT）
可以使用时数据或链表来构建

以数组示例

class Stack {
	Object[] values;
	int size; // 记录存储元素的个数
	public Stack(int length) {
		values = new Object[length];
	}
	// 入栈
	public void push(Object ele) {
		if (size > values.length) {
			throw new RuntimeException("栈空间已满");
		}
		values[size] = ele;
		size++;
	}
	// 出栈
	public Obejct pop() {
		if (size <= 0) {
			throw new RuntimeException("栈空间已空");
		}
		Object value = values[size - 1];
		values[size - 1] = null;
		size--;
		return value;
	}
}

队列（queue，先进先出）

属于抽象数据类型（ADT）

以数组示例

public class Queue{
	Object[] values;
	int size; // 记录存储元素的个数
	public Queue(int length) {
		values = new Object[length];
	}
	// 入队列
	public void add(Object ele) {
		if (size > values.length) {
			throw new RuntimeException("队列空间已满");
		}
		values[size] = ele;
		size++;
	}
	// 出队列
	public Obejct get() {
		if (size <= 0) {
			throw new RuntimeException("队列空间已空");
		}
		Object value = values[0];
		for (int i = 0; i < size - 1; i++) {
			values[i] = values[i + 1];
		}
		values[size - 1] = null;
		size--;
		return value;
	}
}