容器--LinkedList

一、前言

　　上一篇我们介绍了List的重要实现之一ArrayList, 在大多数情况下，我们写代码时会直接使用到ArrayList，因为其在随机访问的优势是其它List无法比拟的。除了ArrayList之外， JDK还提供了一种List实现，即LinkedList, 这个是基于链表来实现的，虽然我们平时用的不多，但它却天生是一个功能完备的双向队列，也可以直接当作stack来使用，所以有些时候还是能有其用武之地的。

　　本文将对这个类的实现机制进行介绍。

二、实现原理

　　和ArrayList类似，LinkedList里的大部分方法都比较简单，所以我们没有必要每个方法都分析，而是重点介绍一些能体现其实现机制的内容。

　　1）数据如何存储？

LinkedList使用的是链表的数据结构进行存储，在数据结构中我们知道，链表结构不同于数组，其在物理上的存储空间是不连续的，每个节点表示一个数据对象，节点与节点之间通过引用变量进行关联，一般分为单向链表和双向链表。LinkedList采用的是双向链表的方式。具体来说，LinkedList通过以下字段或类来进行构造。

　　size: 这个表示LinkedList里数组的个数，初始为0

　　first:链表的表头元素，初始为null， Node<E> 类型

　　last: 表尾元素，初始为null, Node<E> 类型

　　Node：用于表示节点的内部类，定义如下：

 1 private static class Node<E> {
 2         E item; //元素
 3         Node<E> next; //后继
 4         Node<E> prev; //前驱
 5 
 6         //三个参数的顺序,前驱,元素,后继
 7         Node(Node<E> prev, E element, Node<E> next) {
 8             this.item = element;
 9             this.next = next;
10             this.prev = prev;
11         }
12     }

　　可见每个节点都有前驱和后继，这样就构造成了一个双向链表，注意这个链表并不是闭环的，也就是first和last之间没有引用关系。那么针对链表的所有操作，实际上都可以理解为是对部分节点（或所有）的遍历及前后引用的修改操作。理解了链表的操作，也就容易理解LinkedList了。

　　和ArrayList不一样，在新增元素的时候，LinkedList并不需要扩容。

　　2）如何实现get(index)？

　　对于ArrayList来说，实现get(index)的时间复杂度为O(1)，而LinkedList则需要O(n)，因为需要对链表进行遍历，不过由于是双向链表，所以在实现时做了点小小的优化，即先判断index是在前半部分，还是后半部分，以决定是从表头遍历还是表尾遍历。实现如下：

 1 Node<E> node(int index) {
 2         // assert isElementIndex(index);
 3 
 4         //判断 index 在 整个列表中的位置来决定是从头遍历还是从尾遍历
 5         if (index < (size >> 1)) {
 6             Node<E> x = first;
 7             for (int i = 0; i < index; i++)
 8                 x = x.next;
 9             return x;
10         } else {
11             Node<E> x = last;
12             for (int i = size - 1; i > index; i--)
13                 x = x.prev;
14             return x;
15         }
16     }

　　因为每个元素都是有其前后的指针的，所以，只要能定位到某个位置的元素，再在该位置做任何操作都比较方便了。所以，在LinkedList对于所有按index来操作的方法（比如add,remove,set,get等），都是先通过node方法来定位到元素，然后再做相应的操作。

　　3）如何实现对队列的支持？

　　LinkedList的一个重要特点就是实现了双向队列的接口(Deque), 当然Deque继承自Queue，所以单向队列自然也是支持，另外还提供了实现一个栈所需要的方法，比如push, pop，所以也相当于是实现了栈的功能。根据队列和栈的特点，我们可以认为它们是简化以及具有一些设计限制的链表，所以可以直接把链表作为队列和栈来使用。

当然，用ArrayList也能实现栈和队列，但随着队列的出队，入队，栈的出栈，入栈，ArrayList底层的数组大小可能会不断增长，而可能大部分空间都没有利用到，这需要一种更巧妙的实现方式去处理，总的来说较为复杂。

　　但由于队列和栈只会在链表的两端进行操作，不涉及到元素的遍历，这刚好避开了链表的不足，而利用到了链表的优势，所以，我们一般用链表来实现这样的数据结构。

对于LinkedList来说，无论是在表头还是表尾操作都是非常简单的事，仅举一例如下：

    public boolean offer(E e) {
        return add(e); //队尾入队
    }
    public boolean add(E e) {
        linkLast(e); // 将元素添加到列表最后
        return true;
    }
    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++;
    }

上面的逻辑中惟一需要注意的就是我们要正确地将newNode关联到链表中，以及更新表尾的引用。

　　另外，在JDK中对于Queue的定义中，实际上存取元素都分为多个版本，抛异常和不抛出异常，有的时候容易将其混得不清楚，这里对比如下：

Queue各方法对比表

方法功能	异常版本	非异常版本	说明
队尾入队	add	offer	仅对于有容量限制的队列来说，如果队列已满，则执行add会抛出异常，而offer直接返回false
队头出队	remove	poll	当队列为空时，remove抛出异常，而poll返回null
获取队尾元素（不出队）	element	peek	当队列为空时，element抛出异常，而peek返回null

　　刚好我们举了offer的例子，上面可以看到offer的实现和add是完全一样的，这是因为LinkedList并没有对容量的大小做出限制，这种情况下，这两者的实现方式是一样的。

　　异常版本也不难记，它们的首字母刚好组成单词（are)，后续当我们学习到阻塞队列时，这几个方法还有对应的阻塞版本。

三、总结

　　对于链表来说，我们重点要记住的，就是其对于链表结构的定义，以及其对于节点操作的主要步骤，另外就是要了解其是如何实现队列的功能的。