ArrayList 概述

ArrayList 实现了 List 接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入 null 元素，底层通过数组实现。除该类未实现同步外，其余跟 Vector 大致相同。每个 ArrayList 都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java 泛型只是编译器提供的语法糖，所以这里的数组是一个 Object 数组，以便能够容纳任何类型的对象。
Collection - ArrayList 源码解析 - 图1

  • size()，isEmpty()，get()，set() 方法均能在常数时间内完成
  • add() 方法的时间开销跟插入位置有关
  • addAll() 方法的时间开销跟添加元素的个数成正比
  • 其余方法大都是线性时间。

为追求效率，ArrayList 没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用 Vector 替代。

ArrayList的实现

底层数据结构

  1.     /**
  2.      * The array buffer into which the elements of the ArrayList are stored.
  3.      * The capacity of the ArrayList is the length of this array buffer. Any
  4.      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5.      * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6.      */
  7.     transient Object[] elementData; // non-private to simplify nested class access
  9.     /**
  10.      * The size of the ArrayList (the number of elements it contains).
  11.      *
  12.      * @serial
  13.      */
  14.     private int size;

构造函数

  1.     /**
  2.      * Constructs an empty list with the specified initial capacity.
  3.      *
  4.      * @param  initialCapacity  the initial capacity of the list
  5.      * @throws IllegalArgumentException if the specified initial capacity
  6.      *         is negative
  7.      */
  8.     public ArrayList(int initialCapacity) {
  9.         if (initialCapacity > 0) {
  10.             this.elementData = new Object[initialCapacity];
  11.         } else if (initialCapacity == 0) {
  12.             this.elementData = EMPTY_ELEMENTDATA;
  13.         } else {
  14.             throw new IllegalArgumentException("Illegal Capacity: "+
  15.                                                initialCapacity);
  16.         }
  17.     }
  19.     /**
  20.      * Constructs an empty list with an initial capacity of ten.
  21.      */
  22.     public ArrayList() {
  23.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  24.     }
  26.     /**
  27.      * Constructs a list containing the elements of the specified
  28.      * collection, in the order they are returned by the collection's
  29.      * iterator.
  30.      *
  31.      * @param c the collection whose elements are to be placed into this list
  32.      * @throws NullPointerException if the specified collection is null
  33.      */
  34.     public ArrayList(Collection<? extends E> c) {
  35.         elementData = c.toArray();
  36.         if ((size = elementData.length) != 0) {
  37.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  38.             if (elementData.getClass() != Object[].class)
  39.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  40.         } else {
  41.             // replace with empty array.
  42.             this.elementData = EMPTY_ELEMENTDATA;
  43.         }
  44.     }