传送门：Java（Android）数据结构汇总 -- 总纲

简介

Collection接口下面有三个扩展接口：List、Set和Queue。它们在Collection的基础上增加了一些用来实现自己特性的一些方法。

List：可存放重复元素
Set：不可以存放重复元素
Queue：则实现了队列（FIFO）相关的功能

List接口的实现类

这篇文章我们先来整理在java.util包下基于List接口实现的数据结构类，主要有ArrayList、LinkedList、Vector、Stack四个。

一、ArrayList

ArrayList可以说是java中最常用也是我们接触最早的一种数据结构了。它内部是用数组实现的。数组的优点是存储和随机访问效率最高，而缺点有以下两个：

1. 数组长度是固定的，无法动态扩容；
2. 如果在数组中间插入/删除元素，则需要手动将该位置之后的元素进行集体后移/前移。

ArrayList的主要功能就是为了解决这两个缺点，对涉及到的操作进行了封装，实现了自动化。使其在使用上比数组更加简单灵活。

实现原理

举个例子，某个ArrayList对象内部数组的长度为10且已装满，这时如果在第5个位置添加一个元素，则步骤如下：

1. 在内存中新建一个长度为15（每次扩容是增加原来容量的一半）的新数组；
2. 将原来数组中的所有元素复制到新数组中；
3. 将新数组中第5个位置到第10个位置的元素复制到第6个位置到第11个位置上（集体后移一个位置）；
4. 将第5个位置的值修改为新添加的值。

我们来看看源码（再次提醒：本文所有源码都是基于java1.8版本（Android API 27））：

