Vector及LinkedList源码解析

1、本文主要内容

• Vector及LinkedList介绍
• Vector源码解析
• LinkedList源码解析
• 总结

java容器这个系列，虽然较为简单，但本着有始有终的原则，还是必须要写下去。同时感觉一篇只写一个容器，实在有点划水的嫌疑，因此本篇将写两个容器。

2、Vector及LinkedList介绍

Vector、LinkedList以及之前已经介绍的ArrayList属于队列里三个常见的容器。ArrayList是一个可扩容的数组，LinkedList则是以双向链表形式存储元素，而Vector也是一个可扩容数组，不过它是线程安全的。

一般来说，数组适用于随机读取多的场景，插入和删除则比较费劲，需要移动数组。而链表则插入和删除非常高效，读取则需要遍历，效率较低。

3、Vector源码解析

public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
 * The array buffer into which the components of the vector are
 * stored. The capacity of the vector is the length of this array buffer,
 * and is at least large enough to contain all the vector's elements.
 *
 * <p>Any array elements following the last element in the Vector are null.
 *
 * @serial
 */
//存放数组的数组
protected Object[] elementData;

/**
 * The number of valid components in this {@code Vector} object.
 * Components {@code elementData[0]} through
 * {@code elementData[elementCount-1]} are the actual items.
 *
 * @serial
 */
//已经存储数组的个数
protected int elementCount;

/**
 * The amount by which the capacity of the vector is automatically
 * incremented when its size becomes greater than its capacity.  If
 * the capacity increment is less than or equal to zero, the capacity
 * of the vector is doubled each time it needs to grow.
 *
 * @serial
 */
//当已存储数据的个数大于数组容量时，数组容量以capacityIncrement为单位自动增长，如果capacityIncrement值为0
//则数组容量则增加到两倍
protected int capacityIncrement;

/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = -2767605614048989439L;

/**
 * Constructs an empty vector with the specified initial capacity and
 * capacity increment.
 *
 * @param   initialCapacity     the initial capacity of the vector
 * @param   capacityIncrement   the amount by which the capacity is
 *                              increased when the vector overflows
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
//初始化函数
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

/**
 * Constructs an empty vector with the specified initial capacity and
 * with its capacity increment equal to zero.
 *
 * @param   initialCapacity   the initial capacity of the vector
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

/**
 * Constructs an empty vector so that its internal data array
 * has size {@code 10} and its standard capacity increment is
 * zero.
 */
//默认数组初始化长度为0，capacityIncrement增长级数为0
public Vector() {
    this(10);
}

//将vector数组复制到另一个数组当中
public synchronized void copyInto(Object[] anArray) {
    System.arraycopy(elementData, 0, anArray, 0, elementCount);
}

//整理数组的容量到当前长度，因为容量可能大于已存储数据的个数，如果大于就缩小数组长度，去掉不必要的内存占用
public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//数组容量增长，如果capacityIncrement大于0，则增长capacityIncrement，反之则数组容量变成现在的两倍
//最后将当前数组内容复制到新的数组
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);
}

//设置size，如果新size大于当前size，则要判断是否需要增长数组容量，如果小于，则newsize及其以后的索引位都要置空
public synchronized void setSize(int newSize) {
    modCount++;
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else {
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

//返回数组容量
public synchronized int capacity() {
    return elementData.length;
}

//返回已存储元素个数
public synchronized int size() {
    return elementCount;
}

//判断是否有存储元素
public synchronized boolean isEmpty() {
    return elementCount == 0;
}

//判断是否包含某个元素
public boolean contains(Object o) {
    return indexOf(o, 0) >= 0;
}

//求元素索引
public int indexOf(Object o) {
    return indexOf(o, 0);
}

//求元素索引的实现。
//如果元素为null，遍历查看数组中哪个元素为空即可
//如果元素不为空，则需要调用equals方法查询，只有equals返回为true才相等
//所以一些自定义对象中，要想在容器中找到此对象 ，一定要重写equals
public synchronized int indexOf(Object o, int index) {
    if (o == null) {
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//从数组后面寻找索引
public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

//从数组后面寻找索引
public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//求索引位置上的元素
public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}

//返回数组中的第一个元素
public synchronized E firstElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(0);
}

//返回数组中的最后一个元素
public synchronized E lastElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(elementCount - 1);
}

//设置某个索引上的元素
public synchronized void setElementAt(E obj, int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    elementData[index] = obj;
}

//删除索引位上的元素
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j代表此索引位后面还有几个元素
    int j = elementCount - index - 1;
    if (j > 0) {
        //如果j大于0，需要把索引位后面的元素整体向前挪一位，即复制即可，调用System.arraycopy方法
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    //将索引位上的元素置为空，让系统去回收内存
    elementData[elementCount] = null; /* to let gc do its work */
}

//在某个索引位置上插入元素，同样需要确保数组容量足够，并且数组要后移一位，通过复制数组实现
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

//在数组的后边添加一个元素
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

//删除一个特定的元素，先找到此元素的索引，再删除此索引上的元素
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

//删除所有元素
public synchronized void removeAllElements() {
    modCount++;
    // Let gc do its work
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

//克隆
public synchronized Object clone() {
    try {
        @SuppressWarnings("unchecked")
            Vector<E> v = (Vector<E>) super.clone();
        v.elementData = Arrays.copyOf(elementData, elementCount);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}


public synchronized Object[] toArray() {
    return Arrays.copyOf(elementData, elementCount);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

//返回索引位上的元素
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

//设置某索引位上的元素，赋值即可
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

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

//在数组末尾添加元素
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

//删除元素
public boolean remove(Object o) {
    return removeElement(o);
}


public void add(int index, E element) {
    insertElementAt(element, index);
}


public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}


public void clear() {
    removeAllElements();
}

public synchronized boolean containsAll(Collection<?> c) {
    return super.containsAll(c);
}

public synchronized boolean addAll(Collection<? extends E> c) {
    modCount++;
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);
    System.arraycopy(a, 0, elementData, elementCount, numNew);
    elementCount += numNew;
    return numNew != 0;
}


public synchronized boolean removeAll(Collection<?> c) {
    return super.removeAll(c);
}
}

4、LinkedList源码解析

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//LinkedList的大小
transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
//头节点
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
//最后一个节点
transient Node<E> last;

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

/**
 * Links e as first element.
 */
//添加一个新节点作为头节点
//Node的构造函数，第1个参数是pre指针，最后一个参数是next指针
//新节点将next指针指向之前的first节点，然后自己成为新的first节点
//最后将之前的first节点的pre指向自己。
//也要考虑链表为空的情况，那么新节点也是last节点了
private void linkFirst(E e) {
    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;
    //链表大小加1
    size++;
    modCount++;
}

/**
 * Links e as last element.
 */
//添加一个新节点作为last节点
//同样的，新节点先将pre指向指向last节点，再自己成为新的last节点
//最后将之前的last节点的pre指针指向自己
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++;
}

