本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

前言

大家好，我是小彭。

在上一篇文章里，咱们聊到了基于动静数组 ArrayList 线性表，明天咱们来探讨一个基于链表的线性表 —— LinkedList。

小彭的 Android 交换群 02 群曾经建设啦，扫描文末二维码进入~

思维导图：

1. LinkedList 的特点

1.1 说一下 ArrayList 和 LinkedList 的区别？

  • 1、数据结构： 在数据结构上，ArrayList 和 LinkedList 都是 “线性表”，都继承于 Java 的 List 接口。另外 LinkedList 还实现了 Java 的 Deque 接口，是基于链表的栈或队列，与之对应的是 ArrayDeque 基于数组的栈或队列；
  • 2、线程平安： ArrayList 和 LinkedList 都不思考线程同步，不保障线程平安；

  • 3、底层实现： 在底层实现上，ArrayList 是基于动静数组的，而 LinkedList 是基于双向链表的。事实上，它们很多个性的区别都是因为底层实现不同引起的。比如说：

    • 在遍历速度上： 数组是一块间断内存空间，基于局部性原理可能更好地命中 CPU 缓存行，而链表是离散的内存空间对缓存行不敌对；
    • 在访问速度上： 数组是一块间断内存空间，反对 O(1) 工夫复杂度随机拜访，而链表须要 O(n) 工夫复杂度查找元素；
    • 在增加和删除操作上： 如果是在数组的开端操作只须要 O(1) 工夫复杂度，但在数组两头操作须要搬运元素，所以须要 O(n)工夫复杂度，而链表的删除操作自身只是批改援用指向，只须要 O(1) 工夫复杂度（如果思考查问被删除节点的工夫，复杂度剖析上仍然是 O(n)，在工程剖析上还是比数组快）；
    • 额定内存耗费上： ArrayList 在数组的尾部减少了闲置地位，而 LinkedList 在节点上减少了前驱和后继指针。

1.2 LinkedList 的多面人生

在数据结构上，LinkedList 不仅实现了与 ArrayList 雷同的 List 接口，还实现了 Deque 接口（继承于 Queue 接口）。

Deque 接口示意一个双端队列（Double Ended Queue），容许在队列的首尾两端操作，所以既能实现队列行为，也能实现栈行为。

Queue 接口：

回绝策略抛异样返回非凡值
入队（队尾）add(e)offer(e)
出队（队头）remove()poll()
察看（队头）element()peek()

Queue 的 API 能够分为 2 类，区别在于办法的回绝策略上：

  • 抛异样：

    • 向空队列取数据，会抛出 NoSuchElementException 异样；
    • 向容量满的队列加数据，会抛出 IllegalStateException 异样。

  • 返回非凡值：

    • 向空队列取数据，会返回 null；
    • 向容量满的队列加数据，会返回 false。

Deque 接口：

Java 没有提供规范的栈接口（很好奇为什么不提供），而是放在 Deque 接口中：

回绝策略抛异样等价于
入栈push(e)addFirst(e)
出栈pop()removeFirst()
察看（栈顶）peek()peekFirst()

除了规范的队列和栈行为，Deque 接口还提供了 12 个在两端操作的办法：

回绝策略抛异样返回值
减少addFirst(e)/ addLast(e)offerFirst(e)/ offerLast(e)
删除removeFirst()/ removeLast()pollFirst()/ pollLast()
察看getFirst()/ getLast()peekFirst()/ peekLast()

2. LinkedList 源码剖析

这一节，咱们来剖析 LinkedList 中次要流程的源码。

2.1 LinkedList 的属性

  • LinkedList 底层是一个 Node 双向链表，Node 节点中会持有数据 E 以及 prev 与next 两个指针；
  • LinkedList 用 first 和 last 指针指向链表的头尾指针。

LinkedList 的属性很好了解的，不出意外的话又有小朋友进去举手发问了：

  • ♀️ 疑难 1：为什么字段都不申明 private 关键字？

