阅读java.util.LinkedList源码Note

Queue 队列

这些操作都是在头部进行操作，但队列内的排序则不尽然相同，可以FIFO，也可以LIFO， 队列、栈！

Deque 双端队列

方法比较

作为队列, FIFO

作为栈 Stack

双向链表： 链表记录头节点和尾节点，每个节点会持有前驱节点和后驱节点的引用。

public class LinkedList {
    Node first;
    Node last

    class Node {
        Node pre;
        Object item;
        Node next;
    }
}

fail-fast机制：在创建Iterator后，只能通过iterator的remove后者add方法修改集合，其他方式都会引起遍历失败。

    /**
     * Pointer to first node.
     * 集合为空时，first和last必定为空
     * 集合不为空时，first的前驱为空，first的item不为空
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * 集合为空时，first和last必定为空
     * 集合不为空时，last的后驱为空，last的item不为空
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

内部获取指定位置的元素，判断index在前半部分还是后半部分

if( index < size >> 1) {
    //从first开始向后遍历
}else {
    //从last开始向前遍历
}

修改集合结构时，需操作前后节点的prev和next，同时需考虑是否需要设置头尾节点

记录几个关键方法，其余方法底层均是使用此部分方法实现

/**
     * Links e as first element.
     * 链接一个元素为头部节点，注意：此并非为替换元素
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        //集合的头节点引用至新节点
        first = newNode;
        if (f == null)
            //代表空集合，空集合的头节点、尾节点相同，节点的prev\next均为null
            last = newNode;
        else
            //否则将原先头节点的prev指向新的头节点
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    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
            //设置原尾结点的next
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     * 将元素插入特定节点之前
     * 需要做四个链接更新
     * 1. 设置新节点的prev和next
     * 2. 设置succ的prev为新节点
     * 3. 设置succ的原prev节点的next节点为新节点
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //记录后继者的prev引用
        final Node<E> pred = succ.prev;
        //构造节点，指定prev为succ的prev，next为succ，
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 设置succ的prev引用，更新链接关系
        succ.prev = newNode;
        if (pred == null)
            //succ为原来的头节点，相当于此动作为设置新的头节点
            //更新first的引用
            first = newNode;
        else
            //更新succ的原prev节点的next链接
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Unlinks non-null first node 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
            last = null;
        else
            //将next的prev置为null，取消引用关系
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null last node l.
     * 去掉尾结点
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        //更新集合尾结点的引用
        last = prev;
        if (prev == null)
            //若集合为空，首尾节点相同，需将头节点设置为null
            first = null;
        else
            //集合尾结点的next为null，更新新的尾部节点的next链接关系
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null node x.
     * 去掉某个节点
     * 1. 设置x的item prev next为null， help GC
     * 2. 设置x的prev节点的next为x的next节点
     * 3. 设置x的next节点的prev为x的prev节点
     */
    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;
        //[prev item next] [prev item next] [prev item next]
        if (prev == null) {
            //节点的prev引用为空，则可认为是头节点，此时需更新集合的first引用
            first = next;
        } else {
            //设置x的prev节点的next为x的next节点
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            //节点的next引用为空，则可认为是尾节点，此时需更新集合的next引用
            last = prev;
        } else {
            //设置x的next节点的prev为x的prev节点
            next.prev = prev;
            x.next = null;
        }
        //help gc
        x.item = null;
        size--;
        modCount++;
        return element;
    }