LinkedList源码浅析

摘要：重要方法在链尾添加元素除了这个方法以外，还提供了等一些方法，都是为实现和方法服务的，因为双向链表的原因，这些实现都很简单。

LinkedList类声明如下：

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

可以发现 LinkedList继承了 AbstractSequentialList抽象类，而不是像 ArrayList和 Vector那样实现 AbstractList，实际上，java类库中只有 LinkedList继承了这个抽象类，正如其名，它提供了对序列的连续访问的抽象：

LinkedList的底层是 Deque双向链表，实现了 Deque接口，而 Deque接口继承于 Queue接口，因此，在java中，如果要实现队列，一般都使用 LinkedList来实现。

LinkedList中关于链表结点的定义如下：

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

每个结点都有一个前驱和后继结点，并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点：

transient Node first;
transient Node last;

LinkedList中只有两个构造方法，无参数的和带有 Collection参数的：

public LinkedList() {
}
    
public LinkedList(Collection c) {
        this();
        addAll(c);
}

重点看一下第二个构造方法，它调用了 addAll()：

public boolean addAll(Collection c) {
        return addAll(size, c);
    }

这个方法将指定的 Collection添加到链表的结尾，如果在添加的过程中对 Collection进行了修改，则结点是不确定的。

public boolean addAll(int index, Collection c) {
        checkPositionIndex(index);//检查是否越界
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node pred, succ;
        if (index == size) { //如果succ是null，说明是在结尾添加，如果不是，记录index处的结点
            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;
    }

注意最终调用的是这个 addAll方法，这个方法是在指定位置 index 插入 Collection，使链表后面的元素右移，第一个 addAll中传入的 index是 size，因此就是在结尾添加。

 public boolean add(E e) {
        linkLast(e);
        return true;
    }
 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++;
    }    

除了这个 linkLast方法以外，还提供了 linkFirst linkBefore unLink unLinkFirst等一些方法，都是为实现 add和 remove方法服务的，因为双向链表的原因，这些实现都很简单。

因为底层实现不是数组，LinkedList中的 clear方法稍微复杂一些：

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++;
    }

clear方法中逐一取出每个结点，然后将它们的 item pre next都设为 null，有时候看以来不必要，但是为了防止在GC中，这些结点寄居在不同的年代中，因此最好这么做。

先看 clone方法的实现：

public Object clone() {
        LinkedList clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }
    
@SuppressWarnings("unchecked")
    private LinkedList superClone() {
        try {
            return (LinkedList) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }    

可以看到， LinkedList的 Clone方法只是简单的将原来每个 node的 item放到克隆后的对象中，和 ArrayList的 clone方法一样， LinkedList的 Clone方法也只是浅复制，如果元素为引用类型，那么修改原 list的值会影响克隆的 list的值。

如果仔细观察，你会发现在 LinkedList中是没有自己实现 iterator的，如果这样调用：

LinkedList list = new LinkedList<>();
Iterator it = list.iterator();

你会发现它调用的是 AbstractSequentialList中的 iterator()，返回的还是 AbstractList 中的 listIterator()，而在 LinkedList中实现了自己的 listIterator，因此如果进行迭代，还是老老实实用 LinkedList中的 listIterator比较好。
LinkedList中还提供了逆序的 Iterator—— DescendingIterator，实际上它也只是简单的对 ListIterator进行了封装：

private class DescendingIterator implements Iterator {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

public Iterator descendingIterator() {
        return new DescendingIterator();
    }    

这里只是说一下大致的区别：

ArrayList继承于 AbstractList， LinkedList继承于 AbstractSequentialList；

ArrayList基于数组， LinkedList基于双向链表，对于随机访问， ArrayList比较占优势，对于插入删除，LinkedList占优势；

LinkedList没有实现自己的 Iterator，但是有 ListIterator和 DescendingIterator；

LinkedList需要更多的内存，因为 ArrayList的每个索引的位置是实际的数据，而 LinkedList中的每个节点中存储的是实际的数据和前后节点的位置；

ArrayList 和 LinkedList都是非同步的集合。