Java基础知识之ArrayList知识点总结

本文包含常见的ArrayList的基本知识。在一些主题下也自然地引出了Colletion类的一些相关知识。

一.ArrayList的底层数据结构

ArrayList底层是使用一个Object[]数组来存储数据的，所以它本质上是一个线性存储结构。这就造成了它可以在O(1)时间内随机访问任意一个元素。但插入元素或删除元素时就要移动大量的元素，时间复杂度是O(n)

二.ArrayList初始化和容量增长规则

默认初始化
ArrayList初始化时如果不指定容量大小，则默认大小为10。但元素数组elementData并不是在构造方法中完成容量为10的初始化的，而是在第一次添加元素时，才生成大小为10的数组。

每次添加元素，首先要检测当前数组的容量是否满足当前size+1,（size指当前持有元素的个数），如果不满足则扩展数组大小为oldCapacity + (oldCapacity >> 1)，即为原大小的1.5倍。

带容量参数
如果传入容量参数进行初始化，则会直接生成相应大小的数组。

从Collection初始化
可以给ArrayList传入一个Collection来初始化，初始化后的ArrayList和原Collection无关，是一种深拷贝。这个方法在复制ArrayList时有用。

相关代码：

//保存元素的数组
transient Object[] elementData; // non-private to simplify nested class access

//默认构造方法
//elementData指向一个static final常量，该常量为一个长度为0的Object[]数组
//在第一次添加元素时，会生成长度为10的数组
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//传入容量参数的构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//深拷贝Collection进行初始化
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

三.elementData为什么使用transient修饰

首先，ArrayList是实现了java.io.Serializable接口，即ArrayList是支持序列化的。

其次，transient关键字的意思是序列化时要跳过的元素，即不进行序列化。

看起来是有矛盾的，但java中除了默认序列化外，还可以在类中提供writeObject()方法进行自定义序列化，和readObject()方法进行自定义反序列化。ArrayList就是这么做的。

而由于elementData数组中往往有没有用到的空间，为了不让这些无意义的元素也序列化，就自定义了序列化方法，只序列化0到size-1的元素，从而节省序列化后的占用空间。

源码如下：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}


private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

四.forEach循环是怎么实现的

请看我之前的一篇文章

五.ArrayList转化为数组

ArrayList中有两个方法可以转换为数组，一个是toArray()：转换为Object[]数组。由于Object[]类型不能强制转换为Integer[]等子类型，所以这个方法不使用。toArray()还有一个带参数的版本（传入一个数组），可以将elementData转换为传入的数组类型并返回，如果传入的数组大小够装下所有的ArrayList元素，则直接使用传入的数组，否则新建数组。
使用举例：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++)
        list.add(i);
    //传入大小和ArrayList元素个数一样的数组就不用再新建数组了
    Integer[] arr = list.toArray(new Integer[list.size()]);
    System.out.println(Arrays.toString(arr));
}

六.将其它Collection的元素添加到ArrayList

使用addAll(Collection<? extends E> e)方法，可以看到参数需要是一个Collection，并且泛型类必须是当前ArrayList持有的类型或其子类。

这个方法其实是Collection接口的一个方法，这也就是说所有Collection的实现类之间都可以通过addAll这个方法来相互合并。

使用举例

ArrayList<Integer> list = new ArrayList<Integer>();
HashSet<Integer> set = new HashSet<Integer>();  //Set接口也实现了Collection接口
for(int i = 10; i < 15; i++) set.add(i);
list.addAll(set);
System.out.println(list);

//同理，也可以将ArrayList添加到Set中
set.add(list);
System.out.println(set);

七.打印ArrayList

在其父类的父类AbstractCollection中实现了一个toString()方法。所以可以调用list.toString()来获取ArrayList的字符串形式。使用System.out.println(list)打印时，toString()可以省略。

下面顺便记录一下Collection的体系结构：

1. Collection是集合类的顶层接口。它继承自Iterable，保证了所有Collection的实现类都可以通过迭代器或forEach循环访问元素；它定义了add()、remove()、size()、iterator()等基本的功能方法;
2. 按照面向对象设计的常用的一个技巧，通常会使用一个抽象类来实现子类共同的功能。Collection体系中也是这么做的。AbstractCollection抽象类实现了Collection接口，就是在这里实现了toString()、addAll()等方法。
3. 在AbstractCollection之下又实现了AbstractList、AbstractSet、AbstractQueue三个接口，也是定义List、Set、Queue各自通用的功能。

最后，欢迎大家关注我的基础知识专题、Java并发专题，查看更多相关文章。