二、LinkedList源码分析

1、LinkedList概述

1）LinkedList是线程不安全的，允许元素为null的双向链表。
2）底层数据结构是链表，实现了Deque<E>接口，所以可作为一个双端队列。和ArrayList比，没有实现RandomAccess，所以它以下标随机访问元素速度较慢，即查询效率不高。
3）在根据下标index查询Node的时候，会根据index判断目标Node在前半段还是后半段，然后决定是顺序还是逆序查询，以提升时间效率。不过随着n的增大，总体时间效率依然很低。每次查询操作必须进行遍历。
4）因其底层数据结构是链表，可以在任何位置进行高效地插入和移除操作，即增删效率高。
5）LinkedList和Collection的关系：

2、LinkedList的数据结构

LinkedList的数据结构是：

说明：可以看出，LinkedList底层使用的双向链表结构。双向链表包含两个指针和一个element，element用来存放元素，pre指向前一个节点，next指向后一个节点，但是第一个节点（头节点）的pre指向null，最后一个节点（尾结点）的next指向null。

3、LinkedList源码分析

3.1继承结构和层次关系

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

LinkedList的继承结构：
LinkedList extends AbstractSequentialList
AbstractSequentialList extends AbstractList
AbstractList extends AbstractCollection
所有类都继承Object类，所以LinkedList的继承结构就是上图所示。

注意：
1）ArrayList只有四层，为什么LinkedList多了一层AbstractSequentialList的抽象类？
为了减少实现顺序遍历（例如LinkedList）这种类的工作，抽象出这种类的共同方法，若想实现链表形式的类就继承AbstractSequentialList，若想实现数组形式的类就继承AbstracList。
2）LinkedList实现了哪些接口？
①List<E>接口：ArrayList的父类AbstractList也实现了List<E>接口，为什么子类ArrayList还去实现一遍呢？开发这个collection 的作者Josh说，这其实是一个mistake，因为他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。
②Deque<E>接口：表示是一个双端队列，意味着LinkedList是双端队列的一种实现，所以，基于双端队列的操作在LinkedList中全部有效。
③Cloneable接口：是一个标记性接口，实现了该接口，表示该对象能被克隆，能使用Object.clone()方法。没实现该接口调用Object.clone()方法就会抛出CloneNotSupportedException。
④Serializable接口：实现该序列化接口，表明该类可以被序列化。什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。
⑤注意到没有RandomAccess接口：那么就推荐使用iterator遍历，或foreach，其原理就是iterator。

3.2成员变量

LinkedList的属性非常简单，一个头结点，一个尾结点，一个表示链表中实际元素个数的变量。注意：头结点、尾结点都有transient关键字修饰，这意味着在序列化时该域不会序列化。

//记录当前链表的长度（实际元素个数）
transient int size = 0;
//头结点
transient Node<E> first;
//尾结点
transient Node<E> last;

3.3构造方法

LinkedList有两个构造方法：
1）空参构造函数

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

