LinkedList源码解析

摘要：我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针，能指向下一个节点，无需做额外的遍历，速度非常快。不同的遍历性能差距极大，推荐使用迭代器进行遍历。

上一篇文章我们介绍了JDK中ArrayList的实现，ArrayList底层结构是一个Object[]数组，通过拷贝，复制等一系列封装的操作，将数组封装为一个几乎是无限的容器。今天我们来介绍JDK中List接口的另外一种实现，基于链表结构的LinkedList。ArrayList由于基于数组，所以在随机访问方面优势比较明显，在删除、插入方面性能会相对偏弱些(当然与删除、插入的位置有很大关系)。那么LinkedList有哪些优势呢？它在删除、插入方面的操作很简单(只是调整相关指针而已)。但是随机访问方面要逊色写。下面我们还是从源码上来看下这种链表结构的List。

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node last;

我们看到字段非常少，size表示当前节点数量，first指向链表的起始元素、last指向链表的最后一个元素。

从上面主要字段看出，LinkedList链表的Item就是一个Node结构，那么Node结构是怎样的呢？源码如下：

private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

我们看到Node结构包含一个前驱prev指针，item(value)、后继next指针三个部分。结合上面的描述，我们知道了LinkedList的主要结构。如图：

LinkedList相关方法解析 构造函数

/**
 * 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<");

由于LinkedList是通过prev与next指针链接起来的，有元素添加时只需要一个个设置指针将其链接起来即可，所以构造函数相对较简洁。我们重点来看下第二个构造函数中的addAll方法。

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the specified
 * collection"s iterator.  The behavior of this operation is undefined if
 * the specified collection is modified while the operation is in
 * progress.  (Note that this will occur if the specified collection is
 * this list, and it"s nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<");return addAll(size, c);
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection"s iterator."
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<");if (numNew == 0)
        return false;

    Node pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

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

    size += numNew;
    modCount++;
    return true;
}

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

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

addAll方法是将Collection集合插入链表。下面我们来仔细分析整个过程(涉及比较多的指针操作)。

首先代码检查index的值的正确性，如果index位置不合理会直接抛出异常。

然后将待插入集合转化成数组，判断集合长度。

根据index值，分别设置pred和succ指针。如果插入的位置是当前链表尾部，那么pred指向最后一个元素，succ暂时设置为NULL即可。如果插入位置在链表中间，那么先通过node方法找到当前链表的index位置的元素，succ指向它。pred指向待插入位置的前一个节点，succ指向当前index位置的节点，新插入的节点就是在pred和succ节点之间。

for循环创建Node节点，先将pred.next指向新创建的节点，然后pred指向后移，指向新创建的Node节点，重复上述过程，这样一个个节点就被创建，链接起来了。

最后根据情况不同，将succ指向的那个节点作为最后的节点，当然如果succ为NULL的话，last指针指向pred。

removeFirst方法会返回当前链表的头部节点值，然后将头结点指向下一个节点，我们通过源码来分析：

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node 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;
}

我们看到主要逻辑在unlinkFirst方法中，逻辑还是比较清晰的，first指针指向next节点，该节点作为新的链表头部，只是最后需要处理下边界值(next==null)的情况。removeLast方法类似，大家可以去分析源码。

addFirst方法是将新节点插入链表，并且将新节点作为链表头部，下面我们来看源码：

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

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

代码逻辑比较清晰，newNode节点在创建时，由于是作为新的头结点的，所以prev必须是NULL的，next是指向当前头结点f。接下来就是设置first，处理边界值了。
下面我们来看下addLast方法，源码如下：

/**
 * Appends the specified element to the end of this list.
 *
 * 
This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

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

这两个方法是我们使用频率很高的方法，我们来看下其内部实现：

/**
 * Appends the specified element to the end of this list.
 *
 * 
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;
}

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * (o==null ");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 x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * Unlinks non-null node x.
 */
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node 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;
}

我们看到add方法其实就是对linkLast方法的封装(当然，这是末尾添加)。remove方法逻辑会复杂些，需要先找到指定节点，然后调用unlink方法。
unlink方法解析
我们看到unlink方法首先将需要删除的节点的prev和next保存起来，因为后面需要将两者连接起来。然后将prev和next分别判断设置(包括边界值的考虑)，最后将x节点的数据设置为NULL。

/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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 x = first; x != null; ) {
        Node next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node f = first;
    return (f == null) ");return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E element() {
    return getFirst();
}

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node f = first;
    return (f == null) ");return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}

/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

// Deque operations
/**
 * Inserts the specified element at the front of this list.
 *
 * @param e the element to insert
 * @return {@code true} (as specified by {@link Deque#offerFirst})
 * @since 1.6
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * Inserts the specified element at the end of this list.
 *
 * @param e the element to insert
 * @return {@code true} (as specified by {@link Deque#offerLast})
 * @since 1.6
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * Retrieves, but does not remove, the first element of this list,
 * or returns {@code null} if this list is empty.
 *
 * @return the first element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
public E peekFirst() {
    final Node f = first;
    return (f == null) ");if this list is empty.
 *
 * @return the last element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
public E peekLast() {
    final Node l = last;
    return (l == null) ");if this list is empty.
 *
 * @return the first element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
public E pollFirst() {
    final Node f = first;
    return (f == null) ");if this list is empty.
 *
 * @return the last element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
public E pollLast() {
    final Node l = last;
    return (l == null) ");

/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 *
 * 
This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}

/**
 * Pops an element from the stack represented by this list.  In other
 * words, removes and returns the first element of this list.
 *
 * 
This method is equivalent to {@link #removeFirst()}.
 *
 * @return the element at the front of this list (which is the top
 *         of the stack represented by this list)
 * @throws NoSuchElementException if this list is empty
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

private class ListItr implements ListIterator {
    private Node lastReturned;
    private Node next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ");hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ");return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<");while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

List list=new LinkedList<>();
for(int i=0;i<10000;i++) {
	list.add(String.valueOf(i));
}

//遍历方法一
long time=System.currentTimeMillis();
for(int i=0;i iterator=list.iterator();
while (iterator.hasNext()) {
	iterator.next();
}
iterator.remove();
System.out.println(System.currentTimeMillis()-time);

size:10000的情况
120
2
size:100000的情况
28949
2

/**
 * 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}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

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

    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}