ArrayList源码解析

ArrayList

List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。
每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。
此实现不是同步的。

• void ensureCapacity(int minCapacity) ：如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。
• protected void removeRange(int fromIndex, int toIndex) ：移除列表中索引在
  fromIndex （包括）和 toIndex （不包括）之间的所有元素。
• void trimToSize() ：将此 ArrayList 实例的容量调整为列表的当前大小。

ArrayList成员变量

 private static final long serialVersionUID = 8683452581122892189L;//序列版本号
 
    private static final int DEFAULT_CAPACITY = 10;//默认数组元素的初始容量为10
    
    private static final Object[] EMPTY_ELEMENTDATA = {};//空元素对象数组

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//默认容量
    
    transient Object[] elementData; // non-private to simplify nested class access
    
    private int size;//添加的元素的数量
1
2
3
4
5
6
7
8
9
10
11

ArrayList构造方法

	public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//判断参数值
            this.elementData = new Object[initialCapacity];//将传入的值作为数组的初始容量
        } else if (initialCapacity == 0) { //假设传入的值为0的情况
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);//传入的值如果小于0，就抛出参数违规异常
        }
    }
   
 	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//空对象数组初始化，其容量为10
    }

	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;
        }
    }
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

ArrayList的增删改查操作

1、ArrayList的add方法

①添加到指定位置add(int index, E element)

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++;//数组的大小增加
    }

1
2
3
4
5
6
7
8
9
10

②添加所有addAll(Collection c)

    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
2
3
4
5
6
7
8

③添加所有到指定位置addAll(int index, Collection c)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.ArrayList的remove方法

①删除指定索引元素 E remove(int index)

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
5
6
7
8
9
10
11
12
13
14

②删除指定值的元素 remove(Object o)

	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
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

3、ArrayList的get方法

	/**
     * 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);//返回元素，并将Object转型为E
    }
	/**
     * 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));
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、ArrayList的set方法

	public E set(int index, E element) {
		//检查index是否小于size,如果不是抛异常
        rangeCheck(index);
		
        E oldValue = elementData(index);
        //覆盖ArrayList中index.上的元素。
        elementData[index] = element;
        //返回被覆盖的元素
        return oldValue;
    }
1
2
3
4
5
6
7
8
9
10

5、遍历元素iterator（）

public Iterator<E> iterator() {
        return new Itr();
    }
private class Itr implements Iterator<E> {
    int cursor;       // 要返回的下一个元素的索引
    int lastRet = -1; // 返回的最后一个元素的索引，如果没有返回-1
    int expectedModCount = modCount;//标记位：用于判断是否在遍历的过程中，是否发生了add、remove操作

    Itr() {}

    public boolean hasNext() {
        return cursor != size;//如果cursor==size，说明已经遍历完了，上一次遍历的是最后一个元素
    }
    
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
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

判断元素是否存在

	//判断动态数组是否包含元素o
	public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
	//返回第一个出现的元素o的索引位置
    public int indexOf(Object o) {
        if (o == null) {  //返回第一个null的索引
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {   //返回第一个o的索引
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;//不包含
    }
	//返回最后一个出现的元素o的索引位置
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
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