2）有参构造函数
会调用无参构造函数，并且会把集合中所有元素添加到LinkedList中。

   //将集合c中的各个元素构建成LinkedList链表。
    public LinkedList(Collection<? extends E> c) {
        // 调用无参构造函数
        this();
        // 添加集合中所有的元素
        addAll(c);

3.4内部类（Node节点）

    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.5核心方法

3.5.1 增

add相关方法中主要用到三个辅助方法：
linkFirst(E e)：把参数中的元素作为链表的第一个元素。
linkLast(E e)：把参数中的元素作为链表的最后一个元素。
linkBefore(E e, Node<E> succ)：在非空节点succ前插入元素e。

1）boolean add(E e)：向链表尾部添加一个元素，具体添加到尾部的逻辑是由linkLast函数完成的。

//在尾部插入一个节点： add
public boolean add(E e) {
    linkLast(e);
    return true;
}

//生成新节点 并插入到 链表尾部， 更新 last/first 节点。
void linkLast(E e) { 
 //记录原尾部节点
    final Node<E> l = last;
//以原尾部节点为前置节点的新节点
    final Node<E> newNode = new Node<>(l, e, null);
//将新节点作为尾部节点
    last = newNode;
//判断一下l是否为空，若为空，说明原来的LinkedList为空，所以也需要把新节点设置为头节点。
    if (l == null)
        first = newNode;
    else
//否则将原尾节点的后置节点指向新节点（即现在的尾节点）
        l.next = newNode;
    size++;//修改size
    modCount++;//修改modCount
}

2）void add(int index, E element)：在指定下标处插入一个节点，具体添加的逻辑是由linkBefore函数完成的。

    public void add(int index, E element) {
        checkPositionIndex(index);//检查下标是否越界[0,size]
        if (index == size)//在尾节点后插入
            linkLast(element);
        else//在中间插入
            linkBefore(element, node(index));
    }

//检查下标是否越界[0,size]
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

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

    //在非空节点succ前，插入一个新节点e
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //pred 指向succ的前置节点
        final Node<E> pred = succ.prev;
        //构建新节点，其前置节点为pred，后置节点为succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        //修改succ的prev为新节点
        succ.prev = newNode;
        if (pred == null)
//如果之前的前置节点是空，说明succ是原头结点。
//所以将新节点改为现在的头节点
            first = newNode;
        else
//否则修改succ的前一个节点的next为新节点
            pred.next = newNode;
        size++;//修改数量
        modCount++;//修改modCount
    }

//获取下标为index的节点
    Node<E> node(int index) {
        // assert isElementIndex(index);
//通过下标获取某个node 的时候（增、查 ），
//判断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;
        }
    }

3）addAll方法
有两个重载函数，addAll(Collection<? extends E> c)型和addAll(int, Collection<? extends E>)型，平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。

//在尾部批量增加
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//以size为插入下标，插入集合c中所有元素
}

//以index为插入下标，插入集合c中所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//检查是否越界， [0,size] 闭区间

//先把集合转化为数组，然后为该数组添加一个新的引用a
    Object[] a = c.toArray();
    int numNew = a.length;//新增元素的数量
    if (numNew == 0)//如果新增元素数量为0，直接返回false
        return false;

//Node<E> succ：指代待添加节点的位置。
//Node<E> pred：指代待添加节点的前一个节点。
//依据新添加的元素的位置分为两个分支：
//①新添加的元素的位置位于LinkedList最后一个元素的后面。
//②新添加的元素的位置位于LinkedList中。
    Node<E> pred, succ;  
    if (index == size) {//在链表尾部追加数据
        succ = null;  //把succ设置为空
        pred = last;//pred指向尾节点。
    } else {
        succ = node(index);//succ指向待插入位置的节点
        pred = succ.prev; //pred指向succ节点的前一个节点
    }
    //链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的
    for (Object o : a) {//遍历要添加的节点。
        @SuppressWarnings("unchecked") E e = (E) o;
//构建新节点，新节点的prev用来存储pred节点，next设置为空
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) //如果pred是空，说明是头结点
            first = newNode;
        else//若pred不为null，则将pred的next 指向新节点
            pred.next = newNode;
//步进，把pred指向当前节点，为下次添加节点做准备
        pred = newNode;
    }

    if (succ == null) {
//循环插入结束后，判断如果succ 是null，说明是在队尾添加
        last = pred; //则将pred设置尾节点
    } else {
// 否则是在队中插入的节点，
//将pred的next指向succ，succ的prev指向pred
        pred.next = succ; 
        succ.prev = pred;
    }

    size += numNew;  // 修改数量size
    modCount++;  //修改modCount
    return true;
}

3）addFirst和addLast

    public void addFirst(E e) {
        linkFirst(e);//向头部添加节点
    }
    public void addLast(E e) {
        linkLast(e);//向尾部添加节点
    }

//向头部添加节点
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

小结：
1）一定会修改modCount。
2）LinkedList批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加。
3）通过下标index获取某个node 的时候，会根据index处于前半段还是后半段进行折半查找，以提升查询效率。

举例说明调用add函数和addAll函数后链表的状态：

