06、LinkedList

结构

1. LinkedList内部是一个链表的实现，每个节点除了保存自身数据外，还需要维护指向前、后节点的引用
2. 从存储结构上来说，相较于ArrayList的数组来说，LinkedList更耗空间
3. 删除、插入速度比较快；查询（除头节点、尾节点外）需要遍历，速度较慢

1. 实现Iterable接口，支持for-each迭代器
2. 实现List接口，元素有序、可重复
3. 实现Deque（双向队列）接口，支持双向操作
4. 实现Serializable接口，支持序列化和反序列化
5. 实现Cloneable接口，支持克隆
6. 没实现RandomAccess接口，不能支持快速的随机访问

    transient int size = 0;
    /**
     * 头节点
     *     规定：(first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * 尾节点
     *     规定：(first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
    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;
        }
    }

创建

    // 构造一个空列表
    public LinkedList() {
    }
    // 构造一个列表，该列表包含指定集合的元素，其顺序由集合的迭代器返回
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

add

add(e)

将指定的元素增加到列表末尾

    // 将指定的元素增加到列表末尾
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    // 将节点e作为最后一个节点链接到列表上
    void linkLast(E e) {
        final Node<E> l = last;
        // 创建一个以e为item属性、原先的last节点为prev的属性创建一个链表节点
        final Node<E> newNode = new Node<>(l, e, null);
        // last赋值为该新建节点
        last = newNode;
        // 原先的last节点为null，说明列表中没有元素
        if (l == null)
            // 头节点、尾节点都是这个新建节点
            first = newNode;
        else // 原先的last节点不为null，说明列表中已存在元素
            // 原先的尾节点指向新建节点，新建节点变成尾节点
            l.next = newNode;
        // 列表实际元素数目+1
        size++;
        // 列表修改次数+1
        modCount++;
    }

add(index,e)

指定位置插入元素，逻辑上该位置及之后的元素向后移

    public void add(int index, E element) {
        // 范围检查，校验index是否越界
        checkPositionIndex(index);
        // 插入位置为尾部
        if (index == size)
            // 将节点element作为最后一个节点链接到列表上
            linkLast(element);
        else // 插入位置不是尾部
            // index位置前插入element元素
            linkBefore(element, node(index));
    }
    // 在非空节点succ之前插入元素e
    void linkBefore(E e, Node<E> succ) {
        // pred赋值为succ节点的前置节点
        final Node<E> pred = succ.prev;
        // 新建一个节点，该节点的前置节点是succ节点的前置节点，后置节点是succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        // succ的前置节点设置为新建节点
        succ.prev = newNode;
        // 原先succ前置节点为空，表示succ之前是头节点
        if (pred == null)
            // 设置新建节点为头节点
            first = newNode;
        else // 原先succ不是头节点
            // 原先succ的前置节点pred的后置节点设置为新建节点
            pred.next = newNode;
        // 列表实际长度+1
        size++;
        // 修改次数+1
        modCount++;
    }

get

返回列表中指定位置的元素

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    // 返回指定元素索引处的(非空)节点
    Node<E> node(int index) {
        // 断言index是列表元素索引
        // index小于列表实际长度的一半，从头部向后查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { // index大于等于实际长度的一半，从尾部向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

set

将列表中指定位置的元素替换为指定的元素

    // 将列表中指定位置的元素替换为指定的元素
    public E set(int index, E element) {
        // 范围检查，判断index是否越界
        checkElementIndex(index);
        // 找到index位置的节点
        Node<E> x = node(index);
        // 获取节点的旧值
        E oldVal = x.item;
        // 给节点赋新值
        x.item = element;
        // 返回节点的旧值
        return oldVal;
    }

remove

删除列表中指定位置的元素，将所有后续元素向左移。返回从列表中删除的元素

    // 删除列表中指定位置的元素，将所有后续元素向左移。返回从列表中删除的元素
    public E remove(int index) {
        // 范围检查，判断index是否越界
        checkElementIndex(index);
        // 从链表中解除index位置节点的链接关系
        return unlink(node(index));
    }
    // 从链表里删除第一次出现的指定元素
    public boolean remove(Object o) {
        // 要删除的元素是null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                // == 比较null
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else { // 要删除的元素不是null
            for (Node<E> x = first; x != null; x = x.next) {
                // 使用equals方法比较是否相同
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    // 从链表中解除非空节点x
    E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        // x节点前置节点为空，表示x节点是头节点
        if (prev == null) {
            // x节点后置节点设置为头节点
            first = next;
        } else { // x节点不是头节点
            // x的前置节点的后置节点设置为x的后置节点
            prev.next = next;
            // x的前置节点设置为null
            x.prev = null;
        }
        // x的后置节点是空，表示x是尾节点
        if (next == null) {
            // x的前置节点设置为尾节点
            last = prev;
        } else { // x不是尾节点
            // x的后置节点的前置节点设置为x的前置节点
            next.prev = prev;
            // x的后置节点设置为null
            x.next = null;
        }
        // x的值设置为null
        x.item = null;
        // 列表实际长度-1
        size--;
        // 修改次数+1
        modCount++;
        // 返回x节点被删除前的值
        return element;
    }

clear

从列表中删除所有元素。这个调用返回后，列表将为空（没有元素的列表）

    // 从列表中删除所有元素。这个调用返回后，列表将为空（没有元素的列表）
    public void clear() {
        /**
         * 清除节点之间的链表不是必要的，如果丢弃的节点占据了不止一代的内存，即使有一个可到达的迭代             * 器，清除节点之间关系这个操作就可以帮助分代GC
         *但是为了防止其他分代中存在指向这些节点的引用，
         * 导致GC无法回收，有必要将他们设置为null
         */
        // 从头节点开始遍历链表
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            // 节点信息置为null
            x.item = null;
            // 断开节点间的引用链接
            x.next = null;
            x.prev = null;
            // 下一个节点
            x = next;
        }
        // 头节点、尾节点置为null
        first = last = null;
        // 链表长度置为0
        size = 0;
        // 修改次数+1
        modCount++;
    }

疑问： 节点间引用关系不清除，直接将头节点、尾节点设置为null，这个链表也是不可达的啊，为什么还要清除节点间引用关系？

代码中的注释 Clearing all of the links between nodes is "unnecessary", but: helps a generational GC if the discarded nodes inhabit more than one generation is sure to free memory even if there is a reachable Iterator

翻译： 清除节点之间的链表不是必要的，如果丢弃的节点占据了不止一代的内存，即使有一个可到达的迭代器，清除节点之间关系这个操作就可以帮助分代GC 如图所示，如果对该List对象使用过ListItr（迭代器）对象，并且迭代到中间阻塞了，这时候栈中就会存在一个引用指向ListIter对象，这个对象中存在lastReturned指向链表中的一个Entry，这种情况，如果链表节点之间引用没有清除就会导致整个链表无法释放，不能被GC回收

linkFirst

    // 将节点e作为首节点链接到列表上
    private void linkFirst(E e) {
        final Node<E> f = first;
        // 创建一个前置节点为null、item为e、next指向原先头节点的新节点
        final Node<E> newNode = new Node<>(null, e, f);
        // 新节点设置成头节点
        first = newNode;
        // 原先头节点为null，表示链表为空
        if (f == null)
            // 新节点设置为尾节点
            last = newNode;
        else // 不是空链表
            // 原先头节点的前置节点设置为新节点
            f.prev = newNode;
        // 链表实际存储元素长度+1
        size++;
        // 修改次数+1
        modCount++;
    }