JDK源码分析——LinkedList

基础概念

• 首先，它是一个双向链表，但不是线程安全的。
• 实现了List和Deque两个接口，实现所有可选的List操作，并允许所有元素(包括null元素)。
• 迭代器iterator、list-iterator是基于快速失败的。

成员变量

因为是一个双向链表，所以它有需要有两个节点：

• first，头结点
• last，尾节点

其他的一些继承自父类的成员变量：

• size，当前LinkedList中存储元素的大小，由于LinkedList是链表形式，每次插入容量自动+1，所以不存在存储的概念。
• modCount，结构性修改计数器。

结构性修改

泛指添加或删除一个或多个元素的任何操作，仅设置元素的值并不是结构性修改

快速失败

如果list在迭代器创建后的任何时候发生了结构性修改，除了迭代器本身自带的remove()和add()方法，其他方法改变了list的结构性，那么迭代器就会抛出一个ConccurrentModificationException的异常。

迭代器的快速失败行为无法得到保证，通常来讲，在存在不同步的并发修改的情况下，不可能做出任何严格的保证。

快速失败的迭代器实现尽量抛出ConcurrentModificationException异常。

基础对象

作为一个双向链表，存储的是每一个对象是一个节点，LinkedList中的静态内部类Node是节点对象的实现：

/**
 * 链表中节点对象
 * @param <E> 链表运行时类型
 */
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;
    }
}

Node类声明中定了三种属性：

• iterm，节点需要存储的元素。
• next，当前节点指向下一个节点的指针。
• prev，当前节点指向上一个节点的指针。

核心方法

获取元素

node(int index)

node(int index)用于获取给定索引位置的非null节点对象。

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

1. 首先，判断给定索引的大小，以当前LinkedList中元素个数的½为界限，判断是从头部还是尾部开始查。
2. 从头部或者尾部开始进行遍历，直到找到对应的索引位置。
3. 返回给定索引位置的节点对象。

添加元素

linkFirst(E e)

linkFirst(E e)是将给定元素插入到当前LinkedList的头部。

private void linkFirst(E e) {
    final Node<E> f = first;
    // 创建新first节点，first节点没有前置节点，后继节点是当前链表的first节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 更换LinkedList中first节点全局变量
    first = newNode;
    if (f == null) {
        // 如果之前链表中没有first节点，那么新创建的节点也是last节点
        last = newNode;
    } else
        // 否则，修改前first节点的前置节点为当前新的first节点
        f.prev = newNode;
    // 增加链表大小和更新次数
    size++;
    modCount++;
}

1. 使用”iterm=给定元素，next=当前first节点“创建新的节点对象。
2. 将first节点指针指向新创建的节点，前一个first节点的前置节点置为新创建的节点。
3. 如果插入前，LinkedList中没有first节点，那么新创建的节点同时也是LinkedList的last节点。

linkLast(E e)

linkLast(E e)是将给定元素插入到当前LinkedList的尾部。

void linkLast(E e) {
    // 获取当前的last节点
    final Node<E> l = last;
    // 创建新的last节点，last节点的前置节点是当前的last节点，新节点没有后继节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 更换LinkedList中last节点全局变量
    last = newNode;
    if (l == null)
        // 如果之前链表中没有last节点，则新创建的last节点也是first节点
        first = newNode;
    else
        // 否则，修改钱last节点的后继节点是当前新的last节点
        l.next = newNode;
    // 增加元素个数和更新次数
    size++;
    modCount++;
}

1. 使用”term=给定元素，previous=当前tail节点“创建新的节点对象。
2. 将last节点指向新创建的节点，前一个last节点的后继节点为新创建的节点。
3. 如果在插入前，LinkedList没有last节点，那么新创建的节点同时也是first节点。

linkBefore(E e, Node succ)

linkBefore(E e, Node succ)用于在给定节点之前插入给定元素。

void linkBefore(E e, Node<E> succ) {
    // 获取给定节点的前置节点
    final Node<E> pred = succ.prev;
    // 使用给定节点及它的前置节点和给定的元素值创建一个新的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将给定节点的前置节点变更为创建的新节点
    succ.prev = newNode;
    if (pred == null)
        // 如果给定节点的前置节点为null，则插入的位置是first节点，变更first节点的指针指向
        first = newNode;
    else
        //否则给定节点的前置节点的指针指向新创建的节点
        pred.next = newNode;
    // 增加元素个数和更新次数
    size++;
    modCount++;
}

1. 获取给定节点的前置节点。
2. 使用”previous=给定节点的前置节点，iterm=给定元素，next=给定节点“，创建一个新节点。
3. 将给定节点的前置节点置为新创建的节点。
4. 如果给定节点的前置节点为null，则插入的位置first节点位置，直接将新创建的节点置为first节点。
5. 否则正常情况下，给定节点的前置节点的指针指向新创建的节点。
6. 增加元素的个数和更新次数。

