关于java:LinkedList源码解析

一、概述

LinkedList，绝对于 ArrayList，大家可能平时应用 LinkedList 要少一些，其实有时候应用 LinkedList 比 ArrayList 效率高很多，当然，这得视状况而定。

本文将带大家深刻 LinkedList 源码，剖析其背地的实现原理，以便当前在适合的状况下进行应用。

之前我所晓得的 LinkedList 的常识：

• LinkedList 底层是链表构造
• 插入和删除比拟快（O(1)），查问则绝对慢一些（O(n)）
• 因为是链表构造，所以调配的空间不要求是间断的

二、链表

因为 LinkedList 源码中很多中央是进行链表操作, 所以先带大家温习一下链表的基础知识. 以前用 C 语言实现的链表, 大家能够去看一下, 地址:https://github.com/xfhy/dataS…

1. 单链表

一个节点中蕴含数据和下一个节点的指针(留神, 是下一个节点的指针, 而不是下一个节点数据的指针), 尾节点没有下一个节点, 所以指向 null. 拜访某个节点只能从头节点开始查找, 而后顺次往后遍历.

2. 单向循环链表

单向循环链表比单链表多了一个尾节点的指针指向的是头结点.

3. 双向链表

双向链表的每个节点蕴含以下数据: 上一个节点的指针, 本人的数据, 下一个节点的指针. 尾节点没有下一个节点, 所以指向 null. 这样的构造, 比方我拿到链表两头的一个节点, 即能够往前遍历, 也能够往后遍历.

4. 双向循环链表

双向循环链表的尾节点的下一个节点是头结点, 头节点的上一个节点是尾节点.

三、LinkedList 的继承关系

源码中的定义:

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

• AbstractSequentialList 这个类提供了 List 的一个骨架实现接口，以尽量减少实现此接口所需的工作量由“程序拜访”数据存储（如链接列表）反对。对于随机拜访数据（如数组），应应用 AbstractList 优先于此类。
• 实现了 List 接口, 意味着 LinkedList 元素是有序的, 能够反复的, 能够有 null 元素的汇合.
• Deque 是 Queue 的子接口,Queue 是一种队列模式, 而 Deque 是双向队列, 它反对从两个端点方向检索和插入元素.
• 实现了 Cloneable 接口, 标识着能够它能够被复制. 留神,ArrayList 外面的 clone()复制其实是浅复制(不晓得此概念的赶快去查资料, 这知识点十分重要).
• 实现了 Serializable 标识着汇合可被序列化。

四、看 LinkedList 源码前的筹备

1. 节点定义

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 是 LinkedList 的动态外部类.

为什么是动态外部类? 我感觉可能起因如下: 一般外部类会有外部类的强援用, 而动态外部类就没有. 有外部类的强援用的话, 很容易造成内存透露, 写成动态外部类能够防止这种状况的产生.

2. 成员变量

看构造方法之前先看看几个属性:

// 链表长度
transient int size = 0;
/**
* 头结点
*/
transient Node<E> first;

/**
* 尾节点
*/
transient Node<E> last;

这里为什么要存在一个成员变量尾节点? 我感觉是为了不便, 比方查找相应索引处元素 + 插入元素到最初. 查找相应索引处元素时, 先判断索引是在前半段还是在后半段, 如果是在后半段, 那么间接从尾节点登程, 从后往前进行查找, 这样速度更快. 在插入元素到最初时, 能够间接通过尾节点不便的进行插入.

3. 构造方法

上面是构造方法源码:

/**
* 结构一个空列表
*/
public LinkedList() {}

/**
* 结构列表通过指定的汇合
*/
public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

两个构造方法都比较简单, 就是结构一个列表, 其中的 addAll()办法待会儿放到前面剖析.

思考: 为什么 LinkedList 没有提供 public LinkedList(int initialCapacity)这种构建指定大小列表的结构形式?

因为 ArrayList 有这种构造方法public ArrayList(int initialCapacity),ArrayList 提供这种构造方法的益处在于在晓得须要多大的空间的状况下, 能够按需结构列表, 无需节约多余的空间和不必要的生成新数组的操作. 而 LinkedList 能够很轻松动静的减少元素(O(1)), 所以没必要一开始就结构一个有很多元素的列表, 到时须要的时候再按需加上去就行了.

