ArrayList 源码

技术
字数统计: 3.2k字   |   阅读时长≈ 16分钟

概述

  • 动态数组

ArrayList 是基于数组实现的 List，相对于数组， ArrayList 提供了动态扩容的能力，故称之为 动态数组 。

  • 自动扩容

ArrayList 允许任何符合规则的元素插入，甚至包括null。在每次增加元素时，都会进行容量检查，快溢出时就会进行扩容，扩容后的容量是原来的1.5倍。

继承结构

ArrayList 继承结构

  • ArrayList 实现了 List 接口

提供 查询、删除、遍历等操作

  • ArrayList 实现了 RandomAccess 接口

提供了随机访问的能力

源码实现

属性

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;
  • DEFAULT_CAPACIT。

默认容量时，创建的空数组；当添加第一个元素后，默认扩容的容量为 10。

  • EMPTY_ELEMENTDATA

指定容量为 0 时，创建的空数组。 即 new ArrayList(0);，当添加一个元素时，扩容到 1。

  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA

默认容量时，创建的空数组。即 new ArrayList();，当添加一个元素时，扩容到 10。

  • elementData

真正存放元素的地方。使用 transient 修饰，不序列化该字段。
关于 transient

  • size

真正存储元素的个数，不是 elementData 的长度。

构造方法

ArrayList()

无初始容量，初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，会在添加第一个元素的时候扩容为默认的大小，即10。

1
2
3
4
5
6
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList(int initialCapacity)

传入初始化容量。如果初始化容量大于0，则elementData为对应的大小；如果初始化容量等于0，就使用 EMPTY_ELEMENTDATA 空数组；如果小于0，则抛出异常。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

ArrayList(Collection<? extends E> c)

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为0，则初始化为EMPTY_ELEMENTDATA空数组。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}

操作方法

add(E e)

添加元素到末尾，平均时间复杂度为O(1)

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
  1. 检查是否需要扩容；
  2. 如果 elementData 等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则需要的容量为 Math.max(DEFAULT_CAPACITY, size + 1)；否则需要的容量为 size + 1；
  3. 新容量扩容为原来的 1.5 倍（oldCapacity + (oldCapacity >> 1)），如果扩容后的新容量比需要的容量还小，则以需要的容量为准；如果超过了最大容量，以最大容量为准；
  4. 最大容量为 Integer.MAX_VALUE - 8，即 (2^31 - 1 - 8)；其中 8 bytes 存储数组本身大小的描述信息；
  5. 创建新容量的数据，把原来数组的数据拷贝进去；

add(int index, E element)

添加元素到指定位置，时间复杂度为O(n).

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
  1. 检查索引是否越界；
  2. 检查是否需要扩容，如果需要，则进行扩容操作；
  3. 拷贝并把插入索引的位置后的元素后移一位；
  4. 载入的位置放置要插入的元素；
  5. 元素计数器加 1；

addAll(Collection<? extends E> c)

将一个集合追加到另一个集合的尾部。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
  1. 将集合转为数组 a；
  2. 检查是否需要扩容，如果需要，则执行扩容操作；
  3. 把数组 a 中的元素拷贝到 elementData 的尾部；

addAll(int index, Collection<? extends E> c)

将一个集合插入到另一个集合，插入的起点为数组的 index 位置。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element from the
 *              specified collection
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}
  1. 将集合转为数组 a；
  2. 检查是否需要扩容，如果需要，则执行扩容操作；
  3. 从 index 开始，将集合中的元素后移 numNew 位；
  4. 把数组 a 中的元素拷贝到 elementData 中，起点为 index；

get(int index)

获取指定位置的元素，时间复杂度为O(1)。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

/**
 * Checks if the given index is in range.  If not, throws an appropriate
 * runtime exception.  This method does *not* check if the index is
 * negative: It is always used immediately prior to an array access,
 * which throws an ArrayIndexOutOfBoundsException if index is negative.
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
    return (E) elementData[index];
}
  1. 检查索引是否越界，如果越界，则抛出 IndexOutOfBoundsException 异常；
  2. 返回索引位置处的元素；

remove(int index)

删除指定位置的元素，时间复杂度为O(n)。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
  1. 检查索引是否越界；
  2. 获取指定位置的元素；
  3. 如果删除的不是最后一个元素，则从指定位置的后一位元素开始，尾部元素向前移一位；
  4. 将最后一个元素置为null；
  5. 返回删除的元素；

remove(Object o)

删除指定的元素，时间复杂度为O(n)。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}
  1. 找到第一个等于指定值的元素；
  2. 快速删除；

retainAll(Collection<?> c)

取两个集合的交集。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Retains only the elements in this list that are contained in the
 * specified collection.  In other words, removes from this list all
 * of its elements that are not contained in the specified collection.
 *
 * @param c collection containing elements to be retained in this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (<a href="Collection.html#optional-restrictions">optional</a>),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}
  1. 遍历elementData数组；
  2. 如果元素在c中，则把这个元素添加到elementData数组的 w 位置，并将 w 位置往后移一位；
  3. 遍历完之后，w 之前的元素都是两者共有的，w 之后（包含）的元素不是两者共有的；
  4. 将 w 之后（包含）的元素置为null；

removeAll(Collection<?> c)

求两个集合的差集，只保留不在集合 C 中的元素。

View Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Removes from this list all of its elements that are contained in the
 * specified collection.
 *
 * @param c collection containing elements to be removed from this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (<a href="Collection.html#optional-restrictions">optional</a>),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

与 retainAll(Collection<?> c) 方法类似，batchRemove(c, false) 只保存不存在的元素。

总结

  1. ArrayList 底层使用数组存储元素，当数组长度不够时进行扩容，每次扩容为原来的 1.5 倍；对集合元素进行删除操作不会缩容；
  2. ArrayList 支持随机访问，通过索引访问元素，时间复杂度为O(1)；
  3. ArrayList 在尾部添加（或删除）元素，时间复杂度为O(1)；
  4. ArrayList 在中间添加（或删除）元素，要进行元素的移位，时间复杂度为O(n)；
  5. ArrayList 支持求集合并集：addAll(Collection<? extends E> c)；
  6. ArrayList 支持求集合交集：retainAll(Collection<?> c)；
  7. ArrayList 支持求集合的差集：removeAll(Collection<?> c)；

FAQ

Q：ArrayList、Vector、LinkedList的区别？

  • Vector 和 ArrayList 都是以类似数组的形式存储在内存中，LinkedList 以链表的形式进行存储
  • Vector 线程同步，ArrayList 和 LinkedList 线程不同步
  • LinkedList 适合在指定位置进行插入、删除等操作，不适合查找，Vector、ArrayList 适合查找
  • Vector 默认扩充为原来的两倍，ArrayList 默认扩充为原来的1.5倍
打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2015-2020 Andrew
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信