移除元素

unlinkFirst(Node f)

unlinkFirst(Node f)用于释放当前first节点，相当于将当前first节点的后继节点置为first节点。

private E unlinkFirst(Node<E> f) {
    // 获取移除的first节点的元素和next节点
    final E element = f.item;
    final Node<E> next = f.next;
    // 将元素和后继节点指针置为null，帮助GC
    f.item = null;
    f.next = null;
    // 将要移除的first节点的后继节点置为first节点
    first = next;
    if (next == null)
        // 如果要移除的first节点没有后继节点，则要移除的first节点也是last节点，将last节点直接置为null
        last = null;
    else
        // 否则，将要移除的first节点的后继节点的前置节点置为null
        next.prev = null;
    // 减少节点个数和更新次数
    size--;
    modCount++;
    return element;
}

1. 获取要移除的first节点的元素和next节点。
2. 将要移除的first节点的元素和next节点指针置为null，帮助GC。
3. 如果当前要移除的first节点没有后继节点，则要移除的first节点同时也是last节点，直接将last节点置为null。
4. 否则，将要移除的first节点的后继节点的前置节点置为null，因为first节点是没有前置节点的。
5. 减少LinkedList节点个数和更新次数。
6. 返的元素。

为什么置为null方便进行GC，可达性分析不会做吗？

当仍有list-iterator等迭代器对LinkedList进行遍历时，即使释放掉了节点，list-iterator中仍存有指向此节点的引用，所以将节点属性置为null，仍可帮助GC。

unlinkLast(Node f)

unlinkLast(Node f)用于释放当前的last节点，相当于将当前last节点的前置节点置为last节点。

private E unlinkLast(Node<E> l) {
    // 获取移除的last节点的元素和前置节点
    final E element = l.item;
    final Node<E> prev = l.prev;
    // 将要移除的last节点的元素和前置节点置为null，帮助GC
    l.item = null;
    l.prev = null;
    // 将要移除的last节点的前置节点置为last节点
    last = prev;
    if (prev == null)
        // 如果要移除的last节点没有前置节点，则要移除的last节点是first节点，置为null
        first = null;
    else
        // 否则，将要移除的last节点的前置节点的后继节点置为null
        prev.next = null;
    // 减少节点大小和更新次数
    size--;
    modCount++;
    return element;
}

1. 获取移除的last节点的元素和前置节点。
2. 将要移除的last节点的元素和前置节点置为null，帮助GC。
3. 将要移除的last节点的前置节点置为last节点。
4. 如果要移除的last节点没有前置节点，则要移除的last节点同时也是first节点，直接将first节点置为null。
5. 否则，将要移除的last节点的前置节点的后继节点置为null，因为last节点是没有后继节点的。
6. 减少LinkedList节点个数和更新次数。
7. 返回移除的first节点的元素。

unlink(Node x)

unlink(Node x)用于移除LinkedList中的节点，也可以删除first、last节点。

E unlink(Node<E> x) {
    // 获取给定节点的元素、前置节点和后继节点
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // 如果给定节点的前置节点为null，那么给定节点为first节点，移除后，first节点需要指向给定节点的next节点
    if (prev == null) {
        first = next;
    } else {
        // 否则正常情况下，需要将给定节点的前置节点的后继节点指针指向给定节点的后继节点
        prev.next = next;
        x.prev = null;
    }
    // 如果给定节点的后继节点为null，那么给定节点为last节点，移除后，last节点需要指向给定节点的前置节点
    if (next == null) {
        last = prev;
    } else {
        // 否则正常情况下，需要将给定节点的后继节点的前置节点指针指向给定节点的前置节点
        next.prev = prev;
        x.next = null;
    }
    // 将给定节点的元素属性置为null，帮助GC
    x.item = null;
    // 减少节点个数和更新次数
    size--;
    modCount++;
    return element;
}

1. 获取给定节点的元素、前置节点和后继节点。
2. 针对前置节点：
   1. 如果给定节点的前置节点为null，则给定节点为first节点，移除给定节点，则first节点指针需要指向给定节点的后继节点。
   2. 正常情况下，给定节点的前置节点的后继节点指针需要指向给定节点的后继节点。
3. 针对后继节点：
   1. 如果给定节点的后继节点为null，则给定节点为last节点，移除给定节点，则last节点指针需要指向给定节点的前置节点。
   2. 正常情况下，给定节点的后继节点的前置节点指针需要指向给定节点的前置节点。
4. 将给定节点的所有元素属性置为null，帮助GC。
5. 减少LinkedList元素个数和更新次数。
6. 返回移除节点的元素。

