1.LinkedList介绍

我们除了最最常用的ArrayList之外，还有LinkedList，这到底是什么东西？从LinkedList官方文档，我们可以了解到，它其实是实现了List和Queue的双向链表结构，而ArrayList底层则是数组结构。

下面的讲解基于jdk 1.8:

继承了AbstractSequentialList，实现了List,Queue,Cloneable,Serializable，既可以当成列表使用，也可以当成队列，堆栈使用。主要特点有：

• 线程不安全，不同步，如果需要同步需要使用List list = Collections.synchronizedList(new LinkedList());
• 实现List接口，可以对它进行队列操作
• 实现Queue接口，可以当成堆栈或者双向队列使用
• 实现Cloneable接口，可以被克隆，浅拷贝
• 实现Serializable，可以被序列化和反序列化

下面是LinkedList的结构，注意：指针结束指向的是node，开始的是prev或者next

源码定义如下：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    }

2.成员变量

成员变量相对比较简单，因为不像ArrayList一样，需要使用数组保存元素，LinkedList是靠引用来关联前后节点，所以这里只有大小，第一个节点，最后一个节点,以及序列化的uid。

    // 大小
    transient int size = 0;
    // 第一个节点
    transient Node<E> first;
    // 最后一个节点
    transient Node<E> last;
		// 序列化uid
    private static final long serialVersionUID = 876323262645176354L;

我们来看看Node到底是何方神圣？
其实就是内部类，里面的item是真正保存节点的地方，next是下一个节点的引用，prev是上一个节点的引用。这里也体现了LinkedList其实就是双线链表。

只有一个构造函数，三个参数分别对应三个属性。

    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;
        }
    }

3. 构造函数

