Java编程拾遗『容器——LinkedList』

上篇文章讲了List的数组实现——ArrayList，在最后讲了ArrayList的一些特性，比如支持随机访问，插入和删除效率偏低。本篇文章来看一下List基于链表的实现LinkedList的一些细节，每一种实现都是有它特定的使用场景的，而LinkedList就可以解决ArrayList上述插入删除效率低下的问题。

1. 使用规则

LinkedList是基于双向链表实现的，声明如下：

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

跟ArrayList类似，LinkedList实现了List、Cloneable、Serializable接口，继承的抽象类AbstractSequentialList跟ArrayList继承的抽象类AbstractList是相同的作用，也是实现和接口分离的思想，在AbstractSequentialList中实现一些通用方法，方便扩展。另外需要注意的是，LinkedList实现了Deque接口，可以按照队列、栈和双端队列的方式进行操作。下面简单介绍一下方法的使用规则：

1.1 构造方法

1.2 List接口

AbstractSequentialList继承了AbstractList类，LinkedList继承AbstractSequentialList抽象类跟ArrayList继承AbstractList抽象类是一个道理，方便扩展。上图中LinkedList直接或间接实现的接口，LinkedList都是可以使用的，比如可以通过迭代器遍历LinkedList。List接口的方法之前都有详细介绍，这里再简单提一下，如下：

这部分方法在之前的文章中都有讲解，不多解释了。

1.3 Deque接口

LinkedList实现了Deque接口，Deque是一个双向队列，接口中定义了支持栈和队列的相关方法，所以可以使用LinkedList实现栈、队列的相关操作。Deque继承了Queue接口，Queue是一个单向队列，入队操作只能在尾部，出队操作只能在头部。下面来看一下Deque接口中的相关方法。

1.3.1 Queue接口

上面讲到，Deque实现了单向队列Queue接口，下面来看一下Queue接口中定义的方法，如下：

可以发现，队列同一个操作都有两个方法实现，主要区别在于对于一些极端情况的处理上，比如队列为空、队列满时的操作。另外需要注意的是，对于LinkedList实现的队列而言，队列容量没有限制，可以无限大，但是对于像ArrayDeque这样的队列，就有容量限制，产生队列满的情况。

1.3.2 Deque中栈操作方法

接触过数据结构的肯定都清楚，栈是一种后进先出的数据结构。在Java API java.util包中，存在一个Stack类，就是栈这一数据结构在Java中的实现，但是现在很少使用了。Deque中定义了一些栈相关操作的方法，并在LinkedList中给予实现，所以使用LinkedList可以实现队列操作。下面来简单看一下Deque接口中定义的栈操作相关方法，如下：

1.3.3 Deque中双向队列操作方法

栈只操作头部，队列两端都操作，但尾部只添加、头部只查看和删除。有一个更为通用的操作两端的接口Deque，Deque扩展了Queue，包括了栈的操作方法，下面来看一下Deque中用于支持双向队列操作的方法，如下：

2. 实现源码分析

在上篇介绍ArrayList的文章中讲过，ArrayList底层是基于数组实现的，内部存储的元素在物理存储上都是连续存放的。但LinkedList不同的是，LinkedList在物理存储上是非连续的，LinkedList中的各个元素是链表的一个节点，节点跟节点之间是通过引用链接到一起的，这一点跟C和C++的指针很像，如下图所示（下图为单向的链表，LinkedList是双向链表）：

 Java API LinkedList实现中，定义了一个内部类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类中定义了一个节点包括实际的元素item，同时有两个链接，分别指向前一个节点(前驱)prev，和后一个节点(后继)next。

LinkedList声明定义如下，内部主要包含如下三个成员变量：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

}  

类的继承关系上面已经讲过，成员变量size表示链表长度，默认为0，first指向双向链表头节点，last指向双向链表尾节点，初始值为null。

2.1 构造函数

Java API中LinkedList存在两个构造函数，一个无参默认构造函数，另一个是通过一个Collection对象构造LInkedList的构造函数，如下：

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
} 

当调用无参构造函数时，size为0，头节点first、尾节点last都为null。

