1 链表

链表通常由一连串结点组成，每一个结点包含任意的实例数据和指向上一个或下一个节点位置的指针

链表是一种线性表，但存储顺序不是线性，而是在每一个结点里存放下一个结点的指针

失去开箱性和有序性，但可存储数据量提升

1.1 分类

单向链表 一个单链表的结点分为两个部分，第一部分保存数据，第二部分保存下个结点的地址，最后一个结点的第二部分为空

单向链表通过指针进行数据访问，每次访问都要从头开始

双向链表 结点分为三部分，分别为前驱指针（pre）、数据、后继指针（next），循环双向链表中第一个结点的 pre 和最后一个结点的 next 互相指向

1.2 栈 队列 链表的区别

栈和队列是线性表，操作受限

区别在于运算规则不同

链表和数组：

​ 1 空间 数组空间连续；链表空间可连续可不连续

​ 2 长度 链表长度可根据数据的放入自动变化；数组长度一旦定义不能改变

​ 3 访问 数组地址连续，可以访问任意位置，遍历效率高； 每次访问需要指针重新开始，遍历效率低

​ 4 操作 数组需要位移；链表需要改变指针的指向

​ 5 使用场景 数据量大，需要频繁访问元素的用数组；需要进行删除、插入等操作的用链表

链表特点：

• ​ 逻辑顺序 一对一
• ​ 存储结构 顺序表 链表
• ​ 运算规则 随机，顺序放置

栈特点

• ​ 逻辑顺序 一对一
• ​ 存储结构 顺序栈 链栈
• ​ 运算规则 先进后出

队列特点

• ​ 逻辑顺序 一对一
• ​ 存储结构 顺序队 链队
• ​ 运算规则 先进先出

2 非线性结构（经典例 树结构）

2.1 二叉树

• 根结点 起源节点
• 父节点 根节点下的有子节点的结点
• 叶结点 没有子节点的结点
• 树的高度 即树的最大层数
• 子树 以父节点开始的树
• 森林 多颗子树构成

每个结点最多只有两个子节点的树称为二叉树

满二叉树结点数为 2^n -1，n为层数

2.2 二叉树的遍历

前序遍历：先输出父节点，再遍历左子树和右子树

中序遍历：先遍历左子树，再输出父节点，最后遍历右子树

后序遍历：先遍历左子树和右子树，再输出父节点

层序遍历：逐层输出

2.3 红黑树

含有红黑结点并且能自平衡的二叉树

性质

• 1 结点只有黑红两色
• 2 根节点是黑色
• 3 叶结点（NIL）是黑色（java中NIL为null）
• 4 每个红色结点的两个子节点一定是黑色
• 5 任意一个结点到NIL的路径都包含数量相同的黑结点

3 集合

集合类似于容器，可以动态的把多个对象的引用放入集合中，可以存储数量不等的多个对象，还可以保存具有映射关系的数据

数组的存储特点

1. ​ 初始化时长度确定
2. ​ 声明时类型确定
3. ​ 存储有序，可重复

数组的存储弊端

1. 长度不可变，不利于扩展
2. 提供的方法和属性较少，不便于对元素进行添加、删除、插入等操作，且效率不高，同时无法直接获取存储元素的个数

3.1 集合的体系结构

集合特点：存储空间可变的存储模型，存储数据的容量可随时发生改变

集合分为 Collection （单列）和 Map（双列）两大类

Collection 作为集合层次的根接口只能存储对象，而其他集合不允许。有的集合有序，有的集合无序。JDK对Collection不提供直接实现，而是提供了更具体的子接口的实现，如 Set（不可重复）和 List（可重复）。Collection 多用于传递集合，在 Collection 下创建对象通用性最大（多态性）

Set的经典实现：HashSet TreeSet LinkedHashSet

List的经典实现：ArrayList（最通用） LinkedList

Map的经典实现：HashMap TreeMap

Collection接口：

public interface Collection<E>  extends Iterable<E>

3.2 Collection接口的使用

创建对象时只能创建实现类的对象

Collection，单列集合的顶层接口，表示一组对象（元素）

通过子接口的实现创建对象

3.2.1 ArrayList方法：

3.2.2 Iterator

迭代集合的迭代器

hasNext 通过比较当前指针位置（cursor）与集合长度（size）是否相等，当两者相等时，cursor 指向集合外

3.3 List

3.3.1 List的特点

1. 是有序集合，可以精确控制列表中每个元素的插入位置，可通过整数索引搜索并访问元素
2. 通常允许元素重复
3. 可以存储null，并且可以存储多个

经典实现：ArrayList LinkedList Vector

3.3.2 List接口特有方法

List 集合的有序性体现在元素的存入顺序和迭代顺序是一致的

迭代器的使用：for循环更利于空间释放（只作用在方法内，方法结束就释放），但开发中普遍使用while

3.3.4 并发修改异常 （ConcurrentModificationException）

迭代器在迭代过程中，通过集合修改了集合的元素（多为添加或删除），造成迭代器获取园中判断预期修改值和实际修改值不一致

解决方案：集合自身进行遍历，在遍历过程中修改

3.3.5 ListIteator（列表迭代）

在进行元素添加（或修改）时，加入（或修改）元素或后需要返回列表中的上一个元素，即返回到添加（或修改）的元素，否则添加（或修改）的元素不能在迭代过程中输出

在用 hasPrevious 逆序遍历列表前需要先正向遍历一次列表