Java List 常用集合 ArrayList、LinkedList、Vector

Java 中的 List 是非常常用的数据类型。List 是有序的 Collection，Java List 一共有三个实现类，分别是：ArrayList、Vector、LinkedList

本文分析基于 JDK8

ArrayList

ArrayList 继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化，初始容量为 10，允许值为 null，有序，非线程安全，擅长随机访问

ArrayList 还实现了 RandomAccess、Cloneable、Serializable 接口，所以 ArrayList 是支持快速访问、复制、序列化的

RandomAccess

标记接口，用来表明其支持快速随机访问。如果是实现了这个接口的 List，那么使用 for 循环的方式获取数据会优于用迭代器获取数据
Serializable

标记该类支持序列化
Cloneable

允许在堆中克隆出一块和原对象一样的对象，并将这个对象的地址赋予新的引用。ArrayList 提供的是一种深克隆机制，即克隆除自身对象以外的所有对象，包括自身所包含的所有对象实例。实现方式是先调用 super.clone() 方法克隆出一个新对象，然后再手动将原数组中的值复制到一个新的数组，并赋值

ArrayList 扩容机制

扩容机制应该是面试中最常问的了。其他关于 ArrayList 的一些琐碎方法我就不细说了，主要介绍一下扩容机制。首先了解一下 ArrayList 的成员属性

// 表示 ArrayList 的默认容量大小

private static final int DEFAULT_CAPACITY = 10;

// 一个空的 Object 数组对象，长度为 0，如果使用默认构造函数创建，则 elementData 默认是该值

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 最大容量

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// ArrayList 中存放的实际元素个数

private int size;

// 当前元素对象存放的数组，不参与序列化

transient Object[] elementData;

执行 add 方法时，会先执行 ensureCapacityInternal 方法，判断当前数组容量是否足够，不够就扩容。然后将待添加元素加到 elementData 末尾

public boolean add(E e) {

    ensureCapacityInternal(size + 1);

    elementData[size++] = e;

    return true;

}

private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

private static int calculateCapacity(Object[] elementData, int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

}

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // minCapacity > elementData.length 则扩容

    if (minCapacity - elementData.length > 0)

        grow(minCapacity);

}

再分析一下 ensureCapacityInternal 方法，此时 minCapacity 是 size + 1，这里有两个嵌套方法 calculateCapacity 和 ensureExplicitCapacity，作用分别如下：

calculateCapacity

如果当前数组为空，则先设置容量为默认值 10，此时还未初始化数组
ensureExplicitCapacity

确认实际的容量，如果不够就扩容，关键的扩容函数 grow 就在这里

扩展数组大小，首先将容量扩大为原来的 1.5 倍，如果数组是空数组，则将数组初始化，默认容量为 10，如果不是，再判断是否超出最大容量，超过直接赋予最大值，否则赋予新值，复制原数组到新数组

private void grow(int minCapacity) {

    // 扩容前的容量

    int oldCapacity = elementData.length;

    // oldCapacity 右移一位，等于除以二

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 扩容之后还是不够，直接赋予新值

    if (newCapacity - minCapacity < 0)

        newCapacity = minCapacity;

    // 扩容之后超出最大容量，直接赋予最大值

    if (newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    // 复制原数组的值到新数组

    elementData = Arrays.copyOf(elementData, newCapacity);

}

LinkedList

LinkedList 继承自 AbstractSequentialList，实现了 List 和 Deque 接口，基于双向链表实现，每个节点都包含了对前一个和后一个元素的引用，可以被当作堆栈、队列或双端队列进行操作，有序，非线程安全

// 指向链表的第一个节点

transient Node<E> first;

// 指向链表的最后一个节点

transient Node<E> last;

JDK8 中 LinkedList 有一个静态内部类 Node，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点

private static class Node<E> {

    E item;

    Node<E> next;

    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {

        this.item = element;

        this.next = next;

        this.prev = prev;

    }

}

除此之外就没啥好分析的了，LinkedList 不存在容量不足的问题，克隆函数也是将所有元素全都克隆到新的 LinkedList 对象

Vector

Vector 是一个矢量队列，和 ArrayList 类似，继承自 AbstractList，实现了 List 接口，就连额外接口也是一样。不同之处在于：

Vector 使用 synchronized 保证线程同步
Vector 中遗留了大量传统的方法，这些方法不属于集合框架

Vector 有四个构造方法

// 创建一个默认大小为 10 的向量

public Vector()

// 创建指定大小的向量

public Vector(int initialCapacity)

// 创建指定大小的向量，并且指定增量。增量表示向量每次增加的元素数目

public Vector(int initialCapacity, int capacityIncrement)

// 创建一个包含集合 c 元素的向量

public Vector(Collection<? extends E> c)

Vector 的数据结构和 ArrayList 差不多，它包含了三个成员变量：

// 存放元素的动态数组

protected Object[] elementData;

// 动态数组的实际大小

protected int elementCount;

// 动态数组的增长系数

protected int capacityIncrement;

随着 Vector 中元素的增加，Vector 的容量也会动态增长，capacityIncrement 是与容量增长相关的增长系数，具体增长细节在 grow 函数中，和 ArrayList 类似

private void grow(int minCapacity) {

    int oldCapacity = elementData.length;

    // 如果 capacityIncrement > 0，新的容量大小 = 旧的容量大小 + 增长系数

    // 否则容量扩大为原来的两倍

    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?

                                     capacityIncrement : oldCapacity);

    if (newCapacity - minCapacity < 0)

        newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    elementData = Arrays.copyOf(elementData, newCapacity);

}

Stack

Stack 是 Vector 的子类，实现了一个标准的后进先出的栈。Stack 也是通过数组实现的，当然了，我们也可以将 LinkedList 当作栈来使用

Stack 只定义了默认构造函数，用来创建一个空栈

public Stack()

Stack 除了具有 Vector 的所有 API，还有自己实现的方法

// 判断堆栈是否为空

public boolean empty()

// 查看堆栈顶部的对象，但不从堆栈中移除它

public synchronized E peek()

// 移除堆栈顶部的对象，并作为此函数的值返回该对象

public synchronized E pop()

// 把对象压入堆栈顶部

public E push(E item)

// 返回对象在堆栈中的位置，以 1 为基数

public synchronized int search(Object o)

Stack 的扩容机制基于 Vector，不过由于没有指定增长系数，所有默认为 0，每次扩容数组长度增大为原来的两倍

巴特西