基础方法

校验方法

checkPositionIndex(int index)

checkPositionIndex(int index)用于校验给定索引在LinkedList中的合法性，给定的索引需要满足以下条件：

• 自然数。
• 不能超过当前LinkedList的元素个数。

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

checkElementIndex(int index)

checkElementIndex(int index)用与给定索引是否在LinkedList的存储元素范围内，给定的元素需要满足一下条件：

• 自然数。
• 小于当前LinkedList的元素个数（也就是[0, size – 1]）。

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        // 抛出索引溢出异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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

checkPositionIndex(int index)和checkElementIndex(int index)并不是两个功能相同的方法。

• checkElementIndex(int index)用于判定给定索引是否属于LinkedList的索引范围。
• checkPositionIndex(int index)用于判定给定索引是否属于LinkedList的合法范围。

添加元素

add(E e)

add(E e)用于追加给定元素到LinkedList的尾部。

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

底层调用的是LinkedList#linkLast(e)方法

add(indx, E element)

add(indx, E element)用于向LinkedList中的给定位置插入给定元素，当前给定位置及以后的元素向右移动一位，即索引+1。

public void add(int index, E element) {
    // 校验索引在当前LinkedList的合法性
    checkPositionIndex(index);
    // 如果插入的索引恰好位于当前LinkedList的尾部，直接在list尾部追加插入新节点
    if (index == size)
        linkLast(element);
    else
        // 正常情况下，插入索引位置的节点及其后所有节点都需要向后移动
        linkBefore(element, node(index));
}

1. 首先，校验索引在当前LinkedList的合法性
2. 如果插入的位置恰好是LinkedList的尾部，则直接向LinkedList插入新的last节点。
3. 正常情况下，底层调用LinkedList#linkBefore(e, succ)方法在给定位置插入元素。

addAll(int index, Collection<? Extends E> c)

addAll(int index, Collection<? Extends E> c)将给定集合中的元素插入到给定位置，而在给定位置的当前元素及之后元素右移，即增加其索引。

新插入的元素将符合给定集合的迭代器顺序。

public boolean addAll(int index, Collection<? extends E> c) {
    // 校验索引在当前LinkedList的合法性
    checkPositionIndex(index);
    // 转换为Object数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 无需插入，没有修改链表结构，直接返回false
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        // 如果正好是从LinkedList的尾部开始
        succ = null;
        pred = last;
    } else {
        // 其他情况下，获取给定索引位置的节点，和它的前置节点
        succ = node(index);
        pred = succ.prev;
    }
    // 遍历需要插入的元素数组
    for (Object o : a) {
        // 类型转换为当前链表存储的元素类型
        @SuppressWarnings("unchecked") E e = (E) o;
        // 使用给定的元素值，它的前置节点创建新的节点对象
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果没有前置节点，那么新创建的节点就是first节点
        if (pred == null)
            first = newNode;
        else
            // 否则修改前置节点的后继节点指针指向
            pred.next = newNode;
        // 修改前置节点临时对象的指针指向，便于进行下一次迭代
        pred = newNode;
    }

    // 插入完成后，需要把之前在给定索引及之后的元素继续接入到链表中
    if (succ == null) {
        // 给定的索引正好是队尾，则直接赋值last节点即可
        last = pred;
    } else {
        // 其他情况下，需要把给定索引及之后的节点元素接回到链表中
        pred.next = succ;
        succ.prev = pred;
    }
    // 元素个数进行变更
    size += numNew;
    // list结构更新计数器+1
    modCount++;
    return true;
}

1. 首先，校验索引在当前LinkedList的合法性。
2. 将给定集合转换为Object数组。
3. 获取需要插入元素的个数，如果待插入的元素个数为0，则直接返回false。
4. 针对前置节点的情况：
   1. 如果正好从LinkedList的尾部开始插入，则前置节点置为last节点。
   2. 否则，根据索引获取当前节点，前置节点则为插入位置节点的前置节点。
5. 接着开始遍历待插入的元素数组
   1. 首先，将待插入元素转换为LinkedList中存储的元素类型。
   2. 接着，使用前置节点，转换类型后的待插入元素创建新节点。
   3. 如果没有前置节，则新创建的节点即是first节点。
   4. 否则，需要修改前置节点的后继节点指针指向新创建的节点。
   5. 最后，变更前置节点的指针指向，进行下一次遍历。
6. 将所有待插元素插入后，接着需要将之前的节点接回LinkedList中。
   1. 如果插入的位置即是LinkedList的尾部，直接将最后一个前置节点置为last节点。
   2. 否则正常情况下，将插入节点置为最后一个前置节点的后继节点，并将插入节点的前置节点置为最后一个前置节点。
7. 增加元素个数和更新次数。

addAll(Collection<? Extends E> c)