2.2 add(E e)方法

add(E e)方法的功能是向链表尾部添加一个元素，跟ArrayList不同的是，ArrayList在物理存储上是连续的，内部通过数组实现，在添加元素时，要保证容量足够，但是LinkedList在物理上时一个个逻辑上相连的节点，没有容量的定义，所以在add操作时，也不用像ArrayList那样提前分配一个余量，在添加元素时，只要新增一个节点，然后修改一下链接就可以了。定义如下：

public boolean add(E e) {
    linkLast(e);
    return true;
} 

add方法中调用了linkLast方法，向链表尾部添加一个元素，如下：

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

其中比较重要的就是调用Node的构造函数，生成一个Node用于存储带插入的数据e，并进行链接。

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

在生成Node时，对Node的prev和next指针进行链接(这里为了方便表述，本篇文章之后都通过指针表述链接)。在linkLast方法中拿到新生成的Node，尾插法进行连接，修改last指针，first指针指向，并对链表的size和modCount进行自增操作。如下：

 看一个具体的例子，如下：

2.3 add(int index, E element)方法

add(int index, E element)方法时像链表index索引位置添加一个元素，定义如下：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

首先还是通过checkPositionIndex方法，检查index索引的合法性，跟上节讲ArrayList插入操作时一样，index索引位置要求只能在size范围内，如下：

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

接下来通过index和size的关系，判断时在尾部插入还是在尾部之前的位置插入，如果时尾部插入就跟之前的add(E element)操作一致，直接调用linkLast方法即可。如果在size之前的位置插入，调用linkBefore方法进行插入操作，如下：

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

操作也比较简单，就是将带插入的元素生成一个Node，并对Node前后的节点的next、prev指针进行链接，对size和modCount进行自增操作上面已经讲述了，这里不重复讲解了，可以参考下图：

2.4 remove(int index)方法

remove(int index)用来删除指定index位置的元素，如下：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

首先调用checkElementIndex方法检查待删除的index，index范围要求index >= 0 && index < size。然后调用unlink方法，删除node(index)前后节点的链接指针，并进行重链接，如下：

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

首先让x前驱Node的next指针指向x的后继Node，如果x没有前驱Node，说明删除的是头节点，则修改头节点指向x的后继Node。然后让x的后继Node的prev指针指向x的前驱Node，如果x没有后继Node，说明删除的是尾节点，则修改尾节点指向x的前驱Node。 如下图：

2.5 remove(Object o)方法

LinkedList中还有一个remove方法，如下：

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

删除LinkedList中所有与o相等的元素，就是通过藏头遍历LinkedList，然后通过上述unlink操作删除节点。

2.6 get(int index)方法

get方法用于获取指定index位置的元素，定义如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

首先通过checkElementIndex方法，检查index索引的合法性，index范围要求index >= 0 && index < size。然后返回index索引位置的Node的item，如下：

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

size>>1等于size/2，如果索引位置在前半部分 (index<(size>>1))，则从头节点开始查找，否则，从尾节点开始查找，这样效率会高一些。同时也验证了之前的一个结论，ArrayList支持随机访问，查询效率比较高，LinkedList不支持随机访问，需要从头或尾遍历，效率相对较低，时间复杂度为O(N)。

2.6 迭代器

LinkedList中存在四种可用的迭代器，可以通过如下方式获取：

• iterator()，继承自AdstractList类，返回LinkedList从头向尾的单向Iterator迭代器
• descendingIterator()，继承自Deque接口，LinkedList中实现，返回从尾向头的单向Iterator迭代器
• listIterator(int index)，继承自List接口，LinkedList中实现，返回LinkedList index位置开始的的双向迭代器
• spliterator()，返回LinkedList的并行Spliterator迭代器

跟ArrayList相似，在使用迭代器进行迭代过程中，如果修改了LinkedList结构，也会抛ConcurrentModificationException异常。

3. LinkedList特点

• 各元素之间逻辑上连续，物理存储上不连续
• 不支持随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)
• 按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)
• 在两端添加、删除元素的效率很高，为O(1)
• 在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)，不需要像ArrayList那样移位