别孤寡了，看看这篇 LinkedList 吧

作者爱说话

Hello，我是 isysc

这是坚持原创的 第8篇 文章（上星期没发的 =，=）

每次写完文章都感觉，糟了糟了，爆文预定了，怎么办怎么办。等到正式发出去的时候，才知道，原来是想太多了。

每次写文章的选题都是一件很纠结的事，就比如我从下午 5.30 坐在电脑前想选题到了 6 点，终于决定好了，还是先去吃饭吧。

回来的路上终于有了灵感，写一些集合相关的源码？

Got it

背景引入

虽然今天阳光明媚，但是林布丁的心里却下起了雨，不是因为女朋友的傲娇，而是今天上午面试官说的 “ ArrayList和LinkedList的区别都不会，你还是回家种地吧 ”

失落的林布丁来到了表哥林步动的家里 “步动表哥，你为啥一直盯着屏幕？”

步动：就你话多，找我有什么事？

布丁：表哥，今天面试官问我 ArrayList 和 LinkedList 的区别，ArrayList我倒是知道一点点，LinkedList 我都不知道是啥玩意，然后面试官就和我说，8月是种白菜的好季节。表哥你能不能和我讲讲，什么是 LinkedList，最好能从源码角度给我讲讲？

步动：嘴巴好像有点渴。

布丁：表哥，你给我讲明白了，我请你喝一个星期的奈雪的茶

步动：安排

什么是 LinkedList

你不懂的东西只是因为你没看过它的源码 –

秉承着万物皆可 new 的原则（女朋友除外）

我们先来 new 一个 LinkedList ，然后点进去看一看，会不会有什么神奇的事情发生。

步动：看！出现了一堆的注释，表弟你只要全文熟读并背诵就可以解决面试官了。今天就讲到这里了，快去给我买奶茶吧。

布丁：表哥，你也太水了叭，这么多英文我哪里看得懂，你就不能给我概括一下吗？

步动：好吧，谁叫我是暖男，毕竟是过了英语 5 级的男人，我给你翻译概括一下，要是有不对的地方，你就自己琢磨下，也别和我说。

“

想要看原汁原味的注释，可以去 idea 里 new 一个看看，这里贴出来篇幅就过长了。也可以看看官网介绍 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

步动：这里注释主要写的就是

Linkedlist 使用“双向链表”来实现 List 与 Deque 接口。实现了所有 List 接口中的方法，并且允许存放所有元素，包括 Null
所有的操作都可通过双向链表完成。通过从开头或者结尾遍历集合，去接近要操作的那个元素。
请注意，LinkedList 是非同步的。如果多个线程同时操作 LinkedList 实例，并且至少一个线程在结构上的修改链表，则它必须要保证线程的同步。（结构性修改：增加或删除元素，或者调整数组大小，仅仅修改属性的值不属于结构性修改）典型的实现是同步操作数组。
如果这种对象不存在，又想同步集合，可以这样写

 List list = Collections.synchronizedList(new LinkedList(...))

布丁：表哥，你说完了？我虽然看不懂英语，但是我数的清楚，一共7段英文，你就给我翻译了3段，剩下的3段呢，你是不是不行啊，表哥？

步动：男人怎么能说不行，剩下两段是关于 fail-fast 特性的，区区几句话段说不清楚，我在网上给你找了一篇文章，你回头关注下 码儿嘟嘟骑 回复【fail-fast】就可以看到了，二维码我给给你贴在信下面了，关注回复还有大厂面试资料，别怪表哥没有告诉你。

布丁：表哥我关注啦。表哥，我听你的意思是 LinkedList 底层结构就是双向链表是吗？

步动：是的，我再给你详细讲下双向链表到底是啥玩意吧。让我给你整个图

布丁：什么 first，Node，prev 我都不看不懂

步动：我给你解释下吧

Node 代表链表中的节点。具有两个属性 prev 代表前一个节点 next 相反就代表下一个节点
first 代表着是双向链表的头节点，它的前一个节点由于一无所有，那就是 null
last 是双向链表的尾节点，它的后一个节点同样穷困潦倒，所以也是 null
当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null

