Java基础集合（二）List详解

本文介绍: Java基础集合（二）List详解：ArrayList、LinkedList、Vector和Stack。

List 接口直接继承 Collection 接口，它定义为可以存储重复元素的集合，并且元素按照插入顺序有序排列，且可以通过索引访问指定位置的元素。常见的实现有：ArrayList、LinkedList、Vector和Stack

// 查找元素 o 第一次出现的索引位置
public int indexOf(Object o)
// 查找元素 o 最后一次出现的索引位置
public int lastIndexOf(Object o)
//···

AbstractSequentialList 抽象类继承了 AbstractList，在原基础上限制了访问元素的顺序只能够按照顺序访问，而不支持随机访问，如果需要满足随机访问的特性，则继承 AbstractList。子类 LinkedList 使用链表实现，所以仅能支持顺序访问，顾继承了 AbstractSequentialList而不是 AbstractList。

Vector 在现在已经是一种过时的集合了，包括继承它的 Stack 集合也如此，它们被淘汰的原因都是因为性能低下。

原因是JDK 1.0 时代，ArrayList 还没诞生，大家都是使用 Vector 集合，但由于 Vector 的每个操作都被 synchronized 关键字修饰，即使在线程安全的情况下，仍然进行无意义的加锁与释放锁，造成额外的性能开销，做了无用功。在 JDK 1.2 时，Collection 家族出现了，它提供了大量高性能、适用於不同场合的集合，而 Vector 也是其中一员，但由于 Vector 在每个方法上都加了锁，由于需要兼容许多老的项目，很难在此基础上优化Vector了，所以渐渐地也就被历史淘汰了。

现在，在线程安全的情况下，不需要选用 Vector 集合，取而代之的是 ArrayList 集合；在并发环境下，出现了 CopyOnWriteArrayList，Vector 完全被弃用了。

Stack是一种后入先出（LIFO）型的集合容器，如图中所示，大雄是最后一个进入容器的，top指针指向大雄，那么弹出元素时，大雄也是第一个被弹出去的。

取而代之的是后起之秀 Deque接口，其实现有 ArrayDeque，该数据结构更加完善、可靠性更好，依靠队列也可以实现LIFO的栈操作，所以优先选择 ArrayDeque 实现栈。

ArrayDeque 的数据结构是：数组，并提供头尾指针下标对数组元素进行操作。

ArrayList 以数组作为存储结构，它是线程不安全的集合；具有查询快、在数组中间或头部增删慢的特点，所以它除了线程不安全这一点，其余可以替代Vector，而且线程安全的 ArrayList 可以使用 CopyOnWriteArrayList代替 Vector。

// new ArrayList 时的默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 计算该容器应该满足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

LinkedList 底层采用双向链表数据结构存储元素，由于链表的内存地址非连续，所以它不具备随机访问的特点，但由于它利用指针连接各个元素，所以插入、删除元素只需要操作指针，不需要移动元素，故具有增删快、查询慢的特点。它也是一个非线程安全的集合。

由于以双向链表作为数据结构，它是线程不安全的集合；存储的每个节点称为一个Node，下图可以看到 Node 中保存了next和prev指针，item是该节点的值。在插入和删除时，时间复杂度都保持为 O(1)

LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) { // 查找的下标处于链表前半部分则从头找
        x = this.first;
        for(i = 0; i < index; ++i) { x = x.next; }
        return x;
    } else { // 查找的下标处于数组的后半部分则从尾开始找
        x = this.last;
        for(i = this.size - 1; i > index; --i) { x = x.prev; }
        return x;
    }
}