ArrayList详解

Java

概述

ArrayList是实现了List接口的类，其主要有以下特点：

  • ArrayList是用数组实现的线性列表，其是相当与动态数组。
  • ArrayList查找、修改速度较快，插入、删除速度较慢。
  • ArrayList可以存放任何元素，包括null对象。
  • ArrayList是线程不同步的。

ArrayList类图如下：

详解

字段及构造方法

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
private static final int DEFAULT_CAPACITY = 10;  // ArrayList默认容量
transient Object[] elementData;  // ArrayList中存放元素的数组
private int size;  // ArrayList存放元素的个数
/**
 * 常量，代表ArrayList中没有元素。只有当使用有参的构造函数且initialCapatity为0时返回它。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 *常量，当使用无参构造函数时返回它。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 默认的构造函数：创建容量为10的ArrayList
 */
public ArrayList(){
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
 * 创建一个指定容量的ArrayList
 * @param initialCapatity ArrayList的容量
 */
public ArrayList(int initialCapatity){
    if(initialCapatity > 0) {
        this.elementData = new Object[initialCapatity];
    }else if(initialCapatity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    }else {
        throw new IllegalArgumentException("Illegal Capatity" + inintCapatity);
    }
}
/**
 * 创建一个包含Collection的ArrayList
 * @param @param c Collection
 */
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);
        }
    }
}

一些常用API的实现

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
public E get(int index){
    // 检查索引位置
    rangeCheck(index);
    return elementData[index];
}
public E set(int index, E element){
    // 检查索引位置
    rangeCheck(index); 
    E oldValue = elementData[index];
    elementData[index] = element;
    return oldValue;   
}
public boolean add(E e){
    // 确保ArrayList有足够的容量：验证+扩容
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
public void add(int index, E element){
    // 检查索引是否合适
    rangeCheckForAdd(index);
    // 确保ArrayList有足够的容量：验证+扩容
    ensureCapatityInternal(size + 1);
    // 把原数组从index后的每一个元素向后移一位
    System.arraycopy(elementData,index,elementData,index+1,size-index);
    elementData[index] = element;
    size++;
}
public E remove(int index){
    // 检查索引位置是否合适
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    // 把原数组从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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 验证+扩容
 * @param minCapacity 现在ArrayList存放元素所需要的最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if(minCapacity - elementData.length > 0){
        // 扩容
        grow(minCapacity);
    }
}
/**
 * 该方法是扩容：扩大至原来的1.5倍，我没有看懂怎么就扩大到原来的1.5倍~(0)~
 */
private void grow(int minCapacity) {
    // 扩大至原来的1.5倍
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity - minCapacity < 0){
        newCapacity = minCapacity;
    }
    if(newCapacity - MAX_ARRAY_SIZE > 0){
        newCapacity = hugeCapacity(minCapacity);
    }
    // elementData扩容
    elementData = Arrays.copyOf(elementData,newCapacity);
}

以上是部分源码分析，然后这里还有几点：

  • 以上是JDK1.8的源码,其中怎么就扩大要原来的1.5倍，我没有看懂。而且为什么要扩大要原来的1.5倍我也不知道。之前版本是增加至(oldCapacity * 3)/2 + 1。
  • 从上面我们可以看出在插入、删除元素时我们需要调用System.arraycopy()方法，这就比较耗时，所以说ArrayList在插入、删除时的速度慢的原因。当然这是由于ArrayList底层使用数组这种数据结构的缘故。

实现

自己模仿写的ArrayList

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;
    // 存放元素数量
    private int size;
    // 存放元素的数组
    private Object[] elementData;

    ArrayList(){
        elementData = new Object[DEFAULT_CAPACITY];
    }

    ArrayList(int initCapacity){
        if(initCapacity > 0){
            elementData = new Object[initCapacity];
        }else {
            throw new IllegalArgumentException("Illegal Capacity" + initCapacity);
        }
    }

    ArrayList(Collection< ? extends E> c){
        elementData = c.toArray();
        this.size = elementData.length;
        if(size != 0){
            if(elementData.getClass() != Object[].class){
                elementData = copyOf(elementData,size,Object[].class);
            }
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public E get(int index) {
        check(index);
        return (E) elementData[index];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean add(E e) {
        ensureCapacity(size + 1);
        elementData[size] = e;
        size++;
        return true;
    }

    @Override
    public void add(int index, E element) {
        check(index);
        ensureCapacity(size + 1);
        System.arraycopy(elementData,index,elementData,index+1,size - index);
        elementData[index] = element;
        size++;
    }

    @Override
    public boolean remove(Object o) {
        for(int index = 0; index < size; index++){
            if(Objects.equals(o,elementData[index])){
                int numMoved = size - index - 1;
                if(numMoved > 0){
                    System.arraycopy(elementData, index + 1, elementData, index, numMoved);
                }
                elementData[size] = null;
                size--;
                return true;
            }
        }
        return false;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        check(index);
        E oldValue = (E) elementData[index];
        int numMoved = size - index - 1;
        if(numMoved > 0){
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[size] = null;
        size--;
        return oldValue;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        check(index);
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    // 验证索引
    private void check(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index:" + index + "Size:" + size);
        }
    }
    // 验证+扩容
    private void ensureCapacity(int minCapacity){
        // 验证
        if(minCapacity > elementData.length){
            // 扩容
            int oldCapacity = elementData.length;
            int newCapacity = (int) (oldCapacity * 1.5);
            elementData =  Arrays.copyOf(elementData, newCapacity);
        }
    }
}