口说无凭，上源码

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

布丁：我明白啦，表哥，我记住啦。那你再给我讲讲 LinkedList 的构造函数吧？

LinkedList 构造函数

步动：LinkedList 的构造函数写的非常优雅，你看。

// 无参构造，构造一个空的双向链表
public LinkedList() {}

// 有参构造
public LinkedList(Collection<? extends E> c) {
this();
// 使用addAll方法，实际上就是使用遍历c并且采用头插法进行双向链表插入值
addAll(c); // 具体不展开啦，
}

布丁：哦哦，那表哥，那给我具体讲讲 CRUD 吧。详细讲讲

LinkedList 的 CRUD

add

布动：我们往下扒拉扒拉源码可以看见

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

一个 addFirst 和 addLast 你自己看就完事了

布丁：表哥，你这样那我就只能请你喝古茗了

步动：你自己看也费劲，肯定得表哥给你讲讲你也好吸收嘛，那我们先讲讲 addFirst

// 从头部追加
private void linkFirst(E e) {
    // 头节点赋值给临时变量
    final Node<E> f = first;
    // 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值
    final Node<E> newNode = new Node<>(null, e, f);
    // 新建节点成为头节点
    first = newNode;
    // 如果头节点为空，就是整个链表都为空，那么头尾节点是一个节点
    if (f == null)
        last = newNode;
    // 上一个头节点的前一个节点指向当前节点（有点绕口，多读两遍）
    else
        f.prev = newNode;
    // 修改 LinkedList 大小
    size++;
    // 修改 LinkedList 的修改统计数：用来实现 fail-fast 机制。
    modCount++;
}

中心思想就是改变节点指向，修改 LinkedList 大小和统计数

// 从尾部开始追加节点
void linkLast(E e) {
    // 利用一个临时变量存放尾节点数据
    final Node<E> l = last;
    // 新建新的节点，初始化入参含义：
    // l 是新节点的前一个节点，当前值是尾节点值
    // e 表示当前新增节点，当前新增节点后一个节点是 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 新建节点追加到尾部
    last = newNode;
    // 如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点
    if (l == null)
        first = newNode;
    // 否则把前尾节点的下一个节点，指向当前尾节点。
    else
        l.next = newNode;
    // 大小和版本更改
    size++;
    modCount++;
}

总的来说，addFirst 和 addLast 两个方法是非常相似的，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向。

布丁：步动表哥，那我默认 add 是添加到尾部还是头部啊？

步动：如果你 new 一个 LinkedList 然后直接 add，默认是添加到尾部。

remove

布丁：那表哥，我如何从链表中删除一个元素呢？

步动：删除元素和增加也是类似的，可以从头部删除，也可以从尾巴删除，remove 操作会将你想要删除的节点的值，前后都指向 null，你知道为什么都要指向 null 吗？

布丁：无依无靠？方便 GC

步动：对，接下来给你看看 remove 源码

//从头删除节点 f 是代表链表头节点
private E unlinkFirst(Node<E> f) {
    // 取出头节点的值，作为一会方法的返回值
    final E element = f.item;
    // 取出头节点的下一个节点
    final Node<E> next = f.next;
    // 原注释就是 help GC， 就是帮助 GC 回收头节点
    f.item = null;
    f.next = null;
    // 头节点的下一个节点，取代原先头节点的霸主位置，成为新的头节点
    first = next;
    // 如果 next 为空，表明链表为空
    if (next == null)
        last = null;
    // 链表不为空，头节点的前一个节点指向 null
    else
        next.prev = null;
    // 修改链表大小和版本
    size--;
    modCount++;
    return element;
}

步动：从尾部删除的源码我就不给你说了，和这个也非常类似，给你自己推敲推敲

布丁：行叭，表哥，我看其实链表的节点新增、删除都好简单啊，仅仅把前后节点的指向修改下就好了，所以 LinkedList 新增和删除速度是不是很快？

步动：对！你很聪明哦

get