public void add(int index, E element) {      
    // index是要插入的位置，size是当前元素的数量
    // index < 0：很简单，数组的下标是不能为负数的
    // index > size：表明数组中的元素必须挨着存放，不能有间隔
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    // size是当前存储的元素数量
    // ensureCapacityInternal方法用来确保当前数组大小不能小于size + 1，如果小于这个值就进行扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!

    // 将插入位置和之后的元素都集体后移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);

    // 在指定位置插入新元素
    elementData[index] = element;
    size++;
}
...
private void ensureCapacityInternal(int minCapacity) {
    // elementData就是ArrayList内部实现的数组
    // 检查数组是否是空数组，当新建ArrayList时如果没有指定容量，则elementData将是一个0长度的数组，
    // 当第一次添加元素的时候才真正为数组分配空间
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 确保数组的容量不能小于最小值DEFAULT_CAPACITY
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

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

    //  如果需要的最小容量比当前数组容量大，说明数组容量不够用了，则进行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
...
private void grow(int minCapacity) 
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新的容量为当前容量的1.5倍（oldCapacity >> 1等价于oldCapacity除2）
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 一些边界检查
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // 新建一个newCapacity长度的数组，并将elementData里面的元素复制到新数组中，
    // 最后将返回的新数组重新赋值给elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上面就是ArrayList的核心实现了。主要是对数组的操作进行了封装，让我们在使用上变的简单。

由于数组需要的一个连续的内存空间，所以在内存的利用率上不是很高。

因为随着内存中对象的不停创建和释放，会导致大量的内存碎片（不连续的内存空间），比如GC的标记-清除算法就会让这个问题特别明显，虽然GC还有其他算法可以减少了内存碎片，但却无法杜绝。

对于那些容量比ArrayList中数组需要的容量小的内存碎片就无法被ArrayList使用。而如果当此时没有其他足够的可用空间时就会出现OOM，但其实此时的可用内存容量的总和是大于需求内存容量的。

二、LinkedList

LinkedList内部使用的双向链表来实现的。链表的最大特点就是添加/删除元素很快。只需要修改前后节点的节点指针（引用）即可，不需要像数组那样还需要移动元素。

相关源码如下：

public void add(int index, E element) {
    // 边界检查
    checkPositionIndex(index);

    if (index == size)
        // 将元素添加到链表结尾
        linkLast(element);
    else
        // 将元素添加到链表中间，node(index)的作用是查找index位置的节点元素
        linkBefore(element, node(index));
}
...
void linkLast(E e) {
    // first记录的是链表当前的第一个节点
    // last记录的是链表当前的最后一个节点
    final Node<E> l = last;
    // 将要添加的元素封装成一个Node对象，并在构造方法里面将prev指向last且next设置为null，
    // 表示让自己作为链表的最后一个元素
    final Node<E> newNode = new Node<>(l, e, null);
    // 将last重新指向这个新增的节点
    last = newNode;

    if (l == null)
        // 如果当前链表是一个空的（还没有元素），则该节点直接作为第一个节点
        first = newNode;
    else
       // 让开始的最后一个节点指向该节点
        l.next = newNode;

    size++;
    modCount++;
}
...
Node<E> node(int index) {
    // 判断index是否超过总大小的一半，没有超过则从前面开始遍历，否则从后面开始遍历，主要是为了减少遍历次数
    if (index < (size >> 1)) {
        // 从链表头部开始遍历，找到index位置的节点
        Node<E> x = first;
        for (int i = 0; i < index; i++)
             x = x.next;
        return x;
    } else {
        // 从链表结尾开始遍历，找到index位置的节点
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
...
// 将e元素插入到succ节点的前面
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    // 将e封装成一个Node，它的prev指向succ的前一个节点，它的next指向succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改succ的前节点指向：将succ的prev指向这个新的节点
    succ.prev = newNode;
 
    // 修改pred节点的next指向
    if (pred == null)
        // 如果pred为空，表示新元素是插入到链表头部的，则直接使用first指向这个新节点
        first = newNode;
    else
        // 修改pred的后节点指向：将pred的next 指向这个新的节点
        pred.next = newNode;

    size++;
    modCount++;
}

可见，插入元素时只修改了和该位置相邻的节点，重新修改了它们的prev和next指向，其他节点没有任何改动，所以这点比ArrayList要快。

由于LinkedList的每个元素都需要一个额外的节点对象来进行包装，所以在内存的占用上要大一些：需要额外的空间来存储这个对象。

总结

将ArrayList和LinkedList做一个对比来看下它们各自的特点和性能。

特点：

除了上述特点之外，他们还有个特点就是：LinkedList占用的内存会随着元素的增多而增多，也会随着元素的减少也减少。但是ArrayList只会随着元素的增多而增多，不会随着元素的减少而减少。也就是说ArrayList的占用的空间只会增大，不会降低（数组只进行了扩容，没有进行收缩）。

方法性能：

当ArrayList不需要扩容的时候，它的add(e)方法比LinkedList的块，否则就会慢于LinkedList（扩容会涉及到新建数组、元素复制等）。
当add(index, e)和remove(index)操作的是最后一个位置时（不需要扩容时），ArrayList比LinkedList快。

三、Vector

Vector结构和ArrayList基本一致，区别是Vector的方法都实现了同步，所以Vector是线程安全的。

public synchronized E lastElement() {
    ...
}
...
public synchronized E firstElement() {
    ...
}
...
public synchronized E elementAt(int index) {
    ...
}
...
 public synchronized int indexOf(Object o, int index) 
    ...
}
...
public synchronized void setElementAt(E obj, int index) {
    ...
}
...
public synchronized void removeElementAt(int index) {
    ...
}
...
public synchronized void insertElementAt(E obj, int index) {
    ...
}
...

可以看到，那些涉及到访问内部数组的方法都加上了synchronized关键之来实现了同步。但同步必然会带来性能上的开销，所以Vector在性能上比ArrayList要差一些。

四、Stack

Stack（栈）继承至Vector，所以它有Vector的所有优缺点。栈的特点就是后进先出（LIFO），所以它新增了栈操作的相关接口，代码如下：

// 在栈顶添加一个元素
public E push(E item) {
    addElement(item);

    return item;
}
  
// 弹出栈顶元素
public synchronized E pop() {
    E obj;
    int len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

// 查看栈顶元素（注意：该元素不会出栈）
public synchronized E peek() {
    int len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

// 判断栈是否为空
public boolean empty() {
    return size() == 0;
}

// 在栈里查找指定元素的位置索引
public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

Stack的代码非常少，就上面这么点，主要是添加了栈相关的操作方法。

《算法》里面建议是不要使用Stack类来作为栈。因为Stack的API是宽接口API，也就是除了栈的相关操作（push、pop、peek）外它还有队列的相关操作（如get和set等对非栈顶操作的方法），如果使用不当容易破坏栈结构。这些额外操作看起来可能很有用，但他们其实是累赘。而且对于栈这种修改多查询少的特性，我们使用链表来实现性能会更好。

结语

关于List接口的数据结构类基本就这些了，只要大家明白了它们各自的实现原理也就知道了它们各自的区别和适合的使用场景。