走进 JDK 之 LinkedList

Scroll Down

走进 JDK 系列第 15 篇

概述

如果你了解链表的基本结构的话,LinkedList 的源码其实还是比较容易理解的。LinkedList 是基于双向链表实现的,与 ArrayList 不同的是,它在内存中不占用连续的内存空间,相连元素之间通过 “链” 来链接。对于单链表,每个节点有一个 后继指针 指向下一个节点。对于双向链表来说,除了后继指针外,它还要一个 前驱指针 指向前一个节点。那么,双向链表有什么好处呢?既然有了前驱指针,在遍历的时候就可以向前遍历,在下面的源码分析中可以看到,这是单链表所不具备的功能。

前面介绍 ArrayList 的时候说过,数组具备随机访问能力,其根据下标随机访问的时间复杂度是 O(1)。同样,为了保证内存的连续性,其 插入删除 操作就相对低效的多。而链表正好与其相反,其不具备随机访问能力,但是 插入删除 就相对高效,仅仅只需修改 后继指针前驱指针 指向的节点即可。其插入和删除操作的时间复杂度均为 O(1),但这个 O(1) 其实也不是很严谨。删除指定节点,还是删除值等于给定值的节点,单链表还是双向链表,其实时间复杂度的表现都是不一样的,下面的源码解析中也会有所体现。好了,关于链表就说这么多了,下面来进入 LinkedList 的源码分析。

首先看一下 LinkedList 的 UML 图:

源码解析

类声明

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}
  • 继承了抽象类 AbstractSequentialList,它提供了一些集合类型无关的基本方法的实现,如 get set add remove 等。通常实现它的集合类型不具备随机访问能力,这和 AbstractList 是相对立的。

  • 实现了 List 接口

  • 实现了 Deque 接口,说明也可以当做一个双端队列,源码中也实现了相关方法。

  • 实现了 Cloneable 接口,提供克隆能力。和 ArrayList 一样,也是浅拷贝。

  • 实现了 Serializable 接口,提供序列化能力

成员变量

transient int size = 0; // 表示链表大小
transient Node<E> first; // 头结点
transient Node<E> last; // 尾节点
private static final long serialVersionUID = 876323262645176354L;

顺便看一下结点 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;
    }
}

每个结点都包含指向前一个结点的前驱指针 prev,和指向后一个结点的后继指针 next。一般头结点的前驱指针和尾节点的后继指针都指向 null。

构造函数

public LinkedList() { }
    
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

第一个是默认的无参构造,会构建一个空链表。第二个根据参数中的集合 通过 addAll() 方法构造链表,链表中的元素顺序根据集合 c 的迭代器的迭代顺序。

方法

你可以翻一下 LinkedList 的 API 列表,提供了许许多多的方法,其实很多都是重复的。它实现了 Deque 接口中的方法,重写了 AbstractSequentialList 类的方法,总结一下就是各种增删改查操作,最后调用的都是自己的私有方法 linkxxx/unlinkxxx 等,很好的做到了隔离,也是一种值得学习的设计思想。下面就优先来看一下这些方法。

linkFirst(E e)

// 将 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) // 如果链表为空, e 节点就是尾节点
        last = newNode;
    else
        f.prev = newNode; // 链表不为空,插入 e 节点,并将原头结点的 prev 指向 e 节点
    size++;
    modCount++;
}

链表为空的话,插入的 e 既是头结点也是尾节点。

链表不为空的话,就移动原头结点的前驱指针。

linkLast(E e)

// 将 e 置为尾结点
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode; // 如果链表为空, e 节点就是头节点
    else
        l.next = newNode; // 链表不为空,插入 e 节点,并将原尾结点的 next 指向 e 节点
    size++;
    modCount++;
}

链表为空的话,插入的 e 既是头结点也是尾节点。

链表不为空的话,就移动原尾结点的后继指针。

linkBefore(E e, Node succ)

// 在节点 succ 前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ); // 构建新结点
    succ.prev = newNode; // 将 succ 的 prev 指针指向新结点
    if (pred == null) // pred 为 null,说明 succ 原来就是头结点,现在要更新头结点
        first = newNode;
    else
        pred.next = newNode; // 将 succ 的前一个结点的 next 指针指向新结点
    size++;
    modCount++;
}

原理也很简单,你可以想象成打上结的绳子,你只需要把 succ 结点打开,然后把需要插入的结点系上去就可以了,时间复杂度为 O(1)。当然,这是双向链表。对于单向链表还是 O(1) 吗?显然不是的,因为在单向链表中你没办法执行下面这行代码:

