LinkedList源码解析

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

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;
复制代码

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

Node结构

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

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;
    }
}
复制代码

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

第一个节点的prev指向NULL，最后一个节点的next指向NULL。其余节点通过prev与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<? extends E> c) {
    this();
    addAll(c);
}
复制代码

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

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<? extends E> c) {
    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<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> 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<E> 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<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;
    }
}
复制代码

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()方法和removeLast()方法

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<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
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;
}
复制代码

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

addFirst方法和addLast()方法

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<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++;
}
复制代码

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

下面我们来看下addLast方法，源码如下：

/**
 * Appends the specified element to the end of this list.
 *
 * <p>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<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++;
}
复制代码

add方法和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;
}

/**
 * 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
 * <tt>(o==null ? get(i)==null : 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;
}

/**
 * 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;
}
复制代码

我们看到add方法其实就是对linkLast方法的封装(当然，这是末尾添加)。remove方法逻辑会复杂些，需要先找到指定节点，然后调用unlink方法。

unlink方法解析

我们看到unlink方法首先将需要删除的节点的prev和next保存起来，因为后面需要将两者连接起来。然后将prev和next分别判断设置(包括边界值的考虑)，最后将x节点的数据设置为NULL。

clear方法

LinkedList链表结构的，它的clear方法是如何实现的呢？我们来看下：

/**
 * 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<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++;
}
复制代码

代码还是比较清晰的，就是从头结点开始，将Node节点一个个的设置为NULL，方便GC回收。

LinkedList与队列操作

有数据结构基础的同学应该都知道队列的结构，这是一种先进先出的结构。从JDK1.5开始，LinkedList内部集成了队列的操作，LinkedList可以当做一个基本的队列进行使用。下面我们从队列的角度来看下LinkedList提供的相关方法。

peek、poll、element、remove方法

/**
 * 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<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @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<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}
复制代码

从上面的方法，我们知道peek、element方法只返回队列头部数据，不移除头部。而poll、remove方法返回队列头部数据的同是，还会移除头部。

offer方法

/**
 * 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);
}
复制代码

从上面的代码中我们看到，offer方法其实就是入队操作。

LinkedList与双端队列

上面我们介绍了使用LinkedList来作为队列的相关方法，在JDK6中添加相关方法让LinkedList支持双端队列。源代码如下：

// 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<E> f = first;
    return (f == null) ? null : f.item;
 }

/**
 * Retrieves, but does not remove, the last element of this list,
 * or returns {@code 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<E> l = last;
    return (l == null) ? null : l.item;
}

/**
 * Retrieves and removes 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 pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * Retrieves and removes the last element of this list,
 * or returns {@code 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<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
复制代码

上面的代码逻辑比较清楚，就不详细介绍了。

LinkedList与栈(Stack)

堆栈大伙肯定很熟悉，是一种先进后出的结构。类似于叠盘子，一般我们使用的时候肯定从最上面拿取。栈也是这样，最后进入的，最先出去。LinkedList在JDK6的时候也添加了对栈的支持。我们来看相关源码：

/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 *
 * <p>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.
 *
 * <p>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();
}
复制代码

我们看到LinkedList封装的push和pop操作其实就是对first头结点的操作。通过对头结点不短了的push、pop来模拟堆栈先进后出的结构。

LinkedList与迭代器

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

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean 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) ? last : next.prev;
        nextIndex--;
        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<E> 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<? super E> action) {
        Objects.requireNonNull(action);
        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();
    }
}
复制代码

从上面的迭代器的源码我们可以知道以下几点：

• 1、LinkedList通过自定义迭代器实现了往前往后两个方向的遍历。
• 2、remove方法中next == lastReturned条件的判断是针对上一次对链表进行了previous操作后进行的判断。因为上一次previous操作后next指针会“悬空”。需要将其设置为next节点。

LinkedList遍历相关问题

对于集合来说，遍历是非常常规的操作。但是对于LinkedList来说，遍历的时候需要选择合适的方法，因为不合理的方法对于性能有非常大的差别。我们通过例子来看：

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

//遍历方法一
long time=System.currentTimeMillis();
for(int i=0;i<list.size();i++) {
	list.get(i);
}
System.out.println(System.currentTimeMillis()-time);


time=System.currentTimeMillis();
Iterator<String> iterator=list.iterator();
while (iterator.hasNext()) {
	iterator.next();
}
iterator.remove();
System.out.println(System.currentTimeMillis()-time);
复制代码

输出如下：

size:10000的情况
120
2
size:100000的情况
28949
2
复制代码

同样是遍历方法，为什么性能差别几十倍，设置上万倍呢？研究过源码的同学应该能发现其中的奥秘。我们来看get方法的逻辑：

/**
 * 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<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;
    }
}
复制代码

我们看到，我们get(index)的时候，都需要从头，或者从尾部慢慢循环过来。get(4000)的时候需要从0-4000进行遍历。get(4001)的时候还是需要从0-4001进行遍历。做了无数的无用功。但是迭代器就不一样了。迭代器通过next指针，能指向下一个节点，无需做额外的遍历，速度非常快。

总结

• 1、LinkedList在添加及修改时候效率较高，只需要设置前后节点即可(ArrayList还需要拷贝前后数据)。
• 2、LinkedList不同的遍历性能差距极大，推荐使用迭代器进行遍历。LinkedList在随机访问方面性能一般(ArrayList随机方法可以使用基地址+偏移量的方式访问)
• LinkedList提供作为队列、堆栈的相关方法。