/**
 * Inserts element e before non-null Node succ.
 */
//在指定的节点前添加一个新节点
//新节点的pre指针指向指定节点的pre指针，next指向指定节点
//最后处理指定节点的pre节点，指定节点自己的指针
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++;
}

/**
 * Unlinks non-null first node f.
 */
//删除头节点，这个方法传入的f即是头节点，它是私有方法，查看后面代码，参数都为头节点
//清空自己，同时处理头节点的next指针即可
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

/**
 * Unlinks non-null last node l.
 */
//删除尾节点，同上
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

/**
 * 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;
}

//获取first节点的元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//获取尾节点元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

//删除头节点，具体实现前文已经说了
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

//删除尾节点，实现前面也已经解释了
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

//添加一个元素到头节点处
public void addFirst(E e) {
    linkFirst(e);
}

//添加一个元素到尾节点处
public void addLast(E e) {
    linkLast(e);
}

//是否包含某元素，求其索引，如果索引不为-1，则包含
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

//求链表大小
public int size() {
    return size;
}

//添加一个元素，如果使用add方法，则默认添加在尾节点处
public boolean add(E e) {
    linkLast(e);
    return true;
}

//删除指定元素，LinkedList也可以存放空元素
//遍历链表，从头节点开始遍历，一直到最后，也是调用eqauls方法，如果相等则删除此节点
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;
}


public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

//在指定索引上添加一个集合内的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    //先查检索引，索引不能小于0，也不能大于size
    checkPositionIndex(index);
    //将集合先转变成一个数组，并获取数组的长度，如果长度等于0，则返回
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //事先定义两个临时变量，succ代表当前索引位置上的节点，pre代表succ的pre节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        //获取指定索引位置上的节点succ和其pre节点
        succ = node(index);
        pred = succ.prev;
    }
    //新元素要添加在指定的索引位置上，所以需要断开succ和pred现在的关系，只要pred的next指向新节点，并且新节点的pre指向pred即可
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //构造新节点，新节点的pre指向pred
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            //同时pred的next指向新节点
            pred.next = newNode;
        //最后将pred向前移一们，设定pred指向新节点
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        //for循环以后，pred代表的是新加入链表的最后一个节点，所以将它的next指向原先的succ
        //同时处理succ的prev节点
        pred.next = succ;
        succ.prev = pred;
    }
    //size自增numNew
    size += numNew;
    modCount++;
    return true;
}

//清除链表，遍历并且置所有元素为null
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}


// Positional Access Operations

//获取指定索引处的节点的value值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

//设置指定索引处节点的value，node方法在后边有说明
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

//在指定索引处添加一个元素，如果索引等于size，则添加新元素到尾节点，反之则在指定索引之前添加一个新节点
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

//删除指定索引的节点，unlink方法和node方法都有说明
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}


private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

//求取在指定索引上的节点
//方法采用了类似二分查找的方法，如果索引值小于size的一半，则从头节点开始寻找，反之则从尾节点开始寻找
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;
    }
}

// Search Operations

//遍历查找某个元素的索引，元素可以为null
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

//从尾节点开始查找某元素的索引值
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

// Queue operations.

//获取头节点的value值
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

//获取头节点value值
public E element() {
    return getFirst();
}

//删除头节点，并且返回头节点的value值
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

//删除，默认删除的是头节点并且返回头节点的value值
public E remove() {
    return removeFirst();
}

//添加新元素，默认添加到尾节点，add方法前文有描述
public boolean offer(E e) {
    return add(e);
}

//在头节点处添加新元素
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

//在尾节点处添加新元素
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

//获取头节点的value值
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

//获取尾节点的value值
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

//删除头节点并且返回头节点的value值
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

//删除尾节点并且返回头节点的value值
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

//在头节点处添加新元素
public void push(E e) {
    addFirst(e);
}

//删除头节点并返回头节点value值
public E pop() {
    return removeFirst();
}

//删除指定的元素
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}


private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    //注意Node的构造方法的参数顺序，第一个是pre，中间是value，后一个是next
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
}

5、总结

关于List相关的容器已经走读完了，都比较简单，只要肯阅读源码，很多的东西都会变得非常容易。