Java LinkedList

通过双向链表(Doubly-linked)实现，实现了List和Deque接口，所以LinkedList可以作为List的使用，也可以作为Stack和Queue来使用。

作为List使用

结构

LinkedList中维护两个指向链表第一个节点和最后一个节点的指针。Node是一个私有内部类，Node类中存有值item，和两个指向上一结点和下一节点的指针。
整个LinkedList是由一个个Node节点组成的，为了维护每个Node的上下节点信息，链表需要使用更多的空间。

transient Node<E> first;
transient Node<E> last;

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    ...
}

我们通过以下小例子来看一下LinkedList的存储结构。

List<String> list = new LinkedList<>();
list.add("语文: 1");
list.add("数学: 2");
list.add("英语: 3");

结构图示如下

结构

add方法

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);// l是prev节点，e是item值，next节点为null
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

add方法挺简单的，就是在链表尾部添加一个新的Node，也就是调用linkLast(e)方法。不过有一点要注意的是，当l==null，
也就是目前链表只有一个节点，所以first和last指向同一个节点。

get方法

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

Node<E> node(int 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;
    }
}

get方法中，调用了Node方法。Node方法会判断index是在前半区还是后半区，如果是在前半区，就从first开始往后搜索，
如果是在后半区，就从last开始往后搜索。这样使原本查找性能由O(n)变为O(n/2)。

remove方法

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // 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;
}

add方法是linkLast,而remove方法是unlinkFirst。这里也要判断一下特殊情况，当next==null的时候，就是LinkedList中没有节点时，
last要设置为null。

作为Queue使用

LinkedList实现了Deque接口，Deque接口又继承了Queue接口，所以LinkedList也可以作为Queue使用。
下面通过一个小例子来展示一下作为Queue使用的LinkedList。

public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < 5; i++) {
        queue.add(i);
    }

    while (!queue.isEmpty()) {
        Integer i = queue.poll();
        System.out.printf("%d ", i);
    }
}

我们使用Queue的add方法来向队列添加元素，使用poll方法来获取元素。Queue的remove方法也可以用来获取元素，
但是当列表为空时，remove方法会抛出异常，而poll方法会返回null。

add方法刚才已经介绍了，来看一下poll方法。

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

好吧，poll方法只是判断f是否为null，如果不是就调用unlinkFirst方法，这个方法刚才我们也介绍过了。

作为Stack(Deque)使用

Java中其实是有一个Stack类的，但是由于某些原因，Java推荐我们使用Deque来代替Stack。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

而LinkedList实现了Deque接口，所以也可以作为Stack使用。来看一个小栗子：

public static void main(String[] args) {
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i < 5; i++) {
        stack.push(i);
    }

    while (!stack.isEmpty()) {
        Integer i = stack.pop();
        System.out.printf("%d ", i);
    }
}

我们使用Deque的push方法来向栈中添加元素，使用pop方法来获取元素。

public void push(E e) {
    addFirst(e);
}
public E pop() {
    return removeFirst();
}

pop方法中调用了removeFirst方法，刚才我们也介绍过了。push方法调用了addFirst方法，
和linkLast类似，只不过是把添加到链表尾部改为添加到头部，就不多赘述了。

图和部分代码摘自Java LinkedList工作原理及实现