addAll(Collection<? Extends E> c)用于将给定集合插入到LinkedList的尾部，底层调用的是addAll(int index, Collection<? Extends E> c)方法。

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

addFirst(E e)

addFirst(E e)用于向LinkedList的头部插入一个新节点，底层调用的是LinkedList#linkFirst(e)。

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

addLast(E e)

addLast(E e)用于向LinkedList的尾部插入一个新节点，底层调用的是LinkedList#linkLast(e)。

public void addLast(E e) {
    linkLast(e);
}

移除元素

remove(int index)

remove(int index)用于将LinkedList中给定索引的节点移除，底层调用的是LinkedList#unlink(node)。

public E remove(int index) {
    // 校验索引在当前LinkedList的合法性
    checkElementIndex(index);
    // 移除给定索引位置的节点
    return unlink(node(index));
}

remove(Object o)

remove(Object o)用于将LinkedList中给定的元素对应的节点删除，底层调用的是LinkedList#unlink(node)。

public boolean remove(Object o) {
    // 如果给定的元素为null
    if (o == null) {
        // null也是一种元素类型，并不是节点为null，而是节点的item ＝ 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) {
            // 使用equals()方法找到对应的元素
            if (o.equals(x.item)) {
                // 从链表中移除此元素
                unlink(x);
                // 移除后立即返回，不再进行遍历
                return true;
            }
        }
    }
    // 走到这里，证明没有对list进行修改，返回false
    return false;
}

此方法的核心思想是对LinkedList进行从头到尾的遍历查找，而给定元素又分为两种情况：

• Object对象
• null

而一旦我们找到对应的元素的节点，则删除此节点后返回，即移除节点元素等于给定元素的第一个节点。

获取元素

get(int index)

get(int index)用于获取给定位置的节点元素，底层调用的是LinkedList#node(index)。

public E get(int index) {
    // 校验索引是否与当前LinkedList的索引范围
    checkElementIndex(index);
    // 获取给定索引的节点，并返回其元素
    return node(index).item;
}

indexOf(Object o)

indexOf(Object o)用于获取给定元素在LinkedList中第一次出现的索引位置，核心思想是从first节点开始遍历。

public int indexOf(Object o) {
    // 从头开始遍历
    int index = 0;
    // 根据null和正常情况，分别进行处理
    if (o == null) {
        // 给定元素为null的情况下
        for (Node<E> x = first; x != null; x = x.next) {
            // 找到null元素的节点，直接返回其索引
            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++;
        }
    }
    // 没有找到符合条件的给定元素的值的情况下，返回-1
    return -1;
}

给定元素又分为两种元素类型进行遍历：

• Object对象
• null

lastIndexOf(Object o)

lastIndexOf(Object o)用于获取给定元素在LinkedList中最后一次出现的位置，核心思想是从last节点开始向前进行遍历。

