ArrayList

参考

JDKSourceCode1.8

木杉的博客

泛型通配符的概念

前言

底层是 array 实现的。很像学 C 时老师会布置的那种作业，用数组实现一个 List…

类名

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

主要是实现 List 接口。

成员变量

	 /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空的对象数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 默认的空数组
     * 无参构造函数创建的数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存放数据的数组的缓存变量，不可序列化。
     * 因为 elementData 的大小一般比 ArrayList 当前存放的数据个数要大，如果序列化的时候直接把整个	 * elementData序列化了，会很浪费空间的，所以ArrayList并没有这么做，而是在writeObject和		 * readObject中自定义序列化、反序列化的方法。
     */
    transient Object[] elementData;

    /**
     * 元素数量
     * @serial
     */
    private int size;

为什么有一个 EMPTY_ELEMENTDATA 还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA ？

查看构造函数，发现 public ArrayList() 使用到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，而 public ArrayList(int initialCapacity) 使用到 EMPTY_ELEMENTDATA 。

这两个空数组虽然对应的都是空 ArrayList，但是具有不同的含义。

1. List<Integer> list = new ArrayList<Integer>();
2. List<Integer> list = new ArrayList<Integer>(0);

当使用 2. 这种构造方式时，就默认用户对定义的容器的大小是有预期的（虽然是 0）。

在执行 add() 方法时，会先进行对数组大小的判断，如果大小不足，会进行扩容。

public boolean add(E e) {
    // 扩容        --不一定需要扩容嘛,有判断的过程
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将e赋值给elementData的size+1的位置
    elementData[size++] = e;
    return true;
}

在 ensureCapacityInternal() 方法的内部，有一个判断与扩容的过程。在第一次执行 add() 方法时，如果使用无参构造函数，会默认用户对容器的大小没有预期，所以把容器扩展为默认的 DEFAULT_CAPACITY 大小。

否则的话，就按照一般的增长方式来增长容器大小。

//为了得到最小的扩容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;

transient Object[] elementData 中 transient 修饰符什么意思？

transient 表示在序列化的时候不会序列化该字段。

实现 Serializable 接口，就可以序列化，序列化是为了数据的传输。

平时使用情形：面对用户的敏感信息，银行账号等，不适合在网络上操作，就不序列化。

这里不序列化是为了优化空间使用，把序列化的操作放在了其他地方按情况操作。

总结

  • ArrayList的无参数构造函数新建的长度为0，添加第一个元素后，长度为默认长度10
  • ArrayList指定新建的长度为0，添加第一个元素后，长度为1，为正常增长结果
  • ArrayList通过数组存放数据，成员是elementData

时间复杂度

  • size，isEmpty 都由常量 size 维护，调用是常数时间
  • get，set 由于底层使用 array，调用是常数时间

  • iterator 和 listIterator 的调用是常数时间的。（为什么？因为直接返回一个 iterator 和 listIterator 对象？）

  • 插入，删除，查找的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。

很容易想象，在插入，删除，查找时都需要遍历，所以时间复杂度为 O(n)，除此之外，插入和删除还会执行数组的拷贝，所以效率不高，还会造成内存浪费。

/**
 * 在ArrayList的index位置，添加元素element，会检查添加的位置和容量
 *
 * @param index   指定元素将被插入的索引
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 判断index是否越界
    rangeCheckForAdd(index);
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
    //src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度
    // 将elementData从index位置开始，复制到elementData的index+1开始的连续空间
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 在elementData的index位置赋值element
    elementData[index] = element;
    // ArrayList的大小加一
    size++;
}

同理，在 remove() 中也涉及到 System.arraycopy()。

contains(Object o)

用 indexOf

构造方法

《java 编程思想》

所有的 Collection 子类型都有一个接受另一个 Collection 对象的构造器,用所接受的 Collection 对象中的元素来填充新的容器.

public boolean addAll(Collection<? extends E> c) 也是接受这样的对象。

/**
 * 带参数Collection的构造方法
 *
 * 这个的意思就是构造时可以接受 Collection 的子类初始化
 * 比如 接受 LinkedList 的实例
 *
 * 继承自 E 的任意类型
 *
 * @param c 其元素将被放入此列表中的集合
 * @throws NullPointerException 如果指定的集合是空的
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {//这一段是为什么?
        // c.toarray可能（错误地）不返回对象[]（见JAVA BUG编号6260652）
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 使用空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

测试达到的效果：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(2);

ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);
System.out.println(arrayList1);

ArrayList<Integer> arrayList2 = new ArrayList<>(linkedList);
System.out.println(arrayList2);

输出

[1]
[2]