五、增加元素

1. add(E e)

办法作用: 将 e 增加到链表开端, 返回是否增加胜利

/**
* 增加指定元素到链表尾部
*/
public boolean add(E e) {linkLast(e);
    return true;
}
/**
* Links e as last element. 将 e 增加到尾部
*/
void linkLast(E e) {
    //1. 暂记尾节点
    final Node<E> l = last;
    //2. 构建节点 前一个节点是之前的尾节点
    final Node<E> newNode = new Node<>(l, e, null);
    //3. 新建的节点是尾节点了
    last = newNode;
    //4. 判断之前链表是否为空  
    // 为空则将新节点赋给头结点(相当于空链表插入第一个元素, 头结点等于尾节点)
    // 非空则将之前的尾节点指向新节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //5. 链表长度减少
    size++;
    modCount++;
}

大体思路:

1. 构建一个新的节点
2. 将该新节点作为新的尾节点. 如果是空链表插入第一个元素, 那么头结点 = 尾节点 = 新节点; 如果不是, 那么将之前的尾节点指向新节点.
3. 减少链表长度

小细节
boolean add(E e) 增加胜利返回 true, 增加失败返回 false. 咱们在代码中没有看到有返回 false 的状况啊, 间接在代码中写了个返回 true, 什么判断条件都没有, 啊??

认真想想, 分配内存空间不是必须是间断的, 所以只有是还能给它调配空间, 就不会增加失败. 当空间不够调配时(内存溢出), 会抛出 OutOfMemory.

2. addLast(E e)

办法作用: 增加元素到开端. 外部实现和 add(E e) 一样.

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

3. addFirst(E e)

办法作用: 增加元素到链表头部

public void addFirst(E e) {linkFirst(e);
}
/**
* 增加元素到链表头部
*/
private void linkFirst(E e) {
    //1. 记录头结点
    final Node<E> f = first;
    //2. 创立新节点  next 指针指向之前的头结点
    final Node<E> newNode = new Node<>(null, e, f);
    //3. 新建的节点就是头节点了
    first = newNode;
    //4. 判断之前链表是否为空  
    // 为空则将新节点赋给尾节点(相当于空链表插入第一个元素, 头结点等于尾节点)
    // 非空则将之前的头结点的 prev 指针指向新节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    //5. 链表长度减少
    size++;
    modCount++;
}

大体思路:

1. 构建一个新的节点
2. 将该新节点作为新的头节点. 如果是空链表插入第一个元素, 那么头结点 = 尾节点 = 新节点; 如果不是, 那么将之前的头节点的 prev 指针指向新节点.
3. 减少链表长度

4. push(E e)

办法作用: 增加元素到链表头部 这里的意思比较压栈. 和 pop(出栈: 移除链表第一个元素)相同.

外部实现是和 addFirst() 一样的.

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

5. offer(),offerFirst(E e),offerLast(E e)

办法作用: 增加元素到链表头部. 外部实现其实就是add(e)

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

/**
* 增加元素到开端
*/
public boolean offerLast(E e) {addLast(e);
    return true;
}

6. add(int index, E element)

办法作用: 增加元素到指定地位, 可能会抛出IndexOutOfBoundsException

