【Java面试】十三、ArrayList相关

ArrayList、LinkedList、HashMap等集合，从其前缀可知其对应的数据结构为数组、链表、哈希表。从数据结构，也可反推出集合的结构。

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数组进行的拷贝