3、静态数组和动态数组
3.1、静态数组
静态数组是固定长度的容器，其中包含n个可从[0，n-1]范围索引的元素。
问：“可索引”是什么意思？
答：这意味着数组中的每个插槽/索引都可以用数字引用。
3.1.1、使用场景
- 1）存储和访问顺序数据
- 2）临时存储对象
- 3）由IO例程用作缓冲区
- 4）查找表和反向查找表
- 5）可用于从函数返回多个值
- 6）用于动态编程中以缓存子问题的答案
3.1.2、静态数组特点
- 只能由数组下标访问数组元素，没有其他的方式了；
- 第一个下标为0；
- 下标超过范围了会触发数组越界错误。
3.2、动态数组
动态数组的大小可以增加和缩小。
3.2.1、如何实现一个动态数组
使用一个静态数组：
- 创建具有初始容量的静态数组；
- 将元素添加到基础静态数组，同时跟踪元素的数量；
- 如果添加元素将超出容量，则创建一个具有两倍容量的新静态数组，然后将原始元素复制到其中。
3.3、时间复杂度
| 操作 | 静态数组 | 动态数组 |
|---|---|---|
| 访问 | O(1) | O(1) |
| 查找 | O(n) | O(n) |
| 插入 | / | O(n) |
| 追加 | / | O(1) |
| 删除 | / | O(n) |
3.4、编程实践
-
JDK中的实现：
java.util.ArrayList -
练习：