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。

测试代码：

1.2.3. 打印操作（掌握）

1.2.4. 保存操作（掌握）

测试代码

输出结果：

[]

[11,22,33,44,55]

因为数组的长度是固定的，此时的players数组只能存储5个元素，如果再多存储一个就报错：数组索引越界。此时就要考虑在保存操作时对数组做扩容操作，扩容的原理是：

• 创建一个原数组长度两倍长的新数组
• 把旧数组中的所有元素拷贝到新数组中
• 把新数组的引用赋给旧数组变量

保存操作时扩容操作：

//向场上添加一个球员号码

1.2.5. 查询操作（掌握）

需求：查询指定索引位置球员的球衣号码是多少，如查询索引位置为2的球衣号码是33。

其实就是返回数组中，指定索引对应的元素值。

测试代码：

Integer playerNum = list.get(2);

System.out.println(playerNum);

输出结果：

33

1.2.6. 修改操作（掌握）

需求：替换场上索引位置为2的球员，使用333号替换33号。

1.2.7. 删除操作（掌握）

需求：罚下场上索引位置为2的球员（直接罚下，没有补位）。

删除操作的原理，把后续的元素整体往前挪动一个位置。

1.2.8. 让容器支持存储任意数据类型的元素（掌握）

此时元素类型是Integer类型，也就是只能存储整型的数据，但是却不能存储其他类型的数据，此时我们可以考虑吧元素类型改成Object，那么Object数组可以存储任意类型的数据。

1，首先是定义成员变量和构造器：

2，添加和查询方法：

3，替换和删除方法：

4，打印方法：

1.2.9. 数组的性能分析（了解）

在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，常用大O符号来表述。

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

我们在这里针对ArrayList存储数据的增删改查（CRUD）做性能分析：

• 保存操作：

如果保存在数组的最后一个位置，至少需要操作一次。

如果保存在数组的第一个位置，如果存在N个元素，此时需要操作N次(后面的元素要整体后移)。

平均: (N+1) /2 次。 N表示数组中元素的个数。 如果要扩容，更慢，性能更低。

• 删除操作:

如果删除最后一个元素，操作一次。

如果删除第一个元素，操作N次。

平均：(N+1)/2次.

• 修改操作: 操作1次.
• 查询操作：根据索引查询元素: 操作1次.

结论：基于数组的数据结构做查询是和修改是非常快的，做保存和删除操作比较慢了。

那如果想保证保存和删除操作的性能，此时就得提提链表这种数据结构了。

本系列教程为叩丁狼Java基础班内部教材，若要获得最好的学习效果，需要配合对应教学视频一起学习。需要完整教学视频，请私信作者。