1. 数据结构概述
Java的集合框架其实就是对数据结构的封装，在学习集合框架之前，有必要先了解下数据结构。
1.1. 什么是数据结构（了解）
所谓数据结构，其实就是计算机存储、组织数据的方式。
数据结构是用来模拟数据存储操作的，其实就是对数据做增删改查操作。
增：把某个数据存储到某个容器中
删：从容器中把某个数据删除掉
改：把容器中某个数据替换成另一个数据
查：把容器中的数据查询出来
不同的数据结构，底层采用不同的存储方式（算法），在具体操作的时候效率是不一样的，比如有的查询速度很快，有的插入速度很快，有的操作头和尾速度很快等。
常见的数据结构：
数组（Array） 掌握
链表（Linked List） 了解
哈希表（Hash） 了解
栈（Stack） 了解
队列（Queue） 了解
树（Tree） 了解
图（Graph）
堆（Heap）
1.2. 数组结构
1.2.1. 模拟ArrayList（掌握）
假设我现在是某个篮球队的教练，需要安排5个球员上场打球。此时需要模拟上场球员的存储，简单一点，我们就只存储上场球员的球衣号码。那么此时我需要以下几个操作：
1．初始一个容量为5的容器，用来存储场上的5个球衣号码。
2．安排5个球员上场，比如球员号码分别为11、22、33、44、55。
3．查询指定索引位置球员的球衣号码是多少，如查询索引位置为2的球衣号码是33。
4．替换场上索引位置为2的球员，使用333号替换33号。
5．罚下场上索引位置为2的球员（直接罚下，没有补位）。
6．打印出场上球员的球衣号码，打印风格如 [11，22，33，44，55]。
操作前后效果图：
1.2.2. 初始化操作（掌握）
使用Integer数组来存储场上球员号码，提供了两个构造器，一个用于自定义初始化容量，一个用于使用默认的初始化容量10。
public class PlayerList {
//存储场上球员号码
private Integer[] players = null;
//存储场上球员数量
private int size = 0;
//自定义初始容量
public PlayerList(int initialCapacity) {
if (initialCapacity < 0) {
throw new RuntimeException("初始容量不能为负数");
}
this.players = new Integer[initialCapacity];
}
//默认初始容量为10
public PlayerList() {
this(10);
}
}
测试代码：
public class App {
public static void main(String[] args) {
//初始容量为默认的10
PlayerList list1 = new PlayerList();
//自定义初始化容量为5
PlayerList list2 = new PlayerList(5);
//自定义初始化容量为20
PlayerList list3 = new PlayerList(20);
}
}
1.2.3. 打印操作（掌握）
public String toString() {
if (players == null) {//如果没有初始化容器
return "null";
}
if (size == 0) {//如果容器中球员数量为0
return "[]";
}
StringBuilder sb = new StringBuilder(40);
sb.append("[");
for (int index = 0; index < size; index++) {
sb.append(players[index]);
//如果不是最后一个
if (index != size - 1) {
sb.append(",");
} else {//如果是最后一个
sb.append("]");
}
}
return sb.toString();
}
1.2.4. 保存操作（掌握）
//向场上添加一个球员号码
public void add(Integer playerNumber) {
this.players[size] = playerNumber;//保存球衣号码
size++;//场上球员数量加1
}
测试代码
public class App {
public static void main(String[] args) {
//初始化容器,设置初始化容量为5
PlayerList list = new PlayerList(5);
System.out.println(list);
//向容器中添加5个元素（球员号码）
list.add(11);
list.add(22);
list.add(33);
list.add(44);
list.add(55);
//打印容器中每一个元素
System.out.println(list);
}
}
输出结果：
[]
[11,22,33,44,55]
因为数组的长度是固定的，此时的players数组只能存储5个元素，如果再多存储一个就报错：数组索引越界。此时就要考虑在保存操作时对数组做扩容操作，扩容的原理是：
创建一个原数组长度两倍长的新数组
把旧数组中的所有元素拷贝到新数组中
把新数组的引用赋给旧数组变量
保存操作时扩容操作：
//向场上添加一个球员号码
public void add(Integer playerNumber) {
//如果容器容量已满,此时需要扩容，此时扩容机制为原来容量的2倍
if (size == players.length) {
this.players = Arrays.copyOf(players, size * 2);
}
//-----------------------------------------
this.players[size] = playerNumber;//保存球衣号码
size++;//场上球员数量加1
}
1.2.5. 查询操作（掌握）
需求：查询指定索引位置球员的球衣号码是多少，如查询索引位置为2的球衣号码是33。
其实就是返回数组中，指定索引对应的元素值。
public Integer get(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
return players[index];
}
测试代码：
Integer playerNum = list.get(2);
System.out.println(playerNum);
输出结果：
33
1.2.6. 修改操作（掌握）
需求：替换场上索引位置为2的球员，使用333号替换33号。
//替换指定位置的球员号码
public void set(int index, Integer newPlayerNumber) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
players[index] = newPlayerNumber;
}
1.2.7. 删除操作（掌握）
需求：罚下场上索引位置为2的球员（直接罚下，没有补位）。
删除操作的原理，把后续的元素整体往前挪动一个位置。
//删除指定位置的球员号码
public void remove(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
for (int i = index; i < size - 1; i++) {
players[i] = players[i + 1];
}
players[size - 1] = null;
size--;
}
1.2.8. 让容器支持存储任意数据类型的元素（掌握）
此时元素类型是Integer类型，也就是只能存储整型的数据，但是却不能存储其他类型的数据，此时我们可以考虑吧元素类型改成Object，那么Object数组可以存储任意类型的数据。
public class MyArrayList {
//存储元素
private Object[] elementData = null;
//存储元素数量
private int size = 0;
//自定义初始容量
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new RuntimeException("初始容量不能为负数");
}
this.elementData = new Object[initialCapacity];
}
//默认初始容量为10
public MyArrayList() {
this(10);
}
//向容器中添加一个元素
public void add(Object playerNumber) {
//如果容器容量已满,此时需要扩容，此时扩容机制为原来容量的2倍
if (size == elementData.length) {
this.elementData = Arrays.copyOf(elementData, size * 2);
}
//-----------------------------------------
this.elementData[size] = playerNumber;//保存球衣号码
size++;//容器中元素数量加1
}
//查询指定位置的元素
public Object get(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
return elementData[index];
}
//替换指定索引位置的元素
public void set(int index, Object newPlayerNumber) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
elementData[index] = newPlayerNumber;
}
//删除指定索引位置的元素
public void remove(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界");
}
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
elementData[size - 1] = null;
size--;
}
public String toString() {
if (elementData == null) {//如果没有初始化容器
return "null";
}
if (size == 0) {//如果容器中元素数量为0
return "[]";
}
StringBuilder sb = new StringBuilder(40);
sb.append("[");
for (int index = 0; index < size; index++) {
sb.append(elementData[index]);
//如果不是最后一个
if (index != size - 1) {
sb.append(",");
} else {//如果是最后一个
sb.append("]");
}
}
return sb.toString();
}
}
1.2.9. 数组的性能分析（了解）
在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，常用大O符号来表述。
时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
我们在这里针对ArrayList存储数据的增删改查（CRUD）做性能分析：
- 保存操作：
如果保存在数组的最后一个位置，至少需要操作一次。
如果保存在数组的第一个位置，如果存在N个元素，此时需要操作N次(后面的元素要整体后移)。
平均: (N+1) /2 次。 N表示数组中元素的个数。 如果要扩容，更慢，性能更低。
- 删除操作:
如果删除最后一个元素，操作一次。
如果删除第一个元素，操作N次。
平均：(N+1)/2次.
修改操作: 操作1次.
查询操作：根据索引查询元素: 操作1次.
结论：基于数组的数据结构做查询是和修改是非常快的，做保存和删除操作比较慢了。
那如果想保证保存和删除操作的性能，此时就得提提链表这种数据结构了。
1.3. 其他数据结构（了解）
1.3.1. 链表（了解）
链表结构（火车和火车车厢）：
1)：单向链表，只能从头遍历到尾/只能从尾遍历到头。
2)：双向链表，既可以从头遍历到尾,又可以从尾遍历到头。
通过引用来表示上一个节点和下一个节点的关系。
单向链表：
双向链表：
对LinekdList操作的性能分析：
双向链表可以直接获取自己的第一个和最后一个节点。
- 保存操作
如果新增的元素在第一个或最后一个位置，那么操作只有1次。
- 删除操作
如果删除第一个元素 ：操作一次
如果删除最后一个元素：操作一次
如果删除中间的元素：
找到元素节点平均操作：(1+N)/2次
找到节点之后做删除操作: 1次
- 修改操作
平均：(N+1)/2次
- 查询操作:
平均:(N+1)/2次
结论：
ArrayList： 查询、更改较快，新增和删除较慢。
LinkedList： 查询、更改较慢，新增和删除较快。
一般的，在开发中数据都是存储在数据库中，我们一般主要用来查询，所以ArrayList使用较多。
1.3.2. 队列（了解）
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
单向队列(Queue)：先进先出(FIFO)，只能从队列尾插入数据，只能从队列头删除数据。
双向队列(Deque)：可以从队列尾/头插入数据，只能从队列头/尾删除数据。
结论：最擅长操作头和尾。
1.3.3. 栈（了解）
栈（stack）又名堆栈，它是一种运算受限的线性表，后进先出(LIFO)，和手枪弹夹类似。
栈结构仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈中插入新元素又称作入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一个栈中删除元素又称作出栈，表示把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素（LIFO）。
1.3.4. 哈希表（了解）
一般的，数组中元素在数组中的索引位置是随机的，元素的取值和元素的位置之间不存在确定的对应关系。因此，在数组中查找特定的值时，需要把查找值和一系列的元素进行比较。
此时的查询效率依赖于查找过程中所进行的比较次数，如果比较次数较多，查询效率还是不高。
如果元素的值（value）和在数组中的索引位置（index）有一个确定的对应关系，我们把这种关系称之为哈希（hash）。则元素值和索引对应的公式为: index = hash(value)。也就是说，通过给定元素值，只要调用hash(value)方法，就能找到数组中取值为value的元素的位置。
比如，图中的hash算法公式为：index = value / 10 - 1。
在往哈希表中存储对象时，该hash算法就是对象的hashCode方法。
注：这里仅仅是假设算法公式是这样的，真实的算法公式我们可以不关心。
1.3.5. 树和二叉树（了解）
前面我们介绍的数据结构数组、栈、队列，链表都是线性数据结构，除此之外还有一种比较复杂的数据结构——树。
计算机中的树，是根据生活中的树抽象而来的，表示N个有父子关系的节点的集合。
N为0的时候，该节点集合为空，这棵树就是空树
任何非空树中，有且只有一个根节点（root）
N>1时，一颗树由根和若干棵子树组成，每棵子树由更小的若干子树组成
树中的节点根据有没有子节点，分成两种：
普通节点：拥有子节点的节点。
叶子节点：没有字节点的节点。
二叉树：一种特殊的，遵循某种规则的树。
树的结构因为存在多种子节点情况，真的太复杂了，如果我们对普通的树加上一些约束，比如让每一棵树的节点最多只能包含两个子节点，而且严格区分左子节点和右子节点（左右位置不能交换），此时就形成了二叉树。
排序二叉树，有顺序的树：
若左子树不为空，则左子树所有节点的值小于根节点的值。
若右子树不为空，则右子树所有节点的值大于根节点的值。
左右子树也分别是排序二叉树。
红黑树：更高查询效率的的排序二叉树。
排序二叉树可以快速查找，但是如果只有左节点或者左右右节点的时候，此时二叉树就变成了普通的链表结构，查询效率比较低。为此一种更高效的二叉树出现了——红黑树。
每个节点要么是红色的，要么是黑色的。
根节点永远是黑色的。
所有叶子节点都是空节点（null），是黑色的。
每个红色节点的两个子节点都是黑色的。
从任何一个节点到其子树每个叶子节点的路径都包含相同数量的黑色节点。
若要获得最好的学习效果，需要配合对应教学视频一起学习。需要完整教学视频，请参看https://ke.qq.com/course/272077。
