java开发面试：常见集合ArrayList的源码分析，数组和List的相互转换

ArrayList

底层数据结构——数组

寻址公式

a[i] = baseAddress + i *dataTypeSize
即，数组的首地址+索引乘以存储数据的类型大小。

为什么数组索引从0开始呢？从1开始不行吗？

实际上并不是不行。而是如果数组索引从1开始的话，整体性能会变低。
因为寻址公式会变为a[i] = baseAddress + (i-1) *dataTypeSize，也就是说，多了一个减法操作。

查找/插入/删除的时间复杂度

1. 查找
   • 通过下标查询的时间复杂度是O(1)
   • 未知下标查询的时间复杂度是O(n)
   • 未知下标但排序，通过二分查找的时间复杂度是O(logn)
2. 插入，O(n)
3. 删除，O(n)

数组和List（集合）的转换

数组转List ，使用JDK中java.util.Arrays工具类的asList方法
List转数组，使用List的toArray方法，参数为指定长度的数组实例化对象。如果无参，toArray方法返回 Object数组。

示例代码：

//数组转List
public static void testArray2List(){
    String[] strs = {"aaa","bbb","ccc"};
    List<String> list = Arrays.asList(strs);
    for (String s : list) {
    	System.out.println(s);
    	    }
}
//List转数组
public static void testList2Array(){
    List<String> list = new ArrayList<String>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    String[] array = list.toArray(new String[list.size()]);
    for (String s : array) {
    	System.out.println(s);
    	    }
}

数组转List后修改了数组内容，list受影响吗/List转数组后，修改了List内容，数组受影响吗

Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址。

list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响

源码分析

成员变量

private static final int DEFAULT_CAPACITY = 10;// 初始容量，默认等于10
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;//ArrayList的数组（实际存储数据的数组）
private int size; //ArrayList的大小（实际包含的元素）

EMPTY_ELEMENTDATA ：
无参构造 ArrayList 对象，且没有指定初始容量时，ArrayList 内部的 elementData 数组将会被初始化为 EMPTY_ELEMENTDATA。

通过这种方式，在初始时节省了内存空间，只有在首次添加元素时才会真正分配内部数组的容量。

代码如下：

import java.util.ArrayList;
public class EmptyElementDataExample {
    public static void main(String[] args) {
        // 使用无参构造方法创建 ArrayList 对象
        ArrayList<String> list = new ArrayList<>();
        // 添加元素
        list.add("Apple");
        list.add("Banana");
    }
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：
通过带有指定初始容量的构造方法创建 ArrayList 对象，并将初始容量设置为 0时，ArrayList
内部的 elementData 数组会被初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

多加一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了区分使用了初始容量为 0 的构造方法和无参构造方法的情况，避免了两种情况下 elementData 指向同一个空数组的问题。

代码如下：

import java.util.ArrayList;
public class DefaultCapacityEmptyElementDataExample {
    public static void main(String[] args) {
        // 使用带有指定初始容量的构造方法，并设置初始容量为 0
        ArrayList<String> list = new ArrayList<>(0);
        // 添加元素
        list.add("Apple");
        list.add("Banana");
    }
}

elementData ：
使用带有指定初始容量的构造方法时，elementData初始化为长度为指定初始容量的数组。

需要注意的是，elementData被transient关键字修饰，所以不会被默认的序列化机制持久化保存，即，不会转化为字节流，从而节省存储空间和序列化的时间开销。

代码如下：

import java.util.ArrayList;
public class ElementDataExample {
    public static void main(String[] args) {
        // 使用带有指定初始容量的构造方法，并设置初始容量为 5
        ArrayList<String> list = new ArrayList<>(5);
        // 添加元素
        list.add("Apple");
        list.add("Banana");
        // 获取内部的 elementData 数组
        Object[] elementData = list.toArray();
        System.out.println("elementData数组长度：" + elementData.length);
    }
}

add方法

1. 确保数组已使用长度（size）加1之后足够存下下一个数据?
2. 如果当前数组已使用长度+1后大于当前的数组长度(elementData.length)，则调用grow方法扩容到当前数组长度的1.5倍。
3. 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。?
4. 返回添加成功的布尔值。