构造函数有两个，一个是无参数构造函数，另一个是初始化集合元素，里面调用的其实是addAll，一看就是将里面所有的元素加入到集合中。

    public LinkedList() {
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

4. 常用List方法解析

4.1 查找相关

4.1.1 getFirst()

获取第一个元素：

    public E getFirst() {
        // 保存第一个元素为f，注意是final的，
        final Node<E> f = first;
        if (f == null)
            // 如果没有第一个元素，那么就会抛出异常
            throw new NoSuchElementException();
        // 返回第一个元素的item
        return f.item;
    }

4.1.2 getLast()

获取最后一个元素,和获取第一个的原理差不多

    public E getLast() {
        // 保存最后一个元素的引用为l
        final Node<E> l = last;
        // 如果为空，抛出错误
        if (l == null)
            throw new NoSuchElementException();
        // 返回item
        return l.item;
    }

4.1.3 get(int index)

通过索引来获取元素,里面是调用了另外一个方法先获取节点，再获取该节点的item,在此之前，做了index安全性校验。

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

在????上面的代码中调用了通过索引位置查找节点位置的函数，下面我们来分析一下这个函数,由于底层是链表实现的，所以呢？遍历起来不是很方便，就考虑到位运算，如果索引位置在后面一半，就从后往前遍历查找，否则从前往后遍历。

    Node<E> node(int index) {
        // assert isElementIndex(index);
				// size>>1 表示除以2，相当于index小于size的一半
        if (index < (size >> 1)) {
          	// 从前面开始遍历，取出first节点，因为中间过程引用会变化，所以不可直接操作first
            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;
        }
    }

4.1.4 indexOf(Object o)

查找某一个元素的索引位置,分为两种情况讨论，如果要查找的元素为空，那么就使用==，否则使用equals()，这也从侧面印证了LinedList实际上是可以存储null元素的。使用计数查找：

    public int indexOf(Object o) {
        int index = 0;
      	// 如果需要查找null元素
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
          	// 查找元素不为空
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

4.1.5 lastIndexOf(Object o)

和前面的indexOf差不多，区别就是这个是后面开始查找，找到第一个符合的元素。

    public int indexOf(Object o) {
        int index = 0;
      	// 查找元素
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

4.2 添加元素

4.2.1 addFirst(E e)

将元素e，添加到第一个节点，公有方法是addFirst()，但是其实内部调用是linkFirst()，这是private方法。

    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        // 先保存第一个节点
        final Node<E> f = first;
        // 初始化一个新节点，prev是null，next是f（之前的首节点）
        final Node<E> newNode = new Node<>(null, e, f);
        // 更新first为新节点
        first = newNode;
        // 如果之前的第一个节点是空的，那么就说明里面是空的，没有元素
        if (f == null)
            // 最后一个元素也是新加入的元素
            last = newNode;
        else
            // f的prev前置节点的引用更新为新的节点
            f.prev = newNode;
        // 个数增加
        size++;
        // 修改次数增加
        modCount++;
    }

4.2.2 addLast(E e)

将元素添加在链表最后，其实内部也是直接调用的private方法linkLast():

    public void addLast(E e) {
        linkLast(e);
    }
    void linkLast(E e) {
        // 保存最后一个节点的引用
        final Node<E> l = last;
        // 初始化一个节点，前置节点指针引用指向之前的最后一个节点，后续节点的引用是null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将最后一个节点更新
        last = newNode;
        // 如果之前的最后一个节点是null，说明链表是空的
        if (l == null)
            // 新节点同时是第一个节点
            first = newNode;
        else
            // 否则之前的最后一个节点的后续节点引用更新为新的节点
            l.next = newNode;
        // 大小+1
        size++;
        // 修改次数+1
        modCount++;
    }

4.2.3 add(E e)

增加元素，默认也是在链表的最后添加，完成返回true：

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

4.2.4 addAll(Collection

往链表里面批量添加元素,里面默认是在最后面批量添加，内部调用的是addAll(int index, Collection,添加之前会判断索引位置是不是合法的。
然后查找需要插入的位置的前后节点，循环插入。

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查添加位置
        checkPositionIndex(index);

        // 将需要添加的集合转换成为数组
        Object[] a = c.toArray();
        // 获取数组的大小
        int numNew = a.length;
        // 如果数组长度为0，说明没有需要添加的元素，返回false
        if (numNew == 0)
            return false;

        // 插入位置的前节点和后续节点
        Node<E> pred, succ;
        // 如果插入位置索引大小等于链表大小，那么就是在最后插入元素
        if (index == size) {
            // 最后插入元素没有后续节点
            succ = null;
            // 前一个节点就是之前的最后一个节点
            pred = last;
        } else {
            // 查找到索引为index 的节点
            succ = node(index);
            // 获取前一个节点
            pred = succ.prev;
        }
        
        // 循环插入节点
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            // 初始化新节点，上一个节点是pred
            Node<E> newNode = new Node<>(pred, e, null);
            // 如果前一个节点是null，那么第一个节点就是新的节点
            if (pred == null)
                first = newNode;
            else
                // 否则pred的next置为新节点
                pred.next = newNode;
            pred = newNode;
        }

        // 如果插入位置没有后续节点，也就是succ为null
        if (succ == null) {
            // 最后一个节点也就是pred，刚刚插入的新节点
            last = pred;
        } else {
            // 加入所有元素之后的最后一个节点的下一个节点指向succ（后续元素）
            pred.next = succ;
            // 插入位置的后续元素的上一个节点引用指向pred
            succ.prev = pred;
        }
      	// 大小改变
        size += numNew;
      	// 修改次数增加
        modCount++;
        return true;
    }

上面的代码调用了node(index)，这个在前面查找的时候已经说过了，不再解释。

4.2.5 addAll(int index, Collection

在指定位置批量插入节点：

    public boolean addAll(int index, Collection<? extends E> c) {
      	// 检查索引合法性
        checkPositionIndex(index);
      	// 将需要插入的集合转换成为数组
        Object[] a = c.toArray();
      	// 数组的长度
        int numNew = a.length;
      	// 为0则不需要插入
        if (numNew == 0)
            return false;
      	// 插入位置的前节点和后节点
        Node<E> pred, succ;
      	// 如果在最后插入
        if (index == size) {
          	// 后节点为空
            succ = null;
          	// 前节点是最后一个
            pred = last;
        } else {
          	// 获取插入位置的后节点
            succ = node(index);
          	// 获取前节点
            pred = succ.prev;
        }
				
      	// 遍历
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
          	// 初始化节点，前置节点是插入位置的前节点，后续节点为null
            Node<E> newNode = new Node<>(pred, e, null);
          	// 如果插入位置前一个节点是null，说明插入位置是链表首
            if (pred == null)
              	// 首节点就是新插入的节点
                first = newNode;
            else
              	// 前节点的next指向新节点
                pred.next = newNode;
          	// 更新插入位置的前一个节点
            pred = newNode;
        }
      	// 如果插入位置的后一个节点为空，说明插入位置是链表尾部
        if (succ == null) {
          	// 最后一个元素就是插入的元素
            last = pred;
        } else {
          	// 将插入的最后一个元素next指向succ
            pred.next = succ;
          	// succ的上一个元素指向prev
            succ.prev = pred;
        }
      	// 大小更新
        size += numNew;
      	// 修改次数改变
        modCount++;
      	// 返回成功
        return true;
    }

4.2.6 add(int index,E element)

将元素插入在指定位置,先判断索引位置，如果索引位置是最后一个，那么直接调用在最后添加元素函数即可，否则需要调用另外一个函数，在某个元素前面插入：

    public void add(int index, E element) {
      	// index校验
        checkPositionIndex(index);
      	
      	// 索引等于链表大小
        if (index == size)
          	// 直接在最后插入元素
            linkLast(element);
        else
          	// 在某个节点前插入元素
            linkBefore(element, node(index));
    }

4.3 删除元素

4.3.1 removeFirst()

删除第一个节点，先获取首节点，判断第一个节点是不是为空，如果为空则证明没有该节点，抛出异常，内部调用的其实是unlinkFirst()。返回值是被移除的节点里面的数值。

    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;
      	// 将之前的首节点前后节点引用置空，有利于GC
        f.item = null;
        f.next = null; // help GC
      	// 首节点更新
        first = next;
      	// 如果首节点是空的，那么链表没有元素了，最后一个节点自然也是null
        if (next == null)
            last = null;
        else
          	// 否则当前的第一个节点的前置节点置null
            next.prev = null;
      	// 链表大小-1
        size--;
      	// 修改次数增加
        modCount++;
        return element;
    }

4.3.2 removeLast()

删除最后一个节点，和上面的删除首节点差不多，先取出最后一个节点，判断是否为空，如果为空则抛出异常，否则会调用另一个解除连接的函数unLinkLast()。

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
      	// 保存被移除的节点的item
        final E element = l.item;
      	// 获取上一个节点
        final Node<E> prev = l.prev;
      	// 前后引用置空，有利于垃圾回收
        l.item = null;
        l.prev = null; // help GC
      	// 更新最后一个节点
        last = prev;
      	// 如果前置节点为空，那么链表已经没有元素了
        if (prev == null)
            first = null;
        else
          	// 否则将上一个节点的next置null
            prev.next = null;
      	// 大小该表
        size--;
      	// 修改次数增加
        modCount++;
      	// 返回被移除的节点的item值
        return element;
    }

