1.概述
- 存储数据的空间排列
- 查询数据的操作方式
- 核心：有效占用空间、查询数据时间
2.数组
特性
- 内存中连续存储多个数据
- 内存空间分配是连续的
存储
- 数组长度
- 索引
CRUD操作
- 查询：根据数组的首地址，使用索引×单个数据的长度即可得到指定索引的地址
- 修改：在查询到指定索引的地址即可覆盖重写数据
- 增加：一旦声明便固定，不可变
- 删除：需要移位数据，达到内存空间连续
利弊
- 利：查询、修改
- 弊：新增、删除
3.栈
特性
- 线性表的实现（一块连续的内存空间）
- 栈顶允许操作，栈底不允许操作
- 先进后出，后进先出（手枪弹夹）
存储
- 栈顶指针
- 栈底指针
操作
- 快速的加载和读取（删除）数据
- 数据操作只有一个出入口（栈顶）
利弊
- 利
- 内部数据一直都是连续的，没有内存碎片，用于方法中局部变量的存储
- 利
4.队列-Queue
特性
- 线性表的实现
- 先进先出，后进后出（火车进入隧道）
存储
- 队首-前置计数器（front/head）
- 队尾-后置计数器（tail/rear）
操作
- 读取（删除）后，数据内存地址前移
- 新增，从队尾操作
利弊
- 弊：新增、删除后耗费时间
改进
- 双向队列，队首队尾相接，解决弊端
5.链表
特性
- 非连续、非顺序的存储结构
- 数据逻辑顺序由指针指向
类别-根据指针的功能
- 单向链表
- 双向链表
- 循环链表
存储
- 头指针-head
- 下一个数据的指针-next
利弊
- 新增、删除快
- 查询慢
6.二叉树
特性
- 每个根节点至多有两节点
- 左节点小于中间节点
- 右节点大于中间节点
存储
- 根节点
操作
- 查询数据从根节点开始
利弊
- 利：查询速度快
- 弊：极端情况，形成单向树结构（链表），影响查询性能
改进
- 平衡二叉树
- 一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
- 满二叉树
- 如果二叉树中除了叶子结点，每个结点的度都为 2
- 完全二叉树
- 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布（有右节点必有左节点）
- 红黑树
- 是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
- 参考
- 平衡二叉树
7.散列表
特性
- 即哈希表
- 根据关键码和值（key和value）直接进行访问的数据结构
存储
- 底层实现仍旧是数组，单个数组的对象是Entry
- 数组加链表
8.图
- 特性
- 顶点和边的组合
- 链表和树，是最简单的图
- 可以解决更加复杂的交互关系
9.线性表
- 含义：
- n个元素的有限序列
- 包含数组和链表