// 增加元素到指定地位
public void add(int index, E element) {
    //1. 越界查看
    checkPositionIndex(index);

    //2. 判断一下 index 大小
    // 如果是和 list 大小一样, 那么就插入到最初
    // 否则插入到 index 处
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// 查看是否越界
private void checkPositionIndex(int index) {if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* Returns the (non-null) Node at the specified element index.
返回指定元素索引处的（非空）节点。*/
Node<E> node(int index) {// assert isElementIndex(index);

    /**
    * 这里的思维十分奇妙, 如果 index 在链表的前半部分, 那么从 first 开始往后查找
    否则, 从 last 往前面查找
    */
    //1. 如果 index<size/2 , 即 index 在链表的前半部分
    if (index < (size >> 1)) {
        //2. 记录下第一个节点
        Node<E> x = first;
        //3. 循环从第一个节点开始往后查, 直到达到 index 处, 返回 index 处的元素
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //index 在链表的后半局部
        //4. 记录下最初一个节点
        Node<E> x = last;
        //5. 循环从最初一个节点开始往前查, 直到达到 index 处, 返回 index 处的元素
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
/**
* Links e as last element.
将 e 链接到 list 最初一个元素
*/
void linkLast(E e) {
    //1. 记录最初一个元素 l
    final Node<E> l = last;
    //2. 构建一个新节点, 数据为 e, 前一个是 l, 后一个是 null
    final Node<E> newNode = new Node<>(l, e, null);
    //3. 当初新节点是最初一个元素了, 所以须要记录下来
    last = newNode;
    //4. 如果之前 list 为空, 那么 first=last=newNode, 只有一个元素
    if (l == null)
        first = newNode;
    else
        //5. 非空的话, 那么将之前的最初一个指向新的节点
        l.next = newNode;
    //6. 链表长度 +1
    size++;
    modCount++;
}

/**
* Inserts element e before non-null Node succ.
在非 null 节点 succ 之前插入元素 e。*/
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //1. 记录 succ 的前一个节点
    final Node<E> pred = succ.prev;
    //2. 构建一个新节点, 数据是 e, 前一个节点是 pred, 下一个节点是 succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    //3. 将新节点作为 succ 的前一个节点
    succ.prev = newNode;
    //4. 判断 pred 是否为空
    // 如果为空, 那么阐明 succ 是之前的头节点, 当初新节点在 succ 的后面, 所以新节点是头节点
    if (pred == null)
        first = newNode;
    else
        //5. succ 的前一个节点不是空的话, 那么间接将 succ 的前一个节点指向新节点就能够了
        pred.next = newNode;
    //6. 链表长度 +1
    size++;
    modCount++;
}

大体思路:

1. 首先判断一下插入的地位是在链表的最初还是在链表两头.
2. 如果是插入到链表开端, 那么将之前的尾节点指向新节点

3. 如果是插入到链表两头

   1. 须要先找到链表中 index 索引处的节点.
   2. 将新节点赋值为 index 处节点的前一个节点
   3. 将 index 处节点的前一个节点的 next 指针赋值为新节点

哇, 这里形容起来有点艰难,,,, 不晓得我形容分明没有. 如果没看懂我的形容, 看一下代码 + 再联合代码正文 + 画一下草图应该更清晰一些.

6. addAll(int index, Collection<? extends E> c)

办法作用: 将指定汇合的所有元素插入到 index 地位

// 将指定汇合的所有元素插入到开端地位
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}

// 将指定汇合的所有元素插入到 index 地位
public boolean addAll(int index, Collection<? extends E> c) {
    //1. 入参合法性检查
    checkPositionIndex(index);

    //2. 将汇合转成数组
    Object[] a = c.toArray();
    //3. 记录须要插入的汇合元素个数
    int numNew = a.length;
    //4. 如果个数为 0, 那么插入失败, 不继续执行了
    if (numNew == 0)
        return false;

    //5. 判断一下 index 与 size 是否相等
    // 相等则插入到链表开端
    // 不相等则插入到链表两头  index 处   
    Node<E> pred, succ;   
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 索引处节点  这样就能够不便的拿到该节点的前后节点信息
        succ = node(index);
        // 记录 index 索引处节点前一个节点
        pred = succ.prev;
    }

    //6. 循环将汇合中所有元素连贯到 pred 前面
    for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果前一个是空, 那么将新节点作为头结点
        if (pred == null)
            first = newNode;
        else
            // 指向新节点
            pred.next = newNode;
        pred = newNode;
    }

    //7. 判断 succ 是否为空
    // 为空的话, 那么汇合的最初一个元素就是尾节点
    // 非空的话, 那么将 succ 连贯到汇合的最初一个元素前面
    if (succ == null) {last = pred;} else {
        pred.next = succ;
        succ.prev = pred;
    }

    //8. 链表长度 +numNew
    size += numNew;
    modCount++;
    return true;
}