public int lastIndexOf(Object o) {
    // 从尾开始遍历
    int index = size;
    // 根据null和正常情况，分别进行处理
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            // 索引递减
            index--;
            // 找到null元素的节点，直接返回其索引
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            // 索引递减
            index--;
            // 找到给定元素值相等的节点，直接返回其索引
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

给定元素又分为两种元素类型进行遍历：

• Object对象
• null

设置元素

set(int index, E element)

set(int index, E element)用于使用给定元素，在LinkedList中获取并替换给定索引的节点元素，并返回被替换的元素。

public E set(int index, E element) {
    // 校验索引是否与当前LinkedList的索引范围
    checkElementIndex(index);
    // 获取给定位置的当前节点
    Node<E> x = node(index);
    // 获取当前节点的元素
    E oldVal = x.item;
    // 对元素加冰替换
    x.item = element;
    // 返回替换掉的元素
    return oldVal;
}

1. 首先，校验索引是否属于LinkedList的索引范围。
2. 获取给定索引位置的节点。
3. 使用给定元素替换节点的元素。
4. 返回被替换掉的元素。

其他方法

contains(Object o)

contains(Object o)用于判断LinkedList中是否含有给定元素，底层调用是LinkedList#indexOf(object)方法。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

clear()

clear()用于移除LinkedList中所有的元素，核心思想是采用从first节点开始进行遍历。

public void clear() {
    // 清除节点之间的所有连接都是"不必要的"，但是：
    // - 如果丢弃的节点位于多代内存，帮助其分代GC
    // - 一定要释放内存，即使还有一个可达的Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        // 节点的全部属性置为null
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // first节点和last节点置为null，list大小置为0，更新次数+1
    first = last = null;
    size = 0;
    modCount++;
}

即使清除了LinkedList，并不代表下一次使用的是新的LinkedList的，所以modCount没有清零。

size()

size()用于获取LinkedList中当前元素的个数，直接返回size属性的值。

public int size() {
    return size;
}

Deque操作

由于实现了Deque，所以LinkedList也使用了核心方法和基础方法实现了Deque接口方法。

添加元素

offer(E e)

offer(E e)用于向LinkedList的尾部添加元素，底层使用的是LinkedLIst#add(e)。

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

offerFirst(E e)

offerFirst(E e)用于向LinkedList的首部添加元素，底层使用的是LinkedList#addFirst(e)

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

offerLast(E e)

offerLast(E e)用于向LinkedList的尾部添加元素，底层使用的是LinkedList#addLast(e)。

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

push(E e)

push(E e)将LinkedList当做栈，向栈中压入节点，等同于LinkedList#addFirst()方法，底层调用的是LinkedList#linkFirst(e)方法。

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

移除元素

remove()

remove()等同于removeFirst()，用于获取并移除LinkedList中的first节点，移除的first节点的后继节点成为新的first节点，底层调用的是LinkedList#unlinkFist(f)方法。

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

当LinkedList中不存在元素时，会抛出NoSuchElementException异常。

removeFirst()

removeFirst()同上，用于获取并移除LinkedList中的first节点，移除的first节点的后继节点成为新的first节点，底层调用的是LinkedList#unlinkFist(f)方法。

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

当LinkedList中不存在元素时，会抛出NoSuchElementException异常。

removeFirstOccurrence(Object o)

removeFirstOccurrence(Object o)用于移除LinkedList中第一次出现给定元素对应的节点，底层调用的是LinkedList#remove(o)、LinkedList#unlink()方法。

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

核心思想是从first节点开始遍历，直到找到对应的元素的节点。

• 如果找到对应节点，调用unlink(node)移除这个节点。
• 否则返回false。

removeLast()

removeLast()用于获取并移除LinkedList中的last节点，移除的last节点的前置节点成为新的last节点，底层调用的是LinkedList#unlinkLast(l)方法。

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    // 直接将last节点的前置节点置为last节点
    return unlinkLast(l);
}

当LinkedList中不存在元素时，会抛出NoSuchElementException异常。

removeLastOccurrence(Object o)

removeLastOccurrence(Object o)用于移除LinkedList中最后一个出现给定元素的节点，底层调用的是LinkedList#unlink()方法。

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

核心思想是从last节点开始向前遍历，直到找到第一个对应给定元素的节点。

• 如果找到节点，调用LinkedList#unlink(node)移除节点。
• 否则返回false。

获取元素

peek()

peek()用于获取LinkedList的first节点元素，但不会移除first节点。

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

peekFirst()

peekFirst()也是用与获取LinkedList的first节点元素，但不会移除first节点。

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

peekLast()

peekLast()用于获取LinkedList的last节点元素，同时也不会移除last节点。

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

poll()和peek()是两组作用相同，作用结果不同的方法。

poll()

poll()用于获取并移除LinkedList的first节点元素，移除的first节点的后继节点成为新的first节点，底层调用的是LinkedList#unlinkFirst()方法。

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

pollFirst()

pollFirst()也是用于获取并移除LinkedList的first节点，移除的first节点的后继节点成为新的first节点，底层调用的是LinkedList#unlinkFirst()方法。

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

pollLast()

pollLast()用于获取并移除LinkedList的last节点，移除的last节点的前置节点成为新的last节点，底层调用的是LinkedList#unlinkLast()方法。

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

getFirst()

getFirst()用于获取LinkedList中的first节点元素，如果LinkedList中没有元素，则会抛出NoSuchElementException异常。

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

getLast()

getLast()用于获取LinkedList中的last节点元素，如果LinkedList中没有元素，则会抛出NoSuchElementException异常。

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

pop()

pop()是LinkedList中定义的出栈操作，用于获取LinkedList中的first节点元素，

底层调用的是LinkedList#removeFirst()方法。

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

element()

element()用于获取LinkedList中的first节点元素，但不会移除，等同于LinkedList#getFirst()方法。

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

当LinkedList中不存在元素时，会抛出NoSuchElementException异常。

迭代器

list-iterator

list-iterator是我们经常使用的LinkedList的迭代器的实现，list-iterator是一个快速失败的迭代器(快速失败的概念请看本篇文章的开头部分)。

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

具体的实现由ListItr类实现：

ListItr

基本属性

• lastReturned，上一次返回的节点指针。
• next，下一个节点的指针。
• nextIndex，下一个节点索引。
• expectedModCount，期望的集合更新次数，初始值为创建ListItr时，LinkedList的modCount值，用于记录ListItr内部的更新操作计数。

构造方法

ListItr声明了使用给定索引构建list-iterator。