这个问题间接答复吧。我的了解是：因为外部类在编译后会生成独立的 Class 文件，如果外部类的字段是 private 类型，那么编译器就须要通过办法调用，而 non-private 字段就能够间接拜访字段。

  • ♀️ 疑难 2：为什么字段都申明 transient 关键字？

这个问题咱们在剖析源码的过程中答复。

疑难比 ArrayList 少很多，LinkedList 真香（还是别快乐得太早吧）。

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {    // 疑难 1：为什么字段都不申明 private 关键字？    // 疑难 2：为什么字段都申明 transient 关键字？    // 元素个数    transient int size = 0;    // 头指针    transient Node<E> first;    // 尾指针    transient Node<E> last;    // 链表节点    private static class Node<E> {        // 节点数据        // （类型擦除后：Object item;）        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;        }    }}

2.2 LinkedList 的构造方法

LinkedList 有 2 个构造方法：

  • 1、无参构造方法： no-op；
  • 2、带汇合的结构： 在链表开端增加整个汇合，外部调用了 addAll 办法将整个汇合增加到数组的开端。
// 无参构造方法public LinkedList() {}// 带汇合的构造方法public LinkedList(Collection<? extends E> c) {    this();    addAll(c);}// 在链表尾部增加汇合public boolean addAll(Collection<? extends E> c) {    // 索引为 size，等于在链表尾部增加    return addAll(size, c);}

2.3 LinkedList 的增加办法

LinkedList 提供了十分多的 addXXX 办法，外部都是调用一系列 linkFirst、linkLast 或 linkBefore 实现的。如果在链表两头增加节点时，会用到 node(index) 办法查问指定地位的节点。

其实，咱们会发现所有增加的逻辑都能够用 6 个步骤概括：

  • 步骤 1： 找到插入地位的后继节点（在头部插入就是 first，在尾部插入就是 null）；
  • 步骤 2： 结构新节点；
  • 步骤 3： 将新节点的 prev 指针指向前驱节点（在头部插入就是 null，在尾部插入就是 last）；
  • 步骤 4： 将新节点的 next 指针指向后继节点（在头部插入就是 first，在尾部插入就是 null）；
  • 步骤 5： 将前驱节点的 next 指针指向新节点（在头部插入没有这个步骤）；
  • 步骤 6： 将后继节点的 prev 指针指向新节点（在尾部插入没有这个步骤）。

剖析一下增加办法的工夫复杂度，辨别在链表两端或两头增加元素的状况共：

  • 如果是在链表首尾两端增加： 只须要 O(1) 工夫复杂度；
  • 如果在链表两头增加： 因为须要定位到增加地位的前驱和后继节点，所以须要 O(n) 工夫复杂度。如果当时曾经取得了增加地位的节点，就只须要 O(1) 工夫复杂度。

增加办法

public void addFirst(E e) {    linkFirst(e);}public void addLast(E e) {    linkLast(e);}public boolean add(E e) {    linkLast(e);    return true;}public void add(int index, E element) {    checkPositionIndex(index);    if (index == size)        // 在尾部增加        linkLast(element);    else        // 在指定地位增加        linkBefore(element, node(index));}public boolean addAll(Collection<? extends E> c) {    return addAll(size, c);}// 在链表头部增加private void linkFirst(E e) {    // 1. 找到插入地位的后继节点（first）    final Node<E> f = first;    // 2. 结构新节点    // 3. 将新节点的 prev 指针指向前驱节点（null）    // 4. 将新节点的 next 指针指向后继节点（f）    // 5. 将前驱节点的 next 指针指向新节点（前驱节点是 null，所以没有这个步骤）    final Node<E> newNode = new Node<>(null, e, f);    // 批改 first 指针    first = newNode;    if (f == null)        // f 为 null 阐明首个增加的元素，须要批改 last 指针        last = newNode;    else        // 6. 将后继节点的 prev 指针指向新节点        f.prev = newNode;    size++;    modCount++;}// 在链表尾部增加void linkLast(E e) {    final Node<E> l = last;    // 1. 找到插入地位的后继节点（null）    // 2. 结构新节点    // 3. 将新节点的 prev 指针指向前驱节点（l）    // 4. 将新节点的 next 指针指向后继节点（null）    final Node<E> newNode = new Node<>(l, e, null);    // 批改 last 指针    last = newNode;    if (l == null)        // l 为 null 阐明首个增加的元素，须要批改 first 指针        first = newNode;    else        // 5. 将前驱节点的 next 指针指向新节点        l.next = newNode;    // 6. 将后继节点的 prev 指针指向新节点（后继节点是 null，所以没有这个步骤）    size++;    modCount++;}// 在指定节点前增加// 1. 找到插入地位的后继节点void linkBefore(E e, Node<E> succ) {    final Node<E> pred = succ.prev;    // 2. 结构新节点    // 3. 将新节点的 prev 指针指向前驱节点（pred）    // 4. 将新节点的 next 指针指向后继节点（succ）    final Node<E> newNode = new Node<>(pred, e, succ);    succ.prev = newNode;    if (pred == null)        first = newNode;    else        // 5. 将前驱节点的 next 指针指向新节点        pred.next = newNode;    size++;    modCount++;}// 在指定地位增加整个汇合元素// index 为 0：在链表头部增加// index 为 size：在链表尾部增加public boolean addAll(int index, Collection<? extends E> c) {    checkPositionIndex(index);    // 事实上，c.toArray() 的理论类型不肯定是 Object[]，有可能是 String[] 等    // 不过，咱们是通过 Node中的item 承接的，所以不必放心 ArrayList 中的 ArrayStoreException 问题    Object[] a = c.toArray();    // 增加的数组为空，跳过    int numNew = a.length;    if (numNew == 0)        return false;    // 1. 找到插入地位的后继节点    // pred：插入地位的前驱节点    // succ：插入地位的后继节点    Node<E> pred, succ;    if (index == size) {        succ = null;        pred = last;    } else {        // 找到 index 地位本来的节点，插入后变成后继节点        succ = node(index);        pred = succ.prev;    }    // 插入汇合元素    for (Object o : a) {        E e = (E) o;        // 2. 结构新节点        // 3. 将新节点的 prev 指针指向前驱节点        Node<E> newNode = new Node<>(pred, e, null);        if (pred == null)            // pred 为 null 阐明是在头部插入，须要批改 first 指针            first = newNode;        else            // 5. 将前驱节点的 next 指针指向新节点            pred.next = newNode;        // 批改前驱指针        pred = newNode;    }    if (succ == null) {        // succ 为 null 阐明是在尾部插入，须要批改 last 指针        last = pred;    } else {        // 4. 将新节点的 next 指针指向后继节点        pred.next = succ;        // 6. 将后继节点的 prev 指针指向新节点        succ.prev = pred;    }    // 数量减少 numNew    size += numNew;    modCount++;    return true;}// 将 LinkedList 转化为 Object 数组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;}

在链表两头增加节点时，会用到 node(index) 办法查问指定地位的节点。能够看到维持 first 和 last 头尾节点的作用又施展进去了：

  • 如果索引地位小于 size/2，则从头节点开始找；
  • 如果索引地位大于 size/2，则从尾节点开始找。

尽管，咱们从复杂度剖析的角度看，从哪个方向查问是没有区别的，工夫复杂度都是 O(n)。但从工程剖析的角度看还是有区别的，从更凑近指标节点的地位开始查问，理论执行的工夫会更短。

查问指定地位节点

// 寻找指定地位的节点，工夫复杂度：O(n)Node<E> node(int index) {    if (index < (size >> 1)) {        // 如果索引地位小于 size/2，则从头节点开始找        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        // 如果索引地位大于 size/2，则从尾节点开始找        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

LinkedList 的删除办法其实就是增加办法的逆运算，咱们就不反复剖析了。

// 删除头部元素public E removeFirst() {    final Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return unlinkFirst(f);}// 删除尾部元素public E removeLast() {    final Node<E> l = last;    if (l == null)        throw new NoSuchElementException();    return unlinkLast(l);}// 删除指定元素public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));}

2.4 LinkedList 的迭代器

Java 的 foreach 是语法糖，实质上也是采纳 iterator 的形式。因为 LinkedList 自身就是双向的，所以 LinkedList 只提供了 1 个迭代器：

  • ListIterator<E> listIterator()： 双向迭代器

与其余容器类一样，LinkedList 的迭代器中都有 fail-fast 机制。如果在迭代的过程中发现 expectedModCount 变动，阐明数据被批改，此时就会提前抛出 ConcurrentModificationException 异样（当然也不肯定是被其余线程批改）。

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;    // 创立迭代器时会记录外部类的 modCount    private int expectedModCount = modCount;    ListItr(int index) {        next = (index == size) ? null : node(index);        nextIndex = index;    }    public E next() {        // 更新 expectedModCount        checkForComodification();        ...    }    ...}

2.5 LinkedList 的序列化过程

  • ♀️ 疑难 2：为什么字段都申明 transient 关键字？

LinkedList 重写了 JDK 序列化的逻辑，不序列化链表节点，而只是序列化链表节点中的无效数据，这样序列化产物的大小就有所升高。在反序列时，只须要依照对象程序顺次增加到链表的开端，就能复原链表的程序。

// 序列化和反序列化只思考无效数据// 序列化过程private void writeObject(java.io.ObjectOutputStream s)    throws java.io.IOException {    // Write out any hidden serialization magic    s.defaultWriteObject();    // 写入链表长度    s.writeInt(size);    // 写入节点上的无效数据    for (Node<E> x = first; x != null; x = x.next)        s.writeObject(x.item);}// 反序列化过程private void readObject(java.io.ObjectInputStream s)    throws java.io.IOException, ClassNotFoundException {    // Read in any hidden serialization magic    s.defaultReadObject();    // 读取链表长度    int size = s.readInt();            // 读取无效元素并用 linkLast 增加到链表尾部    for (int i = 0; i < size; i++)        linkLast((E)s.readObject());}

2.6 LinkedList 的 clone() 过程

LinkedList 中的 first 和 last 指针是援用类型，因而在 clone() 中须要实现深拷贝。否则，克隆后两个 LinkedList 对象会相互影响：

private LinkedList<E> superClone() {    try {        return (LinkedList<E>) super.clone();    } catch (CloneNotSupportedException e) {        throw new InternalError(e);    }}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;}

2.7 LinkedList 如何实现线程平安？

有 5 种形式：

  • 办法 1 - 应用 Collections.synchronizedList 包装类： 原理也是在所有办法上减少 synchronized 关键字；
  • 办法 2 - 应用 ConcurrentLinkedQueue 容器类： 基于 CAS 无锁实现的线程平安队列；
  • 办法 3 - 应用 LinkedBlockingQueue 容器： 基于加锁的阻塞队列，适宜于带阻塞操作的生产者消费者模型；
  • 办法 4 - 应用 LinkedBlockingDeque 容器： 基于加锁的阻塞双端队列，适宜于带阻塞操作的生产者消费者模型；
  • 办法 5 - 应用 ConcurrentLinkedDeque 容器类： 基于 CAS 无锁实现的线程平安双端队列。

3. 总结

  • 1、LinkedList 是基于链表的线性表，同时具备 List、Queue 和 Stack 的行为；

  • 2、在查问指定地位的节点时，如果索引地位小于 size/2，则从头节点开始找，否则从尾节点开始找；

  • 3、LinkedList 重写了序列化过程，只解决链表节点中无效的元素；

  • 4、LinkedList 和 ArrayList 都不思考线程同步，不保障线程平安。

在上一篇文章里，咱们提到了 List 的数组实现 ArrayList，而 LinkedList 不仅是 List 的链表实现，同时还是 Queue 和 Stack 的链表实现。那么，在 Java 中的 Queue 和 Stack 的数组实现是什么呢，这个咱们在下篇文章探讨，请关注。

小彭的 Android 交换群 02 群