List集合之ArrayList

一、初步了解ArrayList

ArrayList是集合的一种实现，实现了接口List，List接口继承了Collection接口。Collection是所有集合类的父类。

ArrayList底层是用数组实现的存储。

特点：查询效率高，增删效率低，线程不安全。

二、继承结构

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承：AbstractList。
实现：List、RandomAccess、Cloneable、Serializable。

三、源码分析

一、扩容的原理add（）

数组长度有限，而ArrayList是可以存放任意数量的对象，长度不受限制，他是怎样实现的呢？

第一步：add（E e）

1 public boolean add(E e) {
2         // 这句代码是关键，涉及首次添加元素的elementData的初始化和扩容，加入元素前检查容量是否足够
3         ensureCapacityInternal(size + 1);  // Increments modCount!!
4         // 元素被添加在数组末尾
5         // 没有做null检查，元素可以为null
6         elementData[size++] = e;
7         return true;
8     }

第二步：ensureCapacityInternal(size + 1);

 1 private void ensureCapacityInternal(int minCapacity) {
 2         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 3     }
 4 
 5 private void ensureExplicitCapacity(int minCapacity) {         //检查并确保容量
 6         modCount++;
 7 
 8         // overflow-conscious code
 9         if (minCapacity - elementData.length > 0)      //如果添加元素后大于当前数组的长度，则进行扩容
10             grow(minCapacity);       //扩容方法
11     }

第三步:grow(minCapacity);

 1 private void grow(int minCapacity) {
 2         // overflow-conscious code
 3         int oldCapacity = elementData.length;
 4         // 扩容后新的elementData大小：将数组长度增加到原来的一半
 5         int newCapacity = oldCapacity + (oldCapacity >> 1);
 6         // 扩容后仍然不满足需要，则赋值为minCapacity
 7         if (newCapacity - minCapacity < 0)
 8             newCapacity = minCapacity;
 9         // 扩容后超出允许的最大数组大小
10         if (newCapacity - MAX_ARRAY_SIZE > 0)
11             // 确保newCapacity最大只能为Integer.MAX_VALUE
12             newCapacity = hugeCapacity(minCapacity);
13         // 分配新数组，拷贝旧数据
14         elementData = Arrays.copyOf(elementData, newCapacity);
15     }

以上分析可知：

如果使用了默认的构造函数，那么elementData初始化大小为10.

正常情况下，每次扩容后的elementData新大小=1.5倍旧大小。

elementData最大值只能为Integer.MAX_VALUE。

2、add(int index, E element)

 1 public void add(int index, E element) {
 2         // 首先检查inde是否合法
 3         rangeCheckForAdd(index);
 4 
 5         ensureCapacityInternal(size + 1);  // 看elementData的长度是否做够，不够扩容
 6 
 7         // 这个地方主要为了将index位置的数据及其后的数据后移一位
 8         System.arraycopy(elementData, index, elementData, index + 1,
 9                          size - index);
10         // 将元素赋值给数组index处
11         elementData[index] = element;
12         size++;
13     }

二、remove(int index)删除列表中指定位置的元素

 1     public E remove(int index) {
 2         // 检查索引
 3         rangeCheck(index);
 4 
 5         modCount++;
 6         // 获取旧的元素
 7         E oldValue = elementData(index);
 8 
 9         // 计算需要移动的元素个数
10         int numMoved = size - index - 1;
11         if (numMoved > 0)
12             // 通过拷贝完成元素的删除
13             System.arraycopy(elementData, index+1, elementData, index,
14                              numMoved);
15         // 赋值为null，保证可以被GC回收
16         elementData[--size] = null; // clear to let GC do its work
17 
18         // 返回旧的数据
19         return oldValue;
20     }

remove(Object o)删除列表中第一个出现O的元素

 1     // 删除元素。
 2     // 只会删除第一个出现的元素。
 3     public boolean remove(Object o) {
 4         if (o == null) {
 5             // for循环遍历元素。找出待删除元素的index
 6             for (int index = 0; index < size; index++)
 7                 if (elementData[index] == null) {
 8                     fastRemove(index);
 9                     // 此处导致只会删除第一个找到的相等元素
10                     return true;
11                 }
12         } else {
13             // for循环遍历元素。找出待删除元素的index
14             for (int index = 0; index < size; index++)
15                 if (o.equals(elementData[index])) {
16                     fastRemove(index);
17                     // 此处导致只会删除第一个找到的相等元素
18                     return true;
19                 }
20         }
21         return false;
22     }
23 
24     // 该方法与remove(int index)基本相同
25     private void fastRemove(int index) {
26         modCount++;
27         int numMoved = size - index - 1;
28         if (numMoved > 0)
29             System.arraycopy(elementData, index+1, elementData, index,
30                              numMoved);
31         elementData[--size] = null; // clear to let GC do its work
32     }