ListItr(int index) {
    // 如果索引以及到达list的结尾，下一个节点则为null
    // 否则获取给定索引的节点
    next = (index == size) ? null : node(index);
    // 移动下一个索引的指针
    nextIndex = index;
}

1. 在创建一个ListItr时，会首先根据给定的索引获取节点信息，作为next节点指针指向对象。
2. 同时记录下一个节点的索引。

下一个元素

public boolean hasNext() {
    return nextIndex < size;
}

hasNext()用于判断LinkedList中是否还有下个元素。

public E next() {
    // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
    // 如果不包含下一个节点，则抛出NoSuchElementException异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 移动上一次返回的节点指针
    lastReturned = next;
    // 移动下一个节点指针
    next = next.next;
    // 移动下一个节点的索引值
    nextIndex++;
    // 返回下一个节点元素
    return lastReturned.item;
}

next()用于获取LinkedList中下一个节点的元素。

1. 在移动节点指针之前，首先需要判断LinkedList是否发生除此list-iterator之外是否发生了结构性修改。
2. 如果没有后继节点，会抛出NoSuchElementException异常。
3. 在获取下一个节点元素时，需要将当前节点置为lastReturned，同时移动next指针为当前节点的后继节点，增加下一个节点的索引。

上一个元素

public boolean hasPrevious() {
   return nextIndex > 0;
}

hasPrevious()用于判断当前节点是否有前置节点。

public E previous() {
   // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
    // 如果不包含上一个节点，则抛出NoSuchElementException异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 获取next指针的前置节点，置为lastReturned和next指针
    // 如果next指针为null，则从last节点开始逆序遍历
    lastReturned = next = (next == null) ? last : next.prev;
    // 较少索引计数
    nextIndex--;
    // 返回逆序节点的元素
    return lastReturned.item;
}

previous()用于获取LinkedList上一个节点元素。

1. 在移动节点指针之前，首先需要判断LinkedList是否发生除此list-iterator之外是否发生了结构性修改。
2. 如果没有前置节点，会抛出NoSuchElementException异常。
3. 获取next节点指针的前置节点作为lastReturned和next指针指向的节点，此时next指针指向null，则从last节点开始逆序遍历。
4. 减少索引计数。

获取索引

nextIndex()用于获取下一个节点的索引。

public int nextIndex() {
   return nextIndex;
}

previousIndex()用于获取上一个节点的索引。

public int previousIndex() {
    return nextIndex - 1;
}

我们在使用迭代器时需要对LinkedList这种拥有快速失败特性的迭代器进行结构性操作时，需要使用迭代器内部实现的结构性操作。

移除元素

remove()用于在list-iterator内部执行移除节点，不会造成ConcurrentModificationException异常。

public void remove() {
    // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
    // 如果没有上一次返回的元素，则此操作为异常操作
    // 通常情况下是对刚创建的list-iterator执行此方法或者已经进行一次移除操作
    if (lastReturned == null)
        throw new IllegalStateException();
    // 获取上一次返回节点的下一个节点
    Node<E> lastNext = lastReturned.next;
    // 移除上一次返回的节点
    unlink(lastReturned);
    // 如果list-iterator的下一个节点是上一次返回的节点
    // 也就是逆序遍历
    if (next == lastReturned)
        // next指针则为上一次返回的节点的后继节点
        next = lastNext;
    else
        // 否则next指针已经指向正序遍历的下一个节点，此时只需减少下一个节点索引
        nextIndex--;
    // 上一次返回的节点已经移除，直接置为null
    lastReturned = null;
    // 修改list-iterator内部的更新计数器
    expectedModCount++;
}

1. 在移除节点之前，首先需要判断LinkedList是否发生除此list-iterator之外是否发生了结构性修改。
2. 如果lastReturned为null，则无法移除元素，抛出IllegalStateException异常，一般发生为刚创建一个新的list-iterator或已经进行一次结构性操作。
3. 正常情况下，获取lastReturned的下一个节点。
4. 调用底层LinkedList#unlink(e)方法，移除节点。
5. next指针正常情况下应指向移除节点的后继节点，因移除了一个节点，则减少索引计数。
6. 但如果next指针为移除的节点，此时证明进行了逆序遍历，将next指针重置为移除的节点的后继节点。
7. lastReturned节点已经移除，指针需要置为null。
8. 增加list-iterator内部的更新计数。

更新元素

set(E e)不属于结构性更新操作，只是更新上一次返回节点的元素。

public void set(E e) {
    // 如果上一次返回的节点为null，则为非法操作
    if (lastReturned == null)
        throw new IllegalStateException();
    // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
    // 更新上一次返回节点的元素
    lastReturned.item = e;
}

1. 在设置节点元素之前，首先需要判断LinkedList是否发生除此list-iterator之外是否发生了结构性修改。
2. 更新上一次返回节点的元素。

