java集合（3）：LinkedList源码分析

前言

LinkedList集合类是List 接口的链接列表实现。实现所有可选的列表操作，并且允许包含所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

上面这段话什么意思呢？简单说就是LinkedList类不仅实现了List接口，具备列表的特性。而且也实现了Queue接口，因此也就具备了队列和栈的特性，当然可以拿来当队列或者栈来使用。那么是怎么实现队列和栈的特性呢？很简单，LinkedList实现了一组只操作链表头（head）和尾（last）的操作，于是就保证了队列和栈的特性。下图展示了LinkedList类从两个接口中继承的方法。

由上图可以看到，LinkedList类实现了List接口中的一般性操作方法（add，get，remove，set等），并且实现了Deque接口中的只操作头和尾元素的方法，这些方法有个特点就是大多以xxxFirst()和xxxLast()命名。通过操作头尾的方法，就能很方便的拥有队列和栈的特性。

正文

LinkedList源码分析。

1，LinkedList类定义

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable  // 最主要的还是List，Deque接口
           

2， LinkedList类成员变量

transient int size = ;   // List长度

    transient Node<E> first;  // 指向头结点的引用（指针）

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

3，LinkedList类的2个构造方法

public LinkedList() {  // 空链表
    }

    public LinkedList(Collection<? extends E> c) { // 将已知集合按其迭代器顺序构造成链表
        this();
        addAll(c); // addAll()方法正是构造链表的方法
    }
           

4，LinkedList类中来自Deque接口的常用方法（xxxFirst，xxxLast）。我们发现，类中的这部分方法大多存在相互调用的情况，其中被调用最多的当属下列4个方法，这4个方法也就构成了类中头尾操作方法体系的基础。

private void linkFirst(E e) {  // 方法1，在链表头添加一个元素
        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++;
    }
    void linkLast(E e) {    // 方法2，在链表尾添加一个元素
        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++;
    }
     private E unlinkFirst(Node<E> f) {  // 方法3，移除链表头元素
        // 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;
    }
    private E unlinkLast(Node<E> l) {   // 方法4，移除链表尾元素
        // 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;
    }
           

以上面4个操作为基础，来看一下其他方法如何调用这些基础方法实现基本功能的。

• add，addXXX，offer，push等添加操作，都是在调用linkFirst(),linkLast()方法

public boolean add(E e) {
        linkLast(e);  // 调用基础方法
        return true;
    }
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);  // 调用基础方法
        else
            linkBefore(element, node(index));
    }
    public void addFirst(E e) {
        linkFirst(e);  // 调用基础方法
    }
    public void addLast(E e) {
        linkLast(e);  // 调用基础方法
    }
    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;
    }
    public void push(E e) {
        addFirst(e);  // 调用基础方法
    }
           

• remove()，removeFirst()，removeLast()，poll()，pollFirst()，pollLast()，pop()等删除元素都是在调用unlinkFirst()，unlinkLast()方法。

public E remove() {
        return removeFirst();  // 调用基础方法
    }
    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 E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);  // 调用基础方法 
    }
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);  // 调用基础方法
    }
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);  // 调用基础方法
    }
    public E pop() {
        return removeFirst();  // 调用基础方法
    }
           

5，继承自List接口的方法，这部分方法大多跟“脚标”有关系，常用的有如下几个

public void add(int index, E element) {  // 索引处添加新元素
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    public E get(int index) {  // 获取索引处的元素
        checkElementIndex(index);
        return node(index).item;
    }
    public E set(int index, E element) { // 替换索引处的元素
        checkElementIndex(index); 
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    public E remove(int index) {  // 删除索引处的元素
        checkElementIndex(index);
        return unlink(node(index));
    }
           

上面方法的共同点是都调用了node()方法，该方法返回指定索引处的元素。

Node<E> node(int index) {

        if (index < (size >> )) { // 如果索引值在前半部，就从头开始迭代
            Node<E> x = first;
            for (int i = ; i < index; i++)
                x = x.next;
            return x;
        } else {   // 如果索引值在后半部，就从尾开始迭代
            Node<E> x = last;
            for (int i = size - ; i > index; i--)
                x = x.prev;
            return x;
        }
    }
           

6，迭代器方法，这个在上一篇已经讲过了。

总结

LinkedList的实现跟ArrayList有很大不同，这两个作为最常用的集合，各自有自己的长处和短板，以后在开发中会经常用到，需认真体会。