LinkedList源码分析

Java版本：

java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

LinkedList由双向链表实现。
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;

//核心数据结构代码：
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 ;
    }
}

通过定义的内部类，包括三个成员变量，数据对象，前一个节点对象，以及后一个节点对象。

add()/get()/remove()方法举例：

/**
 * 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.
 * 首先获得最后一个元素，新建一个节点newNode，
 * 如果最后一个元素为空，则将newNode赋值给first
 * 否则将newNode赋值给最后一个元素的next
 */
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++;
}


/**
 * Returns the element at the specified position in this list.
 * 
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * 检查index合法性，调用node方法
 */
public E get( int index ) {
    checkElementIndex(index);
    return node(index).item ;
}

/**
 * Returns the (non -null) Node at the specified element index.
 * 采用二分，如果index小于size >> 1(size/2),那么将从第一个元素开始往前推
 * 否则，从最后一个元素往后推
 */
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 ;
    }
}

/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * 检查index合法性，根据index获得对应的Node元素作为参数，调用unlink方法
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Unlinks non -null node x.
 * 获得Node对象的element，前一个节点prev及后一个节点next
 * 处理x的prev节点：
 * 如果移除的元素为首元素(即prev为null)，那么直接将节点next赋给first
 * 否则，将next赋值给prev.next，并将x.prev置空
 * 处理x的next节点：
 * 如果移除的元素为尾元素(即next为null)，那么直接将节点prev赋值给last
 * 否则，将prev赋值给next.prev，并将x.next置空
 */
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 ;
}