添加元素

add(E e)用于在list-iterator内部添加新元素，不会造成ConcurrentModificationException异常。

public void add(E e) {
    // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
    // 将上一次返回的节点置为null
    lastReturned = null;
    // 如果下一个节点也为null
    if (next == null)
        // 则在队尾加入新的节点及元素
        linkLast(e);
    else
        // 否则在下一个节点之前加入新的节点及元素
        linkBefore(e, next);
    // 更新下一个节点的索引和list-iterator内部的更新操作计数器
    nextIndex++;
    expectedModCount++;
}

1. 在添加元素之前，首先需要判断LinkedList是否发生除此list-iterator之外是否发生了结构性修改。
2. 将上一次返回的节点置为null。
3. 底层调用LinkedList#linkBefore(e, next)在next节点之前插入新的元素。
4. 如果next节点为null，证明已经来到LinkedList的尾部，直接底层调用LinkedList#linkLast(e)在LinkedList插入新元素节点。
5. 增加索引计数和内部更新计数。

Stream操作

在JDK 8引入Stream API后，许多类中都加入了FuntionalInterface操作。

forEachRemaining(consumer)用于将正序遍历中剩余未遍历的元素放入到Consumer中。

public void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (modCount == expectedModCount && nextIndex < size) {
        action.accept(next.item);
        lastReturned = next;
        next = next.next;
        nextIndex++;
    }
    // 校验是否发生除此list-iterator之外的结构性更新事件
    checkForComodification();
}

descending-iterator

有正序迭代器，就有逆序迭代器，毕竟ListItr中已经提供了hasPrevious()和previous()方法用于逆序迭代。

而LinkedList声明了descendingIterator()方法用于构造一个逆序迭代器。

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

内部实现是初始化DescendingIterator对象。

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

DescendingIterator的实现比较简单，思路是将hasNext()和next()的意义反过来，即调用next()时，实际上调用的是ListItr#previous()，即调用不变，内部迭代方向发生变化。

并行迭代器

在Stream API操作中我们可以进行并行的Stream操作，我们在进行遍历时也可以使用并行迭代器。

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

内部实现是初始化LLSpliterator对象。

LLSpliterator

基本属性

• BATCH_UNIT，了解Spliterator概念的同学应该了解，Spliterator对象是以数组形式，此属性用于确定每个数组的增量单位。
• MAX_BATCH，用于限制每个数组的最大容量。
• list，需要并行迭代的LinkedList。
• current，当前遍历到的节点。
• est，遍历大小的预估值。
• expectedModCount，作为一个迭代器，即使是并行的，也需要有一个内部的更新计数。
• batch，每个Split的处理容量。

构造方法

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

我们使用LinkedList，遍历大小的预估值和期望的更新技术作为LLSpliterator构造入参构造一个LLSpliterator。

获取预估值

getEst()用于获取每个Split的预估大小。

final int getEst() {
    int s;
    final LinkedList<E> lst;
    // 如果预估值＜0，证明还没有开始初始化
    if ((s = est) < 0) {
        // 如果需要迭代的LinkedList为null，则预估值为0
        if ((lst = list) == null)
            s = est = 0;
        else {
            // 否则设置当前spliterator的更新次数为给定LinkedList的更新次数
            expectedModCount = lst.modCount;
            // 当前节点为给定LinkedList的first节点
            current = lst.first;
            // 预估大小为给定LinkedList容量大小
            s = est = lst.size;
        }
    }
    return s;
}

一般情况下预估大小为当前LinkedList的容量大小。

进行分离

trySplit()用于将LinkedList的中的元素分隔成多个数组，用于进行并行遍历。

public Spliterator<E> trySplit() {
    Node<E> p;
    int s = getEst();
    // 如果当前预估大小＞1并且当前节点不为null
    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;
        do {
            // 向数组中添加元素
            a[j++] = p.item;
        } while ((p = p.next) != null && j < n);
        // 移动当前节点指针指向
        current = p;
        // 设置Spliterator的处理容量
        batch = j;
        // 更新预估容量
        est = s - j;
        // 返回新的Spliterator
        return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
    }
    return null;
}

1. Spliterator的数组大小不能超过MAX_BATCH限制的容量，如果需要对batch进行扩容，则先增加BATCH_UNIT容量，然后再去掉溢出的容量。
2. 如果预估的容量比本次分隔的容量要大，剩余的元素会在下一次分离中进行。
3. 向申请的数组中添加LinkedList元素。
4. 添加完成之后，移动current指针指向遍历的最后一个节点。
5. 设置本次批处理的容量，为下一次批处理的基数。
6. 由于已经分隔处理一些元素，此时需要更新预估容量。

获取元素

