LinkedList

ArrayList是通过数组实现存储，而LinkedList则是通过链表来存储数据，而且他实现的是一个双向链表，简单的说一下什么是双向链表。双向链表是数据结构的一种形式，他的每个节点维护两个指针，prev指向上一个节点，next指向下一个节点。这种结构有什么特点呢？他可以实现双向遍历，这使得在链表中的数据读取变得非常灵活自由。同时，LinkedList中维护了两个指针，一个指向头部，一个指向尾部。维护这两个指针后，可以使得元素从头部插入，也可以使元素从尾部插入。基于方式，用户很容易就能实现FIFO(队列)，LIFO(栈)等效果。那么下面我们来看一下源码中的具体实现。

1.Node节点定义：

2.FIFO(队列)实现原理：
队列的原理就是每次都从链表尾部添加元素，从链表头部获取元素，就像生活中的排队叫号，总是有个先来后到。


// 队列尾部添加一个元素，建议使用这个，约定俗成吧。
public boolean offer(E e) {
    return add(e);
}
// 队列尾部添加一个元素
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
// offer和offerLast底层调用的都是linkLast这个方法，顾名思义就是将元素添加到链表尾部。
void linkLast(E e) {
    final Node<E> l = last;
    // 创建一个节点，将prev指针指向链表的尾节点。
    final Node<E> newNode = new Node<>(l, e, null);
    // 将last指针指向新创建的这个节点。
    last = newNode;
    if (l == null)
        // 如果当前链表为空，那么将头指针也指向这个节点。
        first = newNode;
    else
        // 将链表的尾节点的next指针指向新建的节点，这样就完整的实现了在链表尾部添加一个元素的功能。
        l.next = newNode;
    size++;
    modCount++;
}
// 在链表头部删除一个元素，建议用这个，别问我为什么，我也不知道
public E poll() {
    return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// poll和pollFirst底层调用的就是这个方法，将链表的头元素删除。
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;
}
// 获取头元素，但是不会删除他。
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

以上就是LinkedList实现的两种功能，这里包含了大部分关于链表操作的方法，但不仅限于这几种。不管是栈也好，队列也好，元素都是从头部删除的unlinkFirst方法。但是用户在使用的过程中并不只用到上面两张方式，我们也可以从链表尾部删除元素如removeLast，peekLast，pollLast，unlinkLast等方法。

上文讲到的功能，其实是实现了Deque接口，而现在要讲述的是实现与List的部分功能。那么最典型的操作就是直接对容器元素的读取，因为List容器的一大特点就是顺序存储，元素在容器中的位置和存入时是保持一致的，那么用户在读取元素的时候理所当然就可以通过元素下标来获取，下面就具体介绍这几种方法。

1.将元素插入容器的指定位置

// 将元素插入指定位置
public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
    else
        // 如果不是位于末尾，那么就将元素插入指定位置的元素之前，
        linkBefore(element, node(index));
}
// 将元素插入指定元素前，链表插入元素是数据结构中最基础的知识，这里就不再赘述了。
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++;
}

LinkedList的迭代器实现有两个，一个是实现了Iterator接口的DescendingIterator，另一个则是实现了ListIterator接口的ListItr。

1.ListItr
ListItr遍历需要指定一个起始值

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

ListItr会创建一个以index为起始值的迭代器，然后用户便可以以这个位置为起点，实现向前或者向后遍历。

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();

5. LinkedList

LinkedList