List

前言

声明，本文用得是jdk1.8

前一篇已经讲了Collection的总览：Collection总览，介绍了一些基础知识。
现在这篇主要讲List集合的三个子类：

• ArrayList ： 底层数据结构是数组。线程不安全
• LinkedList ： 底层数据结构是链表。线程不安全
• Vector : 底层数据结构是数组。线程安全

1. ArrayList 解析

来看一下ArrayList的属性：

根据上面我们可以清晰的发现：ArrayList底层其实就是一个数组，ArrayList中有扩容这么一个概念，正因为它扩容，所以它能够实现“动态”增长

1.2 构造方法

我们来看看构造方法来印证我们上面说得对不对：

    /**
     * 构造具有指定初始容量的空列表.
     *
     * @param  初始容量列表的初始容量
     * @throws 如果指定的初始容量为负，则为IllegalArgumentException
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }

    /**
     * 构造初始容量为10的空列表
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /**
     * 构造包含指定集合的元素的列表，按集合的迭代器返回这些元素的顺序。
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    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;
        }
    }

1.3 Add 方法

add方法可以说是ArrayList比较重要的方法了，我们来总览一下：

    /**
     * 将指定的元素追加到此列表的末尾
     *
     * @param e 要附加到此列表的元素
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 插入元素
        elementData[size++] = e;
        return true;
    }

    /**
     * 在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）
     *
     * @param index 要插入指定元素的索引
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // 增量modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

1.3.1 add(E e)

该方法很短，可以从方法名猜到干了什么：

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

1. 确认list容量，尝试容量加1，看看有无必要
2. 添加元素

接下来看一下 * ensureCapacityInternal* 方法

    private void ensureCapacityInternal(int minCapacity) {
        //存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，elementData== DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的任何空ArrayList都将扩展为DEFAULT_CAPACITY。
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

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

        // 如果要的最小容量比数组的长度要大，要么就调用 grow() 来扩容
        //(例如：当添加第11个元素时，minCapacity 为 11，数组长度为10，那么就要扩容了)
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

所以，接下来看看grow()是怎么实现的

    /**
     * 增加容量以确保它至少可以容纳由最小容量参数指定的元素数。
     *
     * @param minCapacity 所需的最小容量
     */
    private void grow(int minCapacity) {
        // oldCapacity 旧数组的长度
        int oldCapacity = elementData.length;
        // 扩容 1.5 倍
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

进去看 copyOf() 方法：

    /**
     * 复制指定的数组，截断或填充空值（如果需要），使副本具有指定的长度。对于在原始数组和副本中都有效的所有索引，这两个数
     * 组将包含相同的值。对于在副本中有效但不是原始索引的任何索
     * 引，副本将包含 null。
     * 当且仅当指定长度大于原始数组时，这些索引将存在。
     * 生成的数组属于新类型。
     *
     * @param <U> the class of the objects in the original array
     * @param <T> the class of the objects in the returned array
     * @param original the array to be copied
     * @param newLength the length of the copy to be returned
     * @param newType the class of the copy to be returned
     * @return a copy of the original array, truncated or padded with nulls
     *     to obtain the specified length
     * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
     * @throws NullPointerException if <tt>original</tt> is null
     * @throws ArrayStoreException if an element copied from
     *     <tt>original</tt> is not of a runtime type that can be stored in
     *     an array of class <tt>newType</tt>
     * @since 1.6
     */
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

总结 add(E e) :

• 首先去检查一下数组的容量是否足够
• 扩容到原来的1.5倍
• 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity
• 足够：直接添加
• 不足够：扩容

1.3.2 add(int index, E element)

步骤：

• 检查角标
• 空间检查，如果有需要进行扩容
• 插入元素

先看代码：

    /**
     * 在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）
     *
     * @param index 要插入指定元素的索引
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        // 检查角标是否越界
        rangeCheckForAdd(index);

        // 扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 调用 System.arraycopy 来进行插入
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

我们发现，与扩容相关 ArrayList 的 add 方法底层其实都是 arraycopy() 来实现的

看到 arraycopy()，我们可以发现：该方法是由 C/C++ 来编写的，并不是由 Java 实现：

public static native void arraycopy(@NonNull Object var0, int var1, @RecentlyNonNull Object var2, int var3, int var4);

总的来说：arraycopy()还是比较可靠高效的一个方法。
参考R大回答：https://www.zhihu.com/question/53749473

1.4 get 方法

步骤

• 检查角标
• 返回元素

来看代码：

    /**
     * 获取列表中指定位置的元素.
     *
     * @param  index 要返回的元素的索引
     * @return 返回此列表中指定位置的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        // 检查角标
        rangeCheck(index);

        // 返回具体元素
        return elementData(index);
    }

接着看看 rangeCheck() 和 * elementData()* 方法的代码：

   // 检查角标
   private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    // 返回元素
    E elementData(int index) {
        return (E) elementData[index];
    }

1.5 set 方法

步骤：

• 检查角标
• 替代元素
• 返回旧值

接着看代码：

    /**
     * 用指定的元素替换此列表中指定位置的元素
     *
     * @param index 要替换的元素的索引
     * @param element 要存储在指定位置的元素
     * @return 以前位于指定位置的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

1.6 remove 方法

步骤

• 检查角标
• 删除元素
• 计算出需要移动的个数，并移动
• 设置为null，让Gc回收

看代码：

    /**
     * 删除此列表中指定位置的元素.
     * 将任何后续元素向左移动（从其索引中减去一个).
     *
     * @param index 要删除的元素的索引
     * @return 从列表中删除的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        // 需要左移动的个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

1.7 总结 ArrayList

• ArrayList 是基于动态数组实现的，在增删时候，需要数组的拷贝复制。
• ArrayList 的默认初始化容量是 10，每次扩容时候增加原先容量的一半，也就是变为原来的 1.5 倍
• 删除元素时不会减少容量，若希望减少容量则调用 trimToSize()
• 它不是线程安全的。它能存放 null 值。

2 Vector 与 ArrayList 区别

Vector是jdk1.2的类了，比较老旧的一个集合类

Vector底层也是数组，与ArrayList最大的区别就是：同步(线程安全)

Vector是同步的，我们可以从方法上就可以看得出来

在要求非同步的情况下，我们一般都是使用 ArrayList 来替代 Vector 的了

如果想要 ArrayList 实现同步，可以使用 Collections 的方法：List list = Collections.synchronizedList(new ArrayList(...));，就可以实现同步了

还有另一个区别：
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

Vector源码的解析可参考：

• https://blog.csdn.net/panweiwei1994/article/details/76972890
• https://zhuanlan.zhihu.com/p/28241176

3 LinkedList 解析

LinkedList底层是双向链表，而且是内部类

从结构上，我们还看到了 LinkedList 实现了 Deque 接口，因此，我们可以操作 LinkedList 像操作队列和栈一样

3.1 构造方法

LinkedList的构造方法有两个：

    /**
     * 构造空列表
     */
    public LinkedList() {
    }

    /**
     * 构造包含指定集合的元素的列表，按集合的迭代器返回这些元素的顺序。
     *
     * @param  c 要将其元素放入此列表中的集合
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

3.2 add 方法

add方法实际上就是往链表最后添加元素：

    /**
     * 在列表的开头插入指定的元素.
     *
     * @param e 要插入的元素
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        //first 指向第一个节点的指针
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

3.3 remove 方法

先看代码：

    /**
     * 从列表中删除指定元素的第一个匹配项（如果存在）。如果此列
     *表不包含元素，则它将保持不变。更正式地说，删除索引最低的元素
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);// 删除元素
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

再看 unlink 方法

    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

实际上就是下面那个图的操作：

3.4 get 方法

可以看到get方法实现就两段代码：

    /**
     * 返回此列表中指定位置的元素.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

看一下 node 方法的相关代码：

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        // 下角标小于长度一半，那就从头开始遍历
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; I++)
                x = x.next;
            return x;
        } else {
            //否则从尾部开始遍历
            Node<E> x = last;
            for (int i = size - 1; i > index; I--)
                x = x.prev;
            return x;
        }
    }

3.5 set 方法

set方法和get方法其实差不多，根据下标来判断是从头遍历还是从尾遍历

    /**
     * 用指定的元素替换此列表中指定位置的元素
     * 
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

LinkedList的方法比ArrayList的方法多太多了，具体可参考：

https://blog.csdn.net/panweiwei1994/article/details/77110354
https://zhuanlan.zhihu.com/p/24730576
https://zhuanlan.zhihu.com/p/28373321

4 总结

其实集合的源码看起来并不是很困难，遇到问题可以翻一翻，应该是能够看懂的~

ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结：

ArrayList

• 底层实现是数组
• ArrayList 的默认初始化容量是 10，每次扩容的时候增加原来容量的一半，也就是变为原来的 1.5 倍
• 在 增删的时候，需要数组的拷贝复制（native 方法由 C/C++ 实现）

LinkedList

• 底层实现是双向链表[双向链表方便实现往前遍历]

Vector

• 底层是数组，现在已少用，被 ArrayLis t替代，原因有两个：
  1. Vector 所有方法都是同步，有性能损失
  2. Vector初始 length 是 10 超过 length 时 以 100% 比率增长，相比于 ArrayList 更多消耗内存

总的来说：查询多用 ArrayList，增删多用 LinkedList。

ArrayList 增删慢不是绝对的(在数量大的情况下，已测试)：

• 如果增加元素一直是使用 add() (增加到末尾)的话，那是 ArrayList要快
• 一直删除末尾的元素也是 ArrayList 要快【不用复制移动位置】
  至于如果删除的是中间的位置的话，还是 ArrayList 要快！
  但一般来说：增删多还是用 LinkedList，因为上面的情况是极端的

参考资料：

• https://blog.csdn.net/panweiwei1994/article/details/76555359
• https://zhuanlan.zhihu.com/p/28216267
• 《Core Java》

申明：开始和结束的图片来源网络，侵删