Java LinkedList的用法（非常详细）

LinkedList 常用来和 ArrayList 进行比较，事实上，这一类的问题都是顺序访问序列和随机访问序列的比较。LinkedList 的两个主要的特性为：顺序访问和写快读慢。下面，将通过对 JDK 源码的解析，来分析 LinkedList 的实现原理。

1. 父类和接口

1）java.util.AbstractSequentialList

该抽象类继承自 java.util.AbstractList，提供了顺序访问存储结构，只要类似于 LinkedList 这样的顺序访问 List，都可以继承该类。它提供了get\set\add\addAll\remove 等方法的迭代器方式的实现，前提是必须提供对迭代器接口 java.util.Iterator 的实现。

2）java.util.Deque

双向队列接口，继承自 java.util.Queue。LinkedList 为什么要实现该接口呢？因为 Queue 的特性是“先进先出”，也就是说，可以在尾部增加数据，头部获取数据。Deque 则可以同时在头尾处完成读写操作。在此基础上，LinekdList 还能操作头尾之间的任意结点，所以 LinkedList 在实现 Deque 的同时实现了 java.util.List。

3）java.lang.Cloneable、java.util.List 和 java.lang.Serialiable

这三个接口的讲解与 ArrayList 文章中一样，请转到 ArrayList 文中查看。

2. 成员变量和常量

这里重点介绍 3 个成员变量：

• transient int size=0; 用于标记序列的大小，因为链表由单个结点组成，除了统计结点个数以外并没有办法获取 size，所以提供了一个标记量来做记录，来提高效率。
• transient Node<E>first; 链表的头结点。
• transient Node<E> last; 链表的尾结点。同时提供头尾结点是为了实现java.util.Deque双向队列接口要求的功能。

引申：可以注意到，所有成员变量都被transient修饰符修饰，在 ArrayList 文章中介绍过，该修饰符用于标记无需序列化的成员变量。也就是说，LinkedList 的所有成员都无需序列化。那么，结合之前讲解过的 Serialiable 接口的知识，可以得出结论，LinkedList 一定提供了 readObject 和 writeObject 方法，读者可以自行阅读LinkedList 源码查证。与 ArrayList 的实现原理类似。

常量：private static final long serialVersionUID=876323262645176354L;

这个常量提供给 Serialiable 序列化接口使用，在 ArrayList 文中里有详细讲解，不再赘述。

3. 构造方法

LinkedList 有两个重载的构造方法：

• public LinkedList()。
• public LinkedList(Collection<? extends E>c)。

与 ArrayList 需要一个定长的数组不同，链表无需初始化任何对象，所以无参构造方法里没有做任何操作；Collection 形参的构造方法中，调用了addAll(Collection) 方法，该方法的具体实现将会在后面讲解。

4. Deque双向队列的实现

LinkedList 是一个在双向队列基础上搭建的双向链表，面试时候经常会问到其底层实现原理；因此，不仅要求掌握底层实现使用的数据结构，而且还需要掌握底层的具体实现原理。

双向链表的关键方法主要有以下几个：

• addFirst(E)：在队头添加元素。
• addLast(E)：在队尾添加元素。
• E removeFirst()：删除队头元素。
• E removeLast()：删除队尾元素。

这些方法都是通过操作成员变量 first 和 last 来实现的。first 和 last 的类型是私有类 Node<E>。实现很简洁，Java 代码如下所示：

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

熟悉双向链表数据结构的读者一定知道：“链表是由结点构成的，结点分为数据域和指针域，双向链表里的单个结点会保存上前驱结点和后继结点的指针（在 Java 语言中是引用）”。

这个 Node，是不是就符合和双向链表的结点概念？

• E item 是数据域，用于存储数据。
• Node<E>next 指向后继结点。
• Node<E>prev 指向前驱结点。

构造方法中清晰体现了它们的初始化过程。这样就能很好地理解之前提及的四个方法是如何实现了。

比如，addLast(E)，新建一个 Node 结点 n，数据域为方法形参，n.prev 设置为当前的 last，last.next 设置为 n，然后 last=n，即可完成需求。其他方法的实现原理类似。

5. getFirst/getLast/get方法实现

getFirst和getLast这两个方法分别用于取出头或尾的数据，在理解了 first 和 last 这两个 Node 之后，就很好理解了，直接返回 first.item 和 last.item 即可实现。

get(int) 方法则不一样，LinkedList 是顺序存储结构，要取到第 i 个数据，必须顺序遍历到 i 结点，所以这个方法的时间复杂度为 O(n)。具体实现时，在这个基础上进行了优化，实现代码如下所示：

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

如果 index 小于 size（成员变量，代表链表长度）的一半，那么正序遍历，反之倒序遍历。虽然这依然是个 O(n) 级别的算法，但是遍历规模小了一倍。这里也体现了双向队列的应用。

6. set/add/addAll的实现

与 ArrayList 不同的是，LinkedList 的 add 方法比 set 更加迅速。add 的本质是在尾部增加一个结点，LinkedList 维护有成员变量 last，很快就能实现。而 set 则需要遍历查找到指定结点 i，并替换之。

addAll(Collection) 等价于调用 add(E) 多次。

7. removeFirst/removeLast/remove方法实现

removeFirst 与 removeLast 方法用于移除头尾结点并返回数据，remove 则是遍历到指定结点，然后移除它。都很好理解，这里需要注意的是它们都会调用的方法unlinkFirst/unlinkLast/unlink。而这三个方法都是用于解除 Node 指针域的指向关系，也就是把 Node.prev 或 Node.next 指向 null。

remove方法的删除操作只需要修改待删除结点后继结点的 pre 与前驱结点的 next 的指向，而不需要像 ArrayList 的 remove 操作一样移动数据，因此，删除操作有更高的效率。

8. 迭代器

ListIteractor<E>listIterator() 方法返回了一个内部类 ListItr，该类即是 LinkedList 迭代器的实现。由于 LinkedList 本身就是顺序结构，该迭代器除了记录 nextIndex 之外没有做特殊处理。此外 LinkedList 的迭代器也具备 fail-fast 特性。