ArrayList、LinkedList、HashMap等集合，从其前缀可知其对应的数据结构为数组、链表、哈希表。从数据结构，也可反推出集合的结构。
文章目录
- 1、算法复杂度分析
- 1.1 时间复杂度
- 1.2 常见复杂度
- 1.3 空间复杂度
- 2、数组
- 2.1 内存寻址
- 2.2 查找元素的时间复杂度
- 2.2 增删元素的时间复杂度
- 3、ArrayList源码
- 3.1 成员变量部分
- 3.2 构造方法部分
- 3.3 添加数据和扩容
- 4、ArrayList底层的实现原理
- 5、实现数组和List之间的转换
1、算法复杂度分析
- 时间复杂度：评估代码的执行耗时（与数据规模n的关系）
- 空间复杂度：内存占用（与数据规模n的关系）
1.1 时间复杂度
以上，有3 * n + 3 行代码，假设每行执行耗费1ms，则总耗时：
T(n) = (3n + 3) * 1ms
时间复杂度，即表示代码执行时间与数据规模n变化的趋势 ⇒ 大O表示法 ⇒
T(n) = O(3n + 3)
因为表示的是一种”趋势”，因此去掉系数和常数：
得出：
T(n) = O(n)
1.2 常见复杂度
总结：常对幂指阶
如O(1)，性能最好，即数据变多，执行耗时还是不变，或者说代码行数是固定的。
如下：只要代码的执行时间不随着n的增大而增大，这样的代码复杂度都是O(1) ，第二个例子中，虽然有循环，但其次数固定，是100，是i < 100，而不是i < n，因此复杂度仍然为O(1)
例2：
例3：
此时，代码的执行和数据规模n的关系如下。因此，时间复杂度为O(log n)
同理，以下的实现复杂度也算为O(log n)
例4：O(n)复杂度的方法调用了O(log n)复杂度的方法，因此，test05方法的时间复杂度为O(n * log n)
1.3 空间复杂度
如下，两个局部变量i和sum，不管n等于多少，循环多少次，都占这两个变量的空间，因此，空间复杂度为O(1)
如下，数据规模n，影响数组长度，也即空间大小，因此，空间复杂度为O(n)
2、数组
2.1 内存寻址
用连续的内存空间存储相同数据类型元素的线性数据结构。数组变量的值，指向0号元素的首地址。
取array[3]的值时，即计算索引为3的元素的内存地址：
//寻址
a[i] = baseAddress + i * dataTypeSize
//baseAddress：数组首地址，如图中的10
//dataTypeSize：数组中元素类型的大小，如int时，该值为4（4 byte）
这也是数组下标从0开始的原因：让CPU少做一次减法运算
//寻址（下标从0开始）
a[i] = baseAddress + i * dataTypeSize
//寻址（下标从1开始）
a[i] = baseAddress + （i - 1） * dataTypeSize
2.2 查找元素的时间复杂度
根据索引查时，有寻址公式直接定位，复杂度为O(1)
未知索引，比如找值为55的这个元素。不排序，就得遍历，时间复杂度为O(n)。排序后二分查找，时间复杂度为O(log n)
2.2 增删元素的时间复杂度
数组是一段连续的空间，因此，插入或删除元素，其他元素会前移或者后退，时间复杂度为O(n)
3、ArrayList源码
3.1 成员变量部分
elementData这个Object类型的数组，是真正存储集合中元素的地方- size：元素个数
3.2 构造方法部分
无参构造，默认elementData是一个空数组{}。传入一个初始化容量的有参构造，逻辑为：传入的容量大于0时，给elementData复制一个对应长度的数组，等于0则给elementData赋值空数组
接收一个Collection（单列集合的父类）的参数，将 collection 对象转换成数组，然后将数组的地址的赋给 elementData
3.3 添加数据和扩容
添加数据和扩容的基本思路为：add前，先确保容量size + 1够不够，size为当前元素个数，size +1如果超过了elementData数组的长度，就需要扩容。扩容时，elementData长度 + elementData长度右移一位（除以2），然后将原elementData拷贝到新容量的elementData数组中
List<Integer> list = new ArrayList<>();
list.add(1);
for (int i = 2; i <= 10; i++) {
list.add(i);
}
list.add(11);
以上，用了无参构造，因此，elementData是一个空数组{}。第一次add的时候：调用扩容方法的判断条件成立，扩容到10
往后，第2次 ~ 第10次add数据时，均不需扩容。比如第十次add：
第十一次add时：elementData长度为第一次扩容的10，而size + 1为11了，大于了elementData.length，扩容。新容量为
elementData.length + (elementData.length >> 1)
//10 + 10 >> 1 = 10 + 10/2 = 15
10扩容为15（约1.5倍），底层的elementData数组拷贝到一个长度为15的新数组
4、ArrayList底层的实现原理
- ArrayList底层是一个数组（elementData属性）
- ArrayList初始容量为0（elementData为空数组
{}），当第一次添加数据时，才会初始化容量为10 - ArrayList扩容的时候，容量为原容量的1.5倍，且每次扩容都需要拷贝数组
调用add添加数据的时候，逻辑如下：
- 确保能存下 下一个数据，判断逻辑是数组已使用长度(size) +1 后是否大于elementData数组的长度
- size +1 > elementData.length则调用grow方法扩容
- 反之，则直接放进去
ArrayList myList = new ArrayList(10);
以上写法，list扩容0次，因为指定了容量为10，elementData数组不再是空数组{ }，因此，第一次add时不会再扩容。
5、实现数组和List之间的转换
- 数组转List，使用java.util.Arrays工具类的asList方法
- List转数组，调用其toArray方法，传参为带list长度的一个空数组
用 Arrays.asList 将数组转List 后，如果修改了数组内容，则由数组转来的List也会跟着变
测试代码：
原因：Arrays工具类底层用静态内部类ArrayList，将传入的数组进行了包装，最终指向的都是同一个内存地址。也就是说，数组转List后，List底层的数组，还是指向原数组
调用toArray方法，将List转为数组，此时再修改List，由List转来的数组并不跟着变
原因：调用了 toArray 以后，返回的是对ArrayList的elementData数组进行的拷贝