大体思路:

1. 将须要增加的汇合转成数组 a
2. 判断须要插入的地位 index 是否等于链表长度 size, 如果相等则插入到链表最初; 如果不相等, 则插入到链表两头, 还须要找到 index 处节点 succ, 不便拿到该节点的前后节点信息.
3. 记录 index 索引处节点的前一个节点 pred, 循环将汇合中所有元素连贯到 pred 的前面
4. 将汇合最初一个元素的 next 指针指向 succ, 将 succ 的 prev 指针指向汇合的最初一个元素

六、删除元素

1. remove(),removeFirst()

办法作用: 移除链表第一个元素

/**
* 移除链表第一个节点
*/
public E remove() {return removeFirst();
}

/**
* 移除链表第一个节点
*/
public E removeFirst() {
    final Node<E> f = first;
    // 留神: 如果之前是空链表, 移除是要报错的哟
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
* Unlinks non-null first node f.
* 将第一个节点删掉
*/
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //1. 记录第一个节点的数据值
    final E element = f.item;
    //2. 记录下一个节点
    final Node<E> next = f.next;
    //3. 将第一个节点置空  帮忙 GC 回收
    f.item = null;
    f.next = null; // help GC
    //4. 记录头节点
    first = next;
    //5. 如果下一个节点为空, 那么链表无节点了    如果不为空, 将头节点的 prev 指针置为空
    if (next == null)
        last = null;
    else
        next.prev = null;
    //6. 链表长度 -1
    size--;
    modCount++;
    //7. 返回删除的节点的数据值
    return element;
}

大体思路: 其实就是将第一个节点移除并置空, 而后将第二个节点作为头节点. 思路还是十分清晰的, 次要是对细节的解决.

2. remove(int index)

办法作用: 移除指定地位元素

// 移除指定地位元素
public E remove(int index) {
    // 查看入参是否非法
    checkElementIndex(index);
    //node(index)找到 index 处的节点  
    return unlink(node(index));
}

// 移除节点 x
E unlink(Node<E> x) {
    // assert x != null;
    //1. 记录该节点数据值, 前一个节点 prev, 后一个节点 next
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    //2. 判断前一个节点是否为空
    if (prev == null) {
        // 为空的话, 那么阐明之前 x 节点是头节点  这时 x 的下一个节点成为头节点
        first = next;
    } else {
        // 非空的话, 将前一个节点的 next 指针指向 x 的下一个节点
        prev.next = next;
        // x 的 prev 置为 null
        x.prev = null;
    }

    //3. 判断 x 后一个节点是否为空
    if (next == null) {
        // 为空的话, 那么阐明之前 x 节点是尾节点, 这时 x 的前一个节点成为尾节点
        last = prev;
    } else {// 为空的话, 将 x 的下一个节点的 prev 指针指向 prev(x 的前一个节点)
        next.prev = prev;
        // x 的 next 指针置空
        x.next = null;
    }

    //4. x 节点数据值置空
    x.item = null;
    //5. 链表长度 -1
    size--;
    modCount++;
    //6. 将 x 节点的数据值返回
    return element;
}

大体思路:

1. 首先找到 index 索引处的节点(这样就能够不便的获取该节点的前后节点), 记为 x
2. 记录 x 的前 (prev) 后(next)节点
3. 将 x 的前一个节点 prev 节点的 next 指针指向 next, 将 x 节点的后一个节点的 prev 指针指向 prev 节点.
4. 将 x 节点置空, 链表长度 -1

3. remove(Object o)

办法作用: 从此链表中删除第一次呈现的指定元素 o

