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]