Java 容器源码分析之Map-Set-List（17）

look_w

调整数组容量从上面介绍的向 ArrayList 中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容有两个方法，其中开发者可以通过一个 public 的方法ensureCapacity(int minCapacity)来增加 ArrayList 的容量，而在存储元素等操作过程中，如果遇到容量不足，会调用priavte方法private void ensureCapacityInternal(int minCapacity)实现。
[url=][/url]
    public void ensureCapacity(int minCapacity) {        if (minCapacity > 0)            ensureCapacityInternal(minCapacity);    }    private void ensureCapacityInternal(int minCapacity) {        modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }    /**     * 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:        elementData = Arrays.copyOf(elementData, newCapacity);    }[url=][/url]

从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的 1.5 倍（从int newCapacity = oldCapacity + (oldCapacity >> 1)这行代码得出）。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity 方法来手动增加 ArrayList 实例的容量。
Fail-Fast 机制ArrayList 也采用了快速失败的机制，通过记录 modCount 参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 关于 Fail-Fast 的更详细的介绍，我在之前将 HashMap 中已经提到。
LinkedList 的实现原理概述LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比 ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比 ArrayList 差。
看一下 LinkedList 的类的定义：
public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
LinkedList 继承自 AbstractSequenceList，实现了 List、Deque、Cloneable、java.io.Serializable 接口。AbstractSequenceList 提供了List接口骨干性的实现以减少实现 List 接口的复杂度，Deque 接口定义了双端队列的操作。
在 LinkedList 中除了本身自己的方法外，还提供了一些可以使其作为栈、队列或者双端队列的方法。这些方法可能彼此之间只是名字不同，以使得这些名字在特定的环境中显得更加合适。
LinkedList 也是 fail-fast 的（前边提过很多次了）。
LinkedList 源码解读数据结构LinkedList 是基于链表结构实现，所以在类中包含了 first 和 last 两个指针(Node)。Node 中包含了上一个节点和下一个节点的引用，这样就构成了双向的链表。每个 Node 只能知道自己的前一个节点和后一个节点，但对于链表来说，这已经足够了。
[url=][/url]
transient int size = 0;    transient Node<E> first; //链表的头指针    transient Node<E> last; //尾指针    //存储对象的结构 Node, LinkedList的内部类    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;        }    }[url=][/url]

存储add(E e)该方法是在链表的 end 添加元素，其调用了自己的方法 linkLast(E e)。
该方法首先将 last 的 Node 引用指向了一个新的 Node(l)，然后根据l新建了一个 newNode，其中的元素就为要添加的 e；而后，我们让 last 指向了 newNode。接下来是自身进行维护该链表。
[url=][/url]
/**     * 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;}/*** 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++;}[url=][/url]

add(int index, E element)该方法是在指定 index 位置插入元素。如果 index 位置正好等于 size，则调用 linkLast(element) 将其插入末尾；否则调用 linkBefore(element, node(index))方法进行插入。该方法的实现在下面，大家可以自己仔细的分析一下。（分析链表的时候最好能够边画图边分析）
[url=][/url]
/**    * Inserts the specified element at the specified position in this list.    * Shifts the element currently at that position (if any) and any    * subsequent elements to the right (adds one to their indices).    *    * @param index index at which the specified element is to be inserted    * @param element element to be inserted    * @throws IndexOutOfBoundsException {@inheritDoc}    */   public void add(int index, E element) {       checkPositionIndex(index);       if (index == size)           linkLast(element);       else           linkBefore(element, node(index));   }   /**        * Inserts element e before non-null Node succ.        */       void linkBefore(E e, Node<E> succ) {           // assert succ != null;           final Node<E> pred = succ.prev;           final Node<E> newNode = new Node<>(pred, e, succ);           succ.prev = newNode;           if (pred == null)               first = newNode;           else               pred.next = newNode;           size++;           modCount++;       }