Java集合--List及其实现类

List集合存放的元素是有序，可重复的。
文档定义如下：

public interface List<E> extends Collection<E> {}

List继承了Collection<E>接口，由于集合中存放的都是对象，因此List对象在add操作的时候可以add(null)。

---

这里主要介绍List的三个实现类ArrayList、LinkedList、Vector。
先给出它们三个的定义：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

从它们各自的定义我们能发现ArrayList和Vector都实现了List<E>接口，这也是我们平时总是定义列表的时候习惯写List<E> list = new ArrayList<>();同时，我们还发现二者都实现了RandomAccess接口，而LinkedList没有实现RandomAccess接口，RandomAccess接口的目的就是告诉我们，实现了该接口的类支持高速随机访问。（当查阅RandomAccess定义的时候，我们发现RandomAccess只是定义了一下，内部并没有任何的方法，我猜这里可能就是为了标识一下吧，标识 -- 实现了该接口的类都支持高速随机访问[当然最可靠的办法还是看源码]）
从另一角度还可以分析ArrayList和Vector支持高速随机访问，而LinkedList不支持。ArrayList和Vector底层是通过数组实现，LinkedList底层是通过双向链表实现。我们知道数组的优点是读取方便，即可以通过索引直接读取值，而链表的读取需要从前向后依次查找，但是链表的删除和插入方便。因此这里最能解释为什么ArrayList和Vector支持高速随机访问，而LinkedList不支持。

ArrayList和Vector的区别是什么呢？
ArrayList中方法都没有做同步，因此ArrayList是线程不安全的；Vector中方法基本都做了同步，因此是线程安全的。我们知道同步是高损耗的，平时尽可能的不去使用同步，除非业务需要，比如转账操作。这也能解释我们平时定义列表的时候为啥总是习惯写List<E> list = new ArrayList<>();首先没有同步机制，低耗；另一个平时大多数情况下都是读操作居多。

下面以列表的add方法为例，查看一下源码，拿ArrayList和LinkedList对比分析：（ArrayList和Vector在源码中区别就在于有没有关键字synChronized，这里就不分析了）

ArrayList中的add()方法

   /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        //1、判断数组容量是否够用 2、赋值 3、return
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

继续看ensureCapacityInternal()的源码：

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //主要是ensureExplicitCapacity方法
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//这个modCount变量的作用是计数，记录修改次数（发现：变量modCount经常出现在线程不安全的方法中）

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

再继续看grow方法：

   /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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:
        //我们看到这里使用了数组的复制方法，进而实现列表的add方法
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList中的add方法

   /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

继续看linkLast方法：

   /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

继续看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因为使用了双向链表，插入和删除都很方便。

转载于:https://www.jianshu.com/p/56f3567ef910