final Node<E> pred = succ.prev;

也就是说你没办法直接拿到 succ 的前驱结点,也就没法直接将 succ 的前一个结点的 next 指针指向新结点。你只能通过遍历去获取前驱结点。所以,对于单链表来说,插入元素的时间复杂度还是 O(n)

unlinkFirst(Node f)

// 移除头结点 f
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 头结点置空以便 GC
    first = next;
    if (next == null) // next 为空,说明链表原来只有一个元素
        last = null;
    else
        next.prev = null; // 将 next 的 prev 置空,此时 next 是头结点
    size--;
    modCount++;
    return element;
}

这里默认参数中的 f 结点就是头结点。如果链表中原本只有一个元素,那么头尾结点都要置空。如果多于一个元素,只要把头结点的下一个结点的前驱指针指向 null 就可以了。

unlinkLast(Node l)

// 移除尾节点 l
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 头结点置空以便 GC
    last = prev;
    if (prev == null) // prev 为空,说明链表原来只有一个元素
        first = null;
    else
        prev.next = null; // 将 prev 的 next 置空,此时 prev 是尾结点
    size--;
    modCount++;
    return element;
}

unlinkfirst 基本一致,只要把尾结点的前一个结点的后继指针指向 null 就可以了。

unlink(Node x)

// 移除指定非空节点 x
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) { // x 是头结点
        first = next;
    } else {
        prev.next = next; // 将 x 的 next 指向 x 后面一个节点
        x.prev = null;
    }

    if (next == null) { // x 是尾节点
        last = prev;
    } else {
        next.prev = prev; // 将 x 的 prev 指向 x 前面一个节点
        x.next = null;
    }

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

代码也比较简单,同时修改前一个结点的后继指针和后一个结点的前驱指针就可以了,要注意参数结点是头结点或者尾节点的特殊情况。时间复杂度也是 O(1),对于单链表是 O(n)

上面的插入和删除都是针对指定结点的,还有一种情况是针对指定值的。比如,对于一个存储 int 值的链表,我要删除值为 1 的结点,其时间复杂度还是 O(1) 吗?下面来看看 remove(Object o) 方法。

remove(Object o)

public boolean remove(Object o) {
    if (o == null) { // 删除 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) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

很显然,对于删除值等于指定值的结点,时间复杂度也是 O(n)。循环遍历得到该结点之后再调用 unlink() 方法去删除。还要注意一点,该方法仅仅删除第一次出现的值等于指定值的结点,链表是允许重复元素的。

说完了插入和删除,我们再来看看查找。虽说链表的查找操作必然是 O(n) 的,但是 LinkedList 还是对查找操作做了相应的优化。下面来看一下 get() 方法。

get(int index)

// 返回指定位置的元素
public E get(int index) {
    checkElementIndex(index); // 边界检查
    return node(index).item; // 虽然时间复杂度仍然是 O(n),但只需遍历一半的链表
}

checkElementIndex 检测 index 是否越界。node() 方法用来获取 index 处的指定结点。

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 根据下标是否小于 size/2,每次只遍历半个链表
    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;
    }
}

得益于双向链表的特性,LinkedList 的查找每次只需遍历半个链表,虽然时间复杂度还是 O(n),但是是有实际上的性能提升的。

LinkedList 的方法就说这么多了,虽说大部分方法都没提到,但是剩下的方法基本都是依靠上面解析过的这些方法来实现的,也就没有单独拿出来说的必要了。我在源码文件中都进行了注释,感兴趣的可以到我的 Github 查看 LinkedList.java

总结

LinkedList 基于双向链表实现,内存中不连续,不具备随机访问,插入和删除效率较高,查找效率较低。使用上没有大小限制,天然支持扩容。

允许 null 值,允许重复元素。和 ArrayList 一样,也是 fail-fast 机制。在 走进 JDK 之 ArrayList(二) 中已经详细说明过 fail-fast 机制,这里就不再赘述了。

双向链表由于可以反向遍历,相较于单向链表在某些操作上具有性能优势,但是由于每个结点都需要额外的内存空间来存储前驱指针,所以双向链表相对来说需要占用更多的内存空间,这也是 空间换时间 的一种体现。

文章首发微信公众号: 秉心说 , 专注 Java 、 Android 原创知识分享,LeetCode 题解。

更多 JDK 源码解析,扫码关注我吧!