ArrayList和LinkedList不得不说的事

本文从ArrayList和LinkedList的不同点入手，到增加/删除元素API的效率比较，顺带扩充知识面：简述随机访问接口RandomAccess、vector集合，最后以ArrayList何时扩容、如何扩容(源码分析)收尾。

热身一下：List、Set、Map的区别？

• List存储一组不唯一、可重复的对象，即可以有多个元素引用相同的对象。
• Set是一个不允许重复的集合，即不会有多个元素引用相同的对象。
• Map键值对存储，每个value与一个独一无二的key关联，两个Key可以引用相同的对象，单Key不能重复。如果使用自定义对象作为Key的时候，经常需要重写hashCode()和equals()。

ArrayList和LinkedList的不同点

1. 两者都是非线程安全的，但是底层数据结构不同：

   ArrayList底层使用Object数组；

   LinkedList底层JDK1.6及之前采用循环双向链表，之后采用的都是双向链表。

2. 正因为二者底层数据结构的不同，内存空间浪费的主要体现也不同：

   ArrayList主要是在列表结尾经常会预留一定的容量空间；

   而LinkedList的空间花费主要体现在其每个数据元素，都需要消耗一定的额外空间(因为要存储元素的前驱和后继)。

3. 数据结构不同，决定了他们各种操作之间的效率不同，拿add和remove来说：

   ArrayList的Add(E e)方法会默认将e追加到列表末尾，时间O(1)，但是如果指定插入位置index的操作add(int index, E element)，时间就是O(n)，因为要将index之后的元素都向后移动，remove操作也是O(n)，因为要将被移除元素之后的所有元素向前移动；

   相较LinkedList的插入操作add(E e)和remove操作虽然整体也是O(n)，但原因是需要线性查找元素或指定位置所造成的。

   *虽然 ArrayList 和 LinkedList 的 add/remove 方法都是 O(n)，但是在很多场景下 ArrayList 会略快一点。因为影响其时间的大量元素移位操作是调用 System.arraycopy() 进行内存连续空间拷贝完成的。这一点相较于LinkedList的大量非连续性地址访问，最终还是略胜一筹的。 *关于arraycopy()方法文末会详细分析。

4. 之所以上述LinkedList的操作必须要有线性查找，原因就是其不支持高效的随机元素访问；而ArrayList则天然的支持这一点。

RandomAccess接口

public interface RandomAccess {}

空接口，只是起到一个标识的作用罢了！标识实现此接口的类具有随机访问的特性。

因此ArrayList实现了此接口，而LinkedList没有实现。

在Collections的binarySearch方法中就有对这个空接口的应用：

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

只要有一些 Java 语法基础就很容易看懂这个接口的应用。

从上述代码的 if else 分支不难总结出list的遍历方式如何选择：

• 如果是实现了RandomAccess接口的 list，因为其支持高效的随机元素访问，所以优先选择普通的 for 循环进行遍历，其次是 foreach。
• 如果是没有实现RandomAccess接口的 list，优先选择iterator遍历(foreach遍历的底层也是采用iterator实现的)，尤其是数据量较大的情况下，决不能使用普通for循环。

Vector

Vector类已经被ArrayList取代了，虽然Vector类的方法都是线程安全的，但是其在同步操作上耗费的时间消耗过于巨大。

ArrayList扩容

既然ArrayList底层选择Object数组实现，那么就不得不面对数组的一大麻烦：扩容！

构造方法

既然说其”扩”容，那就不得不提何时扩容？先看一下其几个常用构造方法：

/**
    * 默认初始容量大小
    */
   private static final int DEFAULT_CAPACITY = 10;
   

   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
    */
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
   
   /**
    * 带初始容量参数的构造函数。（用户自己指定容量）
    */
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {//初始容量大于0
           //创建initialCapacity大小的数组
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {//初始容量等于0
           //创建空数组
           this.elementData = EMPTY_ELEMENTDATA;
       } else {//初始容量小于0，抛出异常
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }


  /**
   *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
   *如果指定的集合为null，throws NullPointerException。 
   */
    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;
       }
   }

可以指定ArrayList的初始数组大小、可以指定包含collection的元素(利用该集合的迭代器按顺序返回其中的元素)，如果选择无参构造方法创建ArrayList时，虽然类中定义了默认大小10，实际上初始化赋值的是一个空数组，只有当真正向集合中添加元素时，才会真正的分配容量。即向集合添加第一个元素时，数组扩容至默认大小10。

何时扩容？

以无参构造函数创建的ArrayList为例进行分析，第一次扩容发生在添加第一个元素时，那么我们就先看看add(E e)中是如何进行的：

/**
 * 将指定的元素追加到此列表的末尾。 
 */
public boolean add(E e) {
    //添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}

添加元素之前先调用ensureCapacityInternal(size+1)：

//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取默认的容量和传入参数的较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

从add(E e)进来之后，minCapacity为1，在max()之后，变成了默认容量10。

之后调用ensureExplicitCapacity(minCapacity)方法：

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}

可以看到这是调用扩容方法grow()之前的最后一步，仔细分析一下：

• 此时minCapacity为10，而elementData.length为0(依然是最初的那个空数组)，所以10-0>0成立，执行grow()开始扩容。
• 为什么是minCapacity - elementData.length > 0？从add(E e)方法传参size+1，到max(默认容量，size+1)传递到这一步，拿到了添加元素之后数组的最小容量minCapacity，减去当前数组的容量elementData.length，结果>0即当前数组大小不足以添加新元素，进行扩容。

如何扩容？

扩容自然是从grow()方法开始：

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
    //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
    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. 先扩容至旧容量oldCapacity的 1.5 倍。

2. 如果不够就扩容至最小容量minCapacity。

3. 还要检查扩容后的新容量newCapacity是否超过最大数组容量MAX_VALUE-8。如果超过最大容量，则执行hugeCapacity方法：

   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       //对minCapacity和MAX_ARRAY_SIZE进行比较
       //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
       //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
       //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
       MAX_ARRAY_SIZE;
   }

   这个方法就是最后检查一下扩容后的最小容量minCapacity是否真的需要那么大的容量；

4. 最后将旧数组elementData复制到新容量newCapacity大小的新数组中，完成扩容。这一操作是调用Arrays.copyOf()完成的：

   public static int[] copyOf(int[] original, int newLength) {
       int[] copy = new int[newLength];
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
   }

   Arrays.copyOf()有各种类型参数的重载方法，其底层就是调用了System.arraycopy()这个 native 方法。在 ArrayList 中大量的调用Arrays.copyOf()和System.arraycopy()，其中前文说的添加/删除时元素移动操作就是借助System.arraycopy()方法实现的。

ensureCapacity()

ArraysList 中提供了一个用户方法ensureCapacity()：

/**
    如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由var1参数指定的元素数。
 *
 * @param   var1   所需的最小容量
 */
public void ensureCapacity(int var1) {
    int var2 = this.elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA ? 0 : 10;
    if (var1 > var2) {
        this.ensureExplicitCapacity(var1);
    }

}

private void ensureExplicitCapacity(int var1) {
    ++this.modCount;
    if (var1 - this.elementData.length > 0) {
        this.grow(var1);
    }

}

这个方法就是提供给用户主动进行容量检查的，如果此时 ArrayList 实例的数组容量小于传参var1则会进行扩容操作。

PS：在使用 ArrayList 时，如果要添加大量元素，最好先调用ensureCapacity()方法，从而减少 add 方法中重新分配容量的次数，这样会有效提升添加操作的执行速度。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github