　　　　List<Integer> lists = new LinkedList<Integer>();
　　　　lists.add(5);
　　　　lists.addAll(0, Arrays.asList(2, 3, 4, 5));

上述代码内部的链表结构如下：

3.5.2 删

remove相关方法中主要用到三个辅助方法：
unlinkFirst(Node<E> f)：删除LinkedList中第一个节点，并且返回删除的节点的值（使用前提是f是头节点，且不能为空）。
unlinkLast(Node<E> l)：删除LinkedList的最后一个节点，并且返回删除节点的值（该节点不为空）。
E unlink(Node<E> x)：删除一个节点（该节点不为空）。

  private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

  private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        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
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
//若前置节点为null，说明x是原头节点，则将头节点指向next
            first = next;
        } else {
//否则，将x的前置节点prev的next指向x的后置节点next
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
//若后置节点为null，说明x是原尾结点，则将尾结点指向prev
            last = prev;
        } else {
//否则，将x的后置节点next的prev指向x的前置节点prev
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

1)E remove()和E removeFirst()：删除头节点，具体删除的逻辑是由unlinkFirst函数完成的。

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

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

2）E remove(int index)：删除指定位置节点，具体删除的逻辑是由unlink函数完成的。

public E remove(int index) {
    checkElementIndex(index);//检查是否越界 下标[0,size)
    return unlink(node(index));//从链表上删除某节点
}

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

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

3）boolean remove(Object o)：删除指定节点，具体删除的逻辑是由unlink函数完成的。

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

4）E removeLast()：删除尾节点，具体删除的逻辑是由unlinkLast函数完成的。

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

小结：一定会修改modCount。

3.5.3 改set，不修改modCount

set也是先根据index找到Node，然后替换值，改不修改modCount。

public E set(int index, E element) {
    checkElementIndex(index); //检查越界[0,size)
    Node<E> x = node(index);//取出对应的Node
    E oldVal = x.item;//保存旧值 供返回
    x.item = element;//用新值覆盖旧值
    return oldVal;//返回旧值
}

3.5.4 查，不修改modCount

1）E get(int index)：根据index查询节点

public E get(int index) {
    checkElementIndex(index);//判断是否越界 [0,size)
    return node(index).item; //调用node()方法取出Node，并返回其值
}

2）int indexOf(Object o)：从头至尾遍历链表，根据节点查询对应下标，无此节点，则返回-1。

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {//如果目标对象是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;
    }

3）int lastIndexOf(Object o)：从尾至头遍历链表，根据节点查询对应下标，无此节点，则返回-1。

    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {[图片上传中...(listiterator.png-93c872-1592971851509-0)]

            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

4、LinkedList的迭代器

4.1ListItr内部类

private class ListItr implements ListIterator<E>
看继承结构，发现只继承了一个ListIterator：

有向后迭代的方法，还有向前迭代的方法，所以ListItr能让linkedList向后迭代，也能让linkedList向前迭代。

ListItr中的方法表明，在迭代的过程中，ListItr还能进行移除、修改、添加值的操作。

4.2DescendingIterator内部类

这个类还是调用的ListItr，作用是封装一下Itr中几个方法，让使用者以正常的思维去写代码。例如，在从后往前遍历的时候，也是跟从前往后遍历一样，使用next等操作，而不用使用特殊的previous。

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

5、总结

1）LinkedList本质上是一个能存储null值的双向链表，通过一个Node内部类实现的这种链表结构。
2）LinkedList实现了Deque接口，能当队列使用。
3）LinkedList在删除和增加等操作上性能好，ArrayList在查询的性能上好。
4）CRUD操作里，都涉及根据index去查找Node的操作。通过下标获取某个node 的时候，会根据index处于前半段还是后半段进行折半，以提升查询效率。

6、参考笔记

Java集合源码分析（二）LinkedList
面试必备：LinkedList源码解析（JDK8）
LinkedList源码解析（基于JDK1.8）

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,319评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,801评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,567评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,156评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,019评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,090评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,500评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,192评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,474评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,566评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,338评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,212评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,572评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,890评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,169评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,478评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,661评论 2赞 335