tryAdvance()用于并行处理中尝试获取下一个节点，并写入到Consumer Stream中。

public boolean tryAdvance(Consumer<? super E> action) {
    Node<E> p;
    // 非法Stream操作流，抛出NullPointerException异常
    if (action == null) throw new NullPointerException();
    // 获取预估大小，如果预估大小＞0，并且当前节点不为null
    // 迭代器中仍有节点未遍历
    if (getEst() > 0 && (p = current) != null) {
        // 减少预估大小
        --est;
        // 将下一个元素放入到Stream操作流中
        E e = p.item;
        current = p.next;
        action.accept(e);
        // 如果发生了除此Spliterator之外的结构性更新，抛出ConcurrentModificationException异常
        if (list.modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return true;
    }
    return false;
}

1. 如果迭代器中仍有节点未遍历，并且current指针仍指向LinkedList中的节点，则可以获取下一个节点。
2. 首先减少剩余容量，并将current指针指向的节点元素放入到Consumer Stream中。
3. 接着判断LLSpliterator是否发生了结构性操作，如果发生，抛出ConcurrentModificationException异常。
4. 正常情况下，返回true。

Stream操作

forEachRemaining(Consumer<? super E> action)同ListItr#forEachRemaining(Consumer<? super E> action)，也是将迭代器中未遍历的元素放入到Consumer Stream中。

public void forEachRemaining(Consumer<? super E> action) {
    Node<E> p;
    int n;
    // Stream操作流不合法
    if (action == null) throw new NullPointerException();
    // 如果当前预估大小＞0，当前节点不为null
    if ((n = getEst()) > 0 && (p = current) != null) {
        // 先当前节点置为null，预估大小置为0
        current = null;
        est = 0;
        // 然后将给定LinkedList还未遍历完的元素放入到Stream操作流中
        do {
            E e = p.item;
            p = p.next;
            action.accept(e);
        } while (p != null && --n > 0);
    }
    // 如果发生了除此Spliterator之外的结构性更新，抛出ConcurrentModificationException异常
    if (list.modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

1. 如果迭代器中仍有节点未遍历，并且current指针仍指向LinkedList中的节点，则可以获取下一个节点。
2. 将剩余的节点遍历放入到Consumer Stream中。
3. 接着判断LLSpliterator是否发生了结构性操作，如果发生，抛出ConcurrentModificationException异常。

特征

Spliterator提供了characteristics()方法用于计算Spliterator的特征，LLSpliterator的特征如下：

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

即LinkedList实现的LLSpliterator需要满足ORDERED、 SIZED、SUBSIZED特征。

其他方法

序列化与反序列化

readObject(ObjectInputSteams s)

readObject(ObjectInputSteams s)对输出流反序列化为LinkedList，LinkedList元素的存储顺序按照输出流的读取顺序，底层调用的是LinkedLast#linklast(e)方法。

@SuppressWarnings("unchecked")
@java.io.Serial
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());
}

writeObject(ObjectOutputStream s)

writeObject(ObjectOutputStream s)用于向输出流中写入LinkedList中的节点元素，写入顺序为从LinkedList的first节点开始一次进行写入。

@java.io.Serial
    private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // 输出所有隐藏的序列化版本
    s.defaultWriteObject();

    // 输出流的大小
    s.writeInt(size);

    // 以合适的顺序输出所有的元素
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

形式转换

toArray()

toArray()用于将LinkedList转换为数组，返回的数组和LinkedList是无引用关系的，调用者无需关心LinkedList被回收的问题，LinkedList中元素的顺序和数组中元素的顺序是相同的。

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

toArray(T[] a)

toArray(T[] a)用于将LinkedList中的元素放入到给定的数组中。

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 如果给定数组大小小于当前list的大小，则使用给定数组的类型和当前list的大小创建一个新数组
        a = (T[]) java.lang.reflect.Array.newInstance(
        a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    // 从first节点开始遍历
    for (Node<E> x = first; x != null; x = x.next)
        // 设置数组中对应位置元素的值
        result[i++] = x.item;
    // 如果数组长度超出list的大小，则将数组超出长度的第一个索引的值职位null
    if (a.length > size)
        a[size] = null;

    return a;
}

1. 如果LinkedList中元素个数大于给定数组的长度，则对给定数组进行扩容。
2. 从first节点开始，将节点元素写入到给定数组中。
3. 如果数组长度大于LinkedList的元素的个数，则将最后一个元素的下一个元素置为null，视为没有元素的标志。

信息输出

outOfBoundsMsg(int index)

outOfBoundsMsg(int index)用于构建IndexOutOfBoundsException异常的详细输出信息，其中包括溢出的索引和LinkedList当前的元素个数。

private String outOfBoundsMsg(int index) {
   return "Index: " + index + ", Size: " + size;
}