4.3.3 remove(Object o)

删除某个元素分为两种情况，元素为null和非null,直接遍历判断，里面真正删除的方法其实是unlink(E e)，成功移除则返回true，注意这里只会移除掉第一个，后续要是还有该节点，不会移除。

    public boolean remove(Object o) {
      	// 元素为null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
          	// 元素不为null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                  	// 移除节点
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

unLink(E e)方法如下：

    E unlink(Node<E> x) {
        // assert x != null;
      	// 保存被移除节点的item
        final E element = x.item;
      	// 下一个节点
        final Node<E> next = x.next;
      	// 上一个节点
        final Node<E> prev = x.prev;
      	// 如果前置节点为空，那么首节点就是当前节点了
        if (prev == null) {
            first = next;
        } else {
          	// 前一个节点的next置为下一个节点
            prev.next = next;
          	// 之前的节点的前一个节点置null
            x.prev = null;
        }
      	// 如果next是空的，那么上一个节点就是现在最后一个节点
        if (next == null) {
            last = prev;
        } else {
          	// next的上一个节点引用指向prev
            next.prev = prev;
          	// 被删除的元素的next置空
            x.next = null;
        }
      	// item置空
        x.item = null;
      	// 大小改变
        size--;
      	// 修改次数增加
        modCount++;
      	// 返回被删除的节点里面的item
        return element;
    }

4.3.4 clear()

移除里面所有的元素：

    public void clear() {
        // 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
        for (Node<E> x = first; x != null; ) {
          	// 保存下一个
            Node<E> next = x.next;
          	// 当前元素置空
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
      	// 首节点和尾节点全部置null
        first = last = null;
        size = 0;
        modCount++;
    }

4.3.5 remove（int index）

移除指定索引的元素。先通过索引找到节点，再移除指定的节点

    public E remove(int index) {
      	// 检查合法性
        checkElementIndex(index);
      	// 先找到节点，再移除指定节点
        return unlink(node(index));
    }

4.4 更新元素

4.4.1 set(int index,E element)

更新指定索引的位置的元素,首先通过索引查找到该元素，然后修改item值，返回旧的item值。

    public E set(int index, E element) {
      	// 检查索引是否合法
        checkElementIndex(index);
      	// 通过索引查找到节点
        Node<E> x = node(index);
      	// 保存旧的值
        E oldVal = x.item;
      	// 修改
        x.item = element;
      	// 返回旧的元素
        return oldVal;
    }

5 queue相关的方法

因为LinkedList也实现了queue接口，所以它肯定也实现了相关的方法，下面我们看看：

5.1 peek()

获取队列第一个元素：

    public E peek() {
      	// 拿到第一个元素，final不可变
        final Node<E> f = first;
      	// 返回item值
        return (f == null) ? null : f.item;
    }

5.2 element()

也是获取队列第一个元素，里面调用的是getFirst()。

    public E element() {
        return getFirst();
    }

5.3 poll()

移除队列第一个节点元素并返回，里面调用的其实是unlinkFirst()

    public E poll() {
      	// 获取到第一个元素
        final Node<E> f = first;
      	// 移除并返回
        return (f == null) ? null : unlinkFirst(f);
    }

5.4 remove()

移除队列第一个元素,里面调用的是removeFirst():

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

5.5 offfer(E e)

在队列后面增加元素：

    public boolean offer(E e) {
        return add(e);
    }

5.6 offerFirst(E e)

往队列的前面插入元素，其实调用的是addFirst()

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

5.7 offerLast(E e)

往队列的后面添加元素,其实调用的是addList()

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

5.8 peekFirst()

获取第一个节点里面的元素:

    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

5.9 peekLast()

获取最后一个节点的元素：

    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

5.10 pollFirst()

获取第一个元素，并且移除它,使用的是unlinkFirst(E e)

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

5.11 pollLast（）

获取队列最后一个元素，并且移除它,调用的其实是unlinkLast(E e)

    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

5.12 push(E e)

像是堆栈的特点，在前面添加元素：

    public void push(E e) {
        addFirst(e);
    }

5.13 pop()

堆栈的特点，取出队列首的第一个元素

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

5.14 removeFirstOccurrence(Object o)

移除元素,从前往后第一次出现的地方移除掉：

    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

5.15 removeLastOccurrence（Object o）

移除元素，最后一次出现的地方移除掉,和前面分析的一样，分为两种情况，null和非null。

    public boolean removeLastOccurrence(Object o) {
      	// 元素为null
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
          	// 元素不是null
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

6.其他方法

是否包含某个元素,其实调用的是indexOf()方法，如果返回的索引不为-1，则包含：

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

返回大小：

    public int size() {
        return size;
    }

是否为有效元素下标索引，从0到size-1

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

是否为有效位置索引，从0到size

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

获取指定索引位置的ListIterator:

    public ListIterator<E> listIterator(int index) {
      	// 检查合法性
        checkPositionIndex(index);
        return new ListItr(index);
    }

获取倒序的迭代器:

    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

拷贝克隆函数,一个是父类的克隆函数，另一个是重写的克隆函数，这里比较特殊，因为LinkedList是链表，本身只保存了第一个和最后一个的引用，所以拷贝的时候需要向里面添加元素的方式进行拷贝。

    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // 添加元素到拷贝的队列中
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }
    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

转换成为数组，通过循环实现

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
      	// 循环实现
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

转换成为指定类型的数组,和前面不同的是，这里初始化的时候使用类型反射创建(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size)

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

获取可分割迭代器：

    public Spliterator<E> spliterator() {
        return new LLSpliterator<E>(this, -1, 0);
    }

7.迭代器

里面定义了三种迭代器，都是以内部类的方式实现，分别是：

• ListItr：列表的经典迭代器
• DescendingIterator：倒序迭代器
• LLSpliterator：可分割迭代器

7.1 ListItr

先来说说ListItr，这个迭代器主要是有next(),hashNext(),hasPrevious(),previous(),nextIndex(),previousIndex(),remove(),set(),add(),forEachRemaining()方法：

• next()：获取下一个元素
• hashNext():是否有下一个元素
• hasPrevious()：是否有上一个元素
• previous()：上一个元素
• nextIndex()：下一个索引位置
• previousIndex()：上一个索引位置
• remove()：删除当前索引位置的元素
• set()：更新元素
• add()：新增元素
• forEachRemaining()：遍历剩下的元素

里面主要有集合重要的属性：

• lastReturned:上一次返回的元素
• next：下一个返回的元素
• nextIndex：下一个索引
• expectedModCount：期待修改的次数

    private class ListItr implements ListIterator{
      	// 上一个返回的元素
        private NodelastReturned;
      	// 下一个元素
        private Nodenext;
      	// 下一个索引
        private int nextIndex;
      	// 期待的修改次数
        private int expectedModCount = modCount;
      	
      	// 初始化
        ListItr(int index) {
            // 根据索引位置更新下一个返回的节点
            next = (index == size) ? null : node(index);
          	// 更新索引
            nextIndex = index;
        }
      	// 是否有下一个元素：索引是否小于size
        public boolean hasNext() {
            return nextIndex < size;
        }
      	// 获取下一个元素
        public E next() {
          	// 检查修改合法化
            checkForComodification();
          	// 如果没有下一个元素会抛异常，所以使用前需要先判断
            if (!hasNext())
                throw new NoSuchElementException();
          	// 上一次返回的元素更新
            lastReturned = next;
          	// 更新下一次返回的元素
            next = next.next;
          	// 更新索引
            nextIndex++;
          	// 返回item
            return lastReturned.item;
        }
      
      	// 是否有上一个：下一个返回的元素索引是不是大于0
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
      	// 返回上一个元素
        public E previous() {
          	// 检查
            checkForComodification();
          	// 判断是否有上一个元素  
          	if (!hasPrevious())
                throw new NoSuchElementException();
          	// 上一个返回的元素，需要更新
            lastReturned = next = (next == null) ? last : next.prev;
            // 更新索引
          	nextIndex--;
            return lastReturned.item;
        }
      	// 下一个索引
        public int nextIndex() {
            return nextIndex;
        }

      	// 上一个索引
        public int previousIndex() {
            return nextIndex - 1;
        }
	
      	// 移除当前位置的索引
        public void remove() {
          	// 检查修改合法性
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
						// 获取下一个元素
            NodelastNext = lastReturned.next;
          	// 移除上一个返回的元素
            unlink(lastReturned);
          	// 如果下一个是上次返回的元素，那么下一个元素需要更新，因为该元素已经被移除了
            if (next == lastReturned)
                next = lastNext;
            else
              	// 更新索引
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

      	// 更新
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
          	// 如果下一个元素是空，那就是在队尾添加元素
            if (next == null)
                linkLast(e);
            else
              	// 否则就是在next索引处添加元素
                linkBefore(e, next);
          	// 更新索引
            nextIndex++;
            expectedModCount++;
        }
				
      	// 遍历剩下的元素
        public void forEachRemaining(Consumer action) {
            Objects.requireNonNull(action);
          	// 使用循环，索引不断后移，遍历
            while (modCount == expectedModCount && nextIndex < size) {
              	// 对每个节点元素执行操作
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

上面的迭代器没有什么好说的，就是往前面和后面遍历的功能，以及增删改的功能。

7.2 DescendingIterator

这个迭代器有点意思，也很简单，就是一个倒序的功能，功能实现也十分简单：

• hasNext:是否有下一个元素，实际上是判断上一个元素
• next：获取下一个元素，实际上是获取前面一个元素
• remove：移除元素

倒序就是别人从前往后，它偏偏从后往前遍历，emmmmmmm

    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();
        }
    }

7.3 LLSpliterator

这个迭代器有点东西，感觉和其它的不太一样，LLSpliterator是在使用node的next进行迭代，下面分析一下：主要是为了将元素分为多份，然后再用多线程来处理。

值得注意的是：分割的时候，LinkedList不是1/2分割，而是每一次分割出来的大小都是递增的，递增的大小是BATCH_UNIT,但是返回的不是LLSpliterator，而是ArraySpliterator，每次都分割出更多的元素，转成数组结构，这也许是出自于性能考虑，比较指针遍历太慢了，我猜的的…别打我

    static final class LLSpliterator<E> implements Spliterator<E> {
      	// 分割长度增加单位
        static final int BATCH_UNIT = 1 << 10;  // batch array size increment
      	// 最大分割长度
        static final int MAX_BATCH = 1 << 25;  // max batch array size;
        final LinkedList<E> list; // null OK unless traversed
      	// 当前节点
        Node<E> current;      // current node; null until initialized
      	// 大小估算
        int est;  
      	// 期待修改的次数
        int expectedModCount; // initialized when est set
      	// 分割长度
        int batch;            // batch size for splits

        LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
            this.list = list;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getEst() {
            int s; // force initialization
            final LinkedList<E> lst;
            if ((s = est) < 0) {
                if ((lst = list) == null)
                    s = est = 0;
                else {
                    expectedModCount = lst.modCount;
                    current = lst.first;
                    s = est = lst.size;
                }
            }
            return s;
        }
				// 估算大小
        public long estimateSize() { return (long) getEst(); }

      	// 分割
        public Spliterator<E> trySplit() {
            Node<E> p;
          	// 获取大小
            int s = getEst();
          	// 当前节点不为空
            if (s > 1 && (p = current) != null) {
              	// 分割位置结束：分割位置+分割单位
                int n = batch + BATCH_UNIT;
              	// 如果大于大小，就限制最后的位置
                if (n > s)
                    n = s;
              	// 最大的分割位置
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
              	// 数组
                Object[] a = new Object[n];
                int j = 0;
              	// 将当前位置到n的位置循环，存放到a数组中
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
              	// ArraySpliterator每次分割成一半一半，而IteratorSpliterator算术递增
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

      	// 对剩下的元素进行处理
        public void forEachRemaining(Consumer<? super E> action) {
            Node<E> p; int n;
            if (action == null) throw new NullPointerException();
            if ((n = getEst()) > 0 && (p = current) != null) {
                current = null;
                est = 0;
                do {
                    E e = p.item;
                    p = p.next;
                    action.accept(e);
                } while (p != null && --n > 0);
            }
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

      	// 对后面一个元素进行处理
        public boolean tryAdvance(Consumer<? super E> action) {
            Node<E> p;
            if (action == null) throw new NullPointerException();
            if (getEst() > 0 && (p = current) != null) {
                --est;
                E e = p.item;
                current = p.next;
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }

        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

8.序列化和反序列化

序列化和反序列化的时候，需要重写，因为我们保存的只有第一个和最后一个节点的引用，我们序列化需要保存大小和引用，所以需要重写，要不反序列化回来就找不到next，节点之间的关系就会丢失。

序列化的时候如下，写入了size，以及遍历的时候将节点的item值写入。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

反序列化的时候，读入大小size以及每个节点里面的元素item

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 默认序列化
        s.defaultReadObject();

        // 大小
        int size = s.readInt();

        // 按照顺序读入元素
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

9.总结一下

• LinkedList底层是用链表实现的，而且是双向链表，并且实现了Queue接口，可以当成双向队列或者堆栈来使用。也正是因为是链表实现，所以删除元素比较快，但是查找的时候相对较慢。当然，也没有什么扩容，除非就是内存不够了。

• 双向链表，可以从头往尾遍历，也可以从尾部往前遍历。

• LinkedList继承了AbstractSequentialList，AbstractSequentialList实现了get,set,add,remove等方法。

• 序列化/反序列化的时候重写了方法，才能达到序列化里面每一个节点元素的效果。

• 线程不安全

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。这个世界希望一切都很快，更快，但是我希望自己能走好每一步，写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~