// 根据链表索引位置查询节点
Node<E> node(int index) {
    // 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思
    // 用位运算就是为了加快计算速度，冲呀
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 直到 for 循环到 index 的前一个 node 停止
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果 index 处于队列的后半部分，就从尾巴开始找
        // 所做的一切都是为了加快 get 的速度，用心良苦
        Node<E> x = last;
        // 直到 for 循环到 index 的后一个 node 停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

步动：LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，如果你不知道什么是二分法，那就不知道吧。

步动：简单来说，LinkedList的查找首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之尾巴找。布丁，你知道这样做有什么好处吗？

布丁：表哥我刚百度到二分法，就是通过这种方式，可以让循环的次数至少降低了一半呀，提高了查找的性能。

set

布丁：快快快，表哥，趁热打铁，给我讲讲 LinkedList 是怎么更新的？

步动：好滴

public E set(int index, E element) {
    // 检查是否越界，你传入的 index 必须大于等于0，小于 LinkedList 长度
    // 什么，你非得传小于 0，那不好意思，抛 IndexOutOfBoundsException 异常
    checkElementIndex(index);
    // 查处 index 位置原先的居住主人
    Node<E> x = node(index);
    // 取出即将被替换的值，以便于一会扔出去
    E oldVal = x.item;
    // 新王登基
    x.item = element;
    // 旧王扔掉
    return oldVal;
}

LinkedList 的迭代器

布丁：好的，我明白啦，表哥，最后一个知识点啦，你给我讲 LinkedList 的迭代器？

步动：害，不争气的表弟。快讲完，我要吃饭啦。

步动：表弟，你知道吗？因为 LinkedList 要实现双向的迭代访问，所以我们通常的使用 Iterator 接口肯定不行了（Iterator 只支持从头到尾的访问）所以 Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法，如下所示：

迭代顺序	方法
从尾到头迭代方法	hasPrevious、previous、previousIndex
从头到尾迭代方法	hasNext、next、nextIndex

口说无凭，看源码

LinkedList 实现了 ListIterator 接口

// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 上一次执行 next() 或者 previos() 方法时的节点位置
    private Node<E> lastReturned;
    // 下一个节点
    private Node<E> next;
    // 下一个节点的索引位置
    private int nextIndex;
    // 期望版本号；modCount：目前最新版本号，也是 fail-fast 的相关知识点
    private int expectedModCount = modCount;
    …………
}

我们先来看下从头到尾方向的迭代：

// 判断还有没有下一个元素
public boolean hasNext() {
    // 下一个节点的索引小于链表的大小
    return nextIndex < size;
}

// 取下一个元素
public E next() {
    // 检查期望版本号有无发生变化
    checkForComodification();
    // 再次检查
    if (!hasNext())
        throw new NoSuchElementException();
    // next 是当前节点，在上一次执行 next() 方法时被赋值的。
    // 第一次执行时，是在初始化迭代器的时候，next 被赋值的
    lastReturned = next;
    // next 是下一个节点了，为下次迭代做准备
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

布丁：就是直接取当前节点的下一个节点呗，那表哥再讲讲从尾到头迭代的过程

步动：好的

// 如果上次节点索引位置大于 0，就还有节点可以迭代
public boolean hasPrevious() {
    return nextIndex > 0;
}
// 取前一个节点
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();
    // next 为空场景：
    // 1:说明是第一次迭代，取尾节点(last);
    // 2:上一次操作把尾节点删除掉了
    // next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)
    lastReturned = next = (next == null) ? last : next.prev;
    // 索引位置变化
    nextIndex--;
    return lastReturned.item;
}

步动：最后再讲讲迭代器的删除，LinkedList 在删除元素时，最好通过迭代器进行删除

public void remove() {
    checkForComodification();
    // lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况：
    // lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错
    // lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值
    if (lastReturned == null)
        throw new IllegalStateException();
    Node<E> lastNext = lastReturned.next;
    // 删除当前节点
    unlink(lastReturned);
    // next == lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下
    // 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等
    if (next == lastReturned)
        // 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 next
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;