public boolean remove(Object o) {
    //1. 判断 o 是否为空
    if (o == null) {
        // 为 null  循环, 找第一个数据值为 null 的节点
        for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {
                // 删除该节点
                unlink(x);
                return true;
            }
        }
    } else {
        // 非空  循环, 找第一个与 o 的数据值相等的节点
        for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {
                // 删除该节点
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

大体思路:

1. 首先判断入参是否为 null
2. 如果为 null, 那么循环遍历链表, 从头节点开始往后查找, 找到第一个节点的数据值为 null 的, 间接删除该节点.
3. 如果非 null, 那么循环遍历链表, 从头节点开始往后查找, 找到第一个节点的数据值为 o 的, 间接删除该节点.

这里的循环遍历链表的代码, 我感觉还是比拟通用的, 从头节点开始, 通过一直的将 x 赋值为下一个元素, 直到遍历到为 null 的中央完结, 这样就完满的遍历完了链表所有节点.

4. removeFirstOccurrence(Object o)

办法作用: 从此链表中删除第一次呈现的指定元素 o. 外部其实就是下面的 remove(o);

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

5. removeLast()

办法作用: 移除最初一个元素并返回

public E removeLast() {
    final Node<E> l = last;
    // 如果链表是空的, 那么就要抛出一个谬误
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
移除链表最初一个元素
*/
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;

    //1. 记录尾节点数据值
    final E element = l.item;
    //2. 找到尾节点的前一个节点 prev
    final Node<E> prev = l.prev;
    //3. 将尾节点置空  不便 GC
    l.item = null;
    l.prev = null; // help GC
    //4. 将 last 赋值为 prev  
    last = prev;
    //5. 判断 prev 是否为 null
    // 为空的话, 阐明之前链表就只有 1 个节点, 当初删了之后, 头节点和尾节点都为 null 了
    // 非空, 间接将新任尾节点的 next 指针指向 null
    if (prev == null)
        first = null;
    else
        prev.next = null;
    //6. 链表长度 -1
    size--;
    modCount++;
    //7. 返回之前尾节点数据值
    return element;
}

大体思路:

1. 判断链表是否有节点, 没有节点间接抛谬误 ….
2. 首先找到倒数第二个节点(可能没有哈, 没有的话, 阐明链表只有一个节点)prev
3. 而后将尾节点置空,prev 的 next 指针指向 null

6. removeLastOccurrence(Object o)

办法作用: 从此链表中删除最初一次呈现的指定元素 o.

实现: 其实和下面的 remove(o)是一样的, 只不过这里遍历时是从尾节点开始往前查找的.

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

7. poll()

办法作用: 获取第一个元素的同时删除第一个元素, 当链表无节点时, 不会报错. 这里的 unlinkFirst()下面已剖析过.

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

8. pop()

办法作用: 获取第一个元素的同时删除第一个元素, 当链表无节点时, 会报错.

public E pop() {return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

七、批改元素

1. set(int index, E element)

办法作用: 设置 index 处节点数据值为 element

public E set(int index, E element) {
    //1. 入参检测
    checkElementIndex(index);
    //2. 找到 index 处节点, 下面已剖析该办法
    Node<E> x = node(index);
    //3. 保留该节点旧值
    E oldVal = x.item;
    //4. 替换为新值
    x.item = element;
    //5. 将旧值返回
    return oldVal;
}

大体思路: 非常简单, 就是首先找到 index 处节点, 替换该节点数据值

八、查问元素

1. element()

办法作用: 获取链表第一个元素. 办法比较简单, 就是将链表头节点数据值进行返回

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

2. get(int index)

办法作用: 获取指定索引处元素. 办法比较简单, 就是通过 node(index)找到 index 索引处节点, 而后返回其数据值

public E get(int index) {
    //1. 入参检测
    checkElementIndex(index);
    //2. 获取指定索引处节点数据值
    return node(index).item;
}

3. getFirst()

办法作用: 获取链表第一个元素. 非常简单, 就是将 first 的数据值返回

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

4. getLast()

办法作用: 获取链表最初一个元素. 非常简单, 就是将 last 的数据值返回

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

5. 通过 listIterator()遍历

这也是查问的一种, 哈哈

咱们先来看看 listIterator(int index) 办法, 就是 new 了一个 ListItr 进行返回.ListItr 是 LinkedList 的外部类.

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

接下来, 咱们看看这个外部类:

private class ListItr implements ListIterator<E> {
    // 上一次返回的节点
    private Node<E> lastReturned;
    // 下一个节点
    private Node<E> next;
    // 下一个节点索引
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {// assert isPositionIndex(index);
        // 如果是最初一个节点, 那么返回 next 是 null    
        // 如果不是最初一个节点, 那么找到该 index 索引处节点
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        // 判断是否还有下一个元素
        return nextIndex < size;
    }

    // 获取下一个元素
    public E next() {checkForComodification();
        //1. 如果没有下一个元素   抛异样
        if (!hasNext())
            throw new NoSuchElementException();

        //2. 记录上一次遍历到的节点
        lastReturned = next;
        //3. 往后移
        next = next.next;
        //4. 索引 +1
        nextIndex++;
        //5. 将遍历到的节点数据值返回
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        // 判断是否还有前一个元素
        return nextIndex > 0;
    }

    // 获取前一个元素
    public E previous() {checkForComodification();
        //1. 如果没有前一个元素, 则抛异样
        if (!hasPrevious())
            throw new NoSuchElementException();

        //2. 当 next 是 null 的时候, 赋值为 last     
        // 不是 null 的时候, 往前挪动
        lastReturned = next = (next == null) ? last : next.prev;
        //3. index-1  因为是往前
        nextIndex--;
        //4. 将遍历到的节点数据值返回
        return lastReturned.item;
    }

    public int nextIndex() {return nextIndex;}

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

    // 移除以后遍历到的元素
    public void remove() {checkForComodification();
        //1. 移除以后遍历到的元素为 null, 间接抛谬误
        if (lastReturned == null)
            throw new IllegalStateException();

        //2. 记录以后节点的下一个节点
        Node<E> lastNext = lastReturned.next;
        //3. 删除以后节点
        unlink(lastReturned);
        //4. 如果 next == lastReturned, 阐明以后是从返回后遍历的, 那么将 next 赋值为下一个节点
        // 如果不相等, 那么阐明是从后往前遍历的, 这时只须要将 index- 1 就行了
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        //5. 将移除的节点置空
        lastReturned = null;
        expectedModCount++;
    }

    // 设置以后正在遍历的节点的值   啥? 用 ListIterator 竟然能够在遍历的时候批改值,,666
    public void set(E e) {if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        // 设置以后遍历的节点的值
        lastReturned.item = e;
    }

    // 增加一个值
    public void add(E e) {checkForComodification();
        lastReturned = null;
        // 如果 next 为 null, 那么增加到最初
        // 否则, 将 e 元素增加到 next 的后面
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

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

    // 判断一下该列表是否被其余线程改过(在迭代过程中)   批改过则抛异样
    final void checkForComodification() {if (modCount != expectedModCount)
            throw new ConcurrentModificationException();}
}

这里的 ListIterator 有点强

• ListIterator 只能用于 List 及其子类型。
• 有 add()办法, 能够往链表中增加对象
• 能够通过 hasNext()和 next()往后程序遍历, 也能够通过 hasPrevious()和 previous()实现往前遍历
• 能够通过 nextIndex()和 previousIndex()返回以后索引处的地位
• 能够通过 set()实现以后遍历对象的批改

九、总结

好了, 又到了总结的时候, 置信各位认真看完的应该对链表的基本操作十分相熟了.

上面咱们来总结一下 LinkedList 的关键点

LinkedList 关键点

• 底层是双向链表存储数据, 并且记录了头节点和尾节点
• 增加元素十分快, 如果是增加到头部和尾部的话更快, 因为曾经记录了头节点和尾节点, 只须要链接一下就行了. 如果是增加到链表的两头局部的话, 那么多一步操作, 须要先找到增加索引处的元素(因为须要链接到这里), 能力进行增加.
• 遍历的时候, 倡议采纳 forEach()进行遍历, 这样能够在每次获取下一个元素时都十分轻松 (next = next.next;). 而后如果是通过fori 和get(i)的形式进行遍历的话, 效率是极低的, 每次 get(i) 都须要从最后面 (或者最初面) 开始往后查找 i 索引处的元素, 效率很低.
• 删除也是十分快, 只须要改变一下指针就行了, 代价很小.

本文有写的不对中央, 还请多多包涵, 欢送批评指正.

这是我的笔记的其中一篇，须要看其余笔记的请移步 https://github.com/xfhy/Andro…，欢送 star、fork.