JAVA学习-ArrayList详解

1.定义

ArrayList是实现了List接口的大小可变数组，实现了所有可选列表操作，运行Null在内的所有元素。以下源码是基于JDK 1.7.0_79 (疑问提出：1.如何实现大小可变的?)

2.结构

ArrayList的类的结构如下图所示

image

从上图中可以清晰的ArrayList的体系结构，主要实现、继承的接口如下：

1.Collection 接口： Collection接口是所有集合类的根节点，Collection表示一种规则，所有实现了Collection接口的类遵循这种规则

2.List 接口： List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合

3.AbstractCollection 类： Collection接口的骨架实现类，最小化实现了Collection接口所需要实现的工作量(疑问，为啥要这么做)

4.AbstractList 类： List接口的骨架实现类，最小化实现了List接口所需要实现的工作量

5.Cloneable 接口： 实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制，如果没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。正常情况下，实现了Cloneable接口的类会以公共方法重写Object.clone()

6.Serializable 接口： 实现了该接口标示了类可以被序列化和反序列化，具体的 查询序列化详解

7.RandomAccess 接口： 实现了该接口的类支持快速随机访问

3.实现原理

下面通过源码来分析ArrayList的实现原理，主要的关注的内容如下几点

3.1 底层结构

3.1.1 基础属性

ArrayList部分源码如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;
    
    private int size;

    //...省略部分代码
}

如上代码中为ArrayList的主要属性

1. DEFAULT_CAPACITY：默认容量，即为初始值大小

2. EMPTY_ELEMENTDATA：共享的空数组，用于初始化空实例

3. elementData：ArrayList内部结构，是一个Object[]类型的数组

4. size：数组长度大小

3.1.2 构造方法

如下为ArrayList的构造方法

1.public ArrayList(int initialCapacity)

2.public ArrayList()

3.public ArrayList(Collection<? extends E> c){
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

1.构造方法1，表示接受指定地容量值，初始化创建数组，建议在可估算数组大小时,创建ArrayList可指定

2.构造方法2，是默认的构造方法，它将创建一个空数组

3.构造方法3，接收一个Collection的实体，将该Collection实体转换为ArrayList对象

3.1.3 主干流程

1.添加指定元素代码如下

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

可以看到实际上只有3行代码，其流程主要如下：

1.扩容 (这里便解释了，在介绍时提出的问题)：

主要源码如下

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

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

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

//最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

• 第一个方法的逻辑为：判断是不是第一次添加元素，若为第一次，则设置初始化大小为默认的值10,否则使用传入的参数

• 第二个方法的逻辑为：若长度大于数组长度，则扩容

• 第三个方法的逻辑为:

  1·扩容的大小为3/2倍原数组长度

  2.若值newCapacity比传入值minCapacity还要小，则使用传入minCapacity，若newCapacity比设定的最大数组容量大，则使用最大整数值

  3.实际扩容，使用了Arrays.copyof(elementData, newCapacity)
  (此处有两个问题
  1.为啥扩容是原来的3/2倍原数组的长度?
  2.调用Arrays.copyOf(elementData, newCapacity)方法具体做了什么操作?
  )

2.赋值：将添加的值放置到size++的位置上

3.返回：返回true

2.添加指定元素到指定的位置上代码如下

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.校验下标：调用rangeCheckForAdd方法进行下标校验，不正确则会抛出IndexOutOfBoundsException异常

2.扩容：详见上部分中做的介绍

3.移动数据：将数据index后面的数据，都向后移动

4.赋值：将加入的值放置到index位置中

5.长度增加：长度增加

4.常用的方法

4.1 基本方法

ArrayList基本的方法如下所示

方法	说明	实现原理
boolean contains(Object o)	返回列表中包含指定的元素	内部调用indexOf()方法进行判断，遍历列表进行查询，需要注意的是需要实现equals方法比较对象是否相等
E get(int index)	返回此列表中指定位置上的元素	内部主要两步，首先检查索引，然后获取数组对象索引的元素
E set(int index, E element)	用指定元素替代指定位置上的元素	需要注意的是该方法还会返回老的元素的值，内部主要三步，首先检查索引，然后获取老的元素，赋值并返回
E remove(int index)	删除指定位置上的元素	内部实现步骤为 1.检查索引 2.获取老的元素 3.将index后的元素向前移动 4.最后一个元素置为null并返回老的元素
boolean remove(Object o)	删除列表中首次出现指定元素（如果存在）	内部实现为 1.判断为NULL，若是则遍历并删除 2.若不是则遍历并删除

4.2 ArrayList遍历

ArrayList遍历方式主要有以下几种方式

1.使用for循环的方式，代码如下

for (int i = 0; i < arrayList.size(); i++) {
    System.out.println(arrayList.get(i));
}

2.使用foreach方式

for (String str : arrayList) {
    System.out.println(str);
}

3.使用Iterator迭代器方式

Iterator<String> ite = arrayList.listIterator();
while (ite.hasNext()){
    System.out.println(ite.next());
}

5.常见问题

1.问题描述

在使用ArrayList比较常见的一个问题就是在遍历ArrayList的时候调用remove()方法进行元素的删除操作,从而得到意想不到的结果，本人在开发过程中也遇到过这样的问题，所以在这里提出了，希望能够帮助到大家。

2.实例及分析
如下代码中，在遍历List时，调用了remove方法，删除元素a

//arrayList中的值为 [a,a,c,a,a]
for (int i = 0; i < arrayList.size(); i++) {
    if (arrayList.get(i) == "a") {
        arrayList.remove(i);
    }
}
System.out.println(arrayList);

这段代码看似解决了删除列表中所有的a元素，但是删除后得出List的结果为[a, c, a]，为什么这种方式没有达到想要的效果，其实仔细分析后会发现，在调用remove()方法时List的长度会发生变化而且元素的位置会发生移动，从而在遍历时list实际上是变化的，例如
当i=0时，此时list中的元素为[a,a,c,a,a],
但当i=1时，此时List中的元素为[a,c,a,a],元素的位置发生了移动，从而导致在遍历的过程中不能达到删除的效果
3.解决方案
通过上述的分析可以看出，出现问题的原因是元素的位置发生了移动，从而导致异常的结果

方案一、逆向遍历List删除,代码如下，这种做法可行主要是因为remove()方法删除index处的元素时，是将index+1到size-1索引处的元素前移，而逆向遍历可以避免元素位置的移动

for (int i = arrayList.size()-1; i >=0 ; i--) {
    if (arrayList.get(i) == "a") {
        arrayList.remove(i);
    }
}
System.out.println(arrayList);

方案二、使用迭代器中的remove方法，迭代器具体参考Iterator详解，主要代码如下(这种方式比较推荐)

Iterator<String> ite = arrayList.listIterator();
while (ite.hasNext()){
    if(ite.next() == "a")
        ite.remove();
}
System.out.println(arrayList);

6.总结

本文主要讲解ArrayList的底层实现、主要流程、常用方法等，有写的不好的地方还望指正