Java 容器源码分析之 LinkedList

概览

同 ArrayList 一样，LinkedList 也是对 List 接口的一种具体实现。不同的是，ArrayList 是基于数组来实现的，而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下：

1
2
3

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

LinkedList 继承自 AbstractSequentialList，实现了 List 接口，同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类，为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口，Deque 接口是一种双端队列，可以作为 FIFO 队列和 LIFO 队列（栈）来使用。LinkedList 支持所有元素，包括 null。

下面基于JDK 8 中的代码对LinkedList的实现加以分析。

底层结构

LinkedList 基于双向链表进行实现，并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样，使用 modCount 来记录结构化修改的次数，并依此实现 fail-fast 机制。

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

双向链表的节点结构如下，分别用 prev 和 next 指向该节点的前驱和后继结点。

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 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在双向链表的两端进行操作，也是基于对头和尾部元素的操作。总的来说，双向链表的操作并不复杂，下面简单地进行解析，大部分操作都是对以下几种操作的封装。

向头部添加元素

//将一个元素加入双向链表的头部
private void linkFirst(E e) {
    final Node<E> f = first;
    //新节点的前驱节点为null，后继节点为原来的头节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) //原来的头节点为空
        //新加入的节点是第一个也是最后一个
        last = newNode;
    else
        //修改原来头节点的前驱指向
        f.prev = newNode;
    //调整链表大小
    size++;
    //修改计数器
    modCount++;
}

向尾部添加元素

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;
    else
        l.next = newNode;
    size++;
    modCount++;
}

从中间插入元素

//在一个非空节点前插入元素
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;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    //修改大小
    size++;
    modCount++;
}

移除头部节点

//将头节点从链表移除
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    //引用修改为null，方便GC
    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; //后继

    //注意对前驱为null的处理
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    //注意对后继为null的处理
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

清空链表

主要是为了方便垃圾回收器进行垃圾回收。

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

根据索引获取元素

因为是双向链表，可向前遍历，也可向后遍历。查找时双向进行，靠近头节点则从前向后查找；靠近尾部，则从后向前查找。

//根据索引获取元素
Node<E> node(int index) {
    // assert isElementIndex(index);
    //双向查找，根据index和size判断
    //前半段，从头节点向后查找
    //后半段，从尾节点向前查找
    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;
    }
}

反查一个元素的索引

第一次出现：

public int indexOf(Object o) {
    int index = 0;
    if (o == 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;
}

最后一次出现，从后向前查找：

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

迭代器

通过 next 的指向依次进行遍历。还提供了反向的迭代（从尾部到头部），通过 prev 的指向依次遍历。

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    //创建迭代器时的modCount，检测并发修改，fail-fast
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        //如果next == null， 前一个为尾节点
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

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

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        //调用unlink方法移除元素
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        //修改modCount
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        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();
    }
    //检查并发修改，fail-fast
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

小结

LinkedList 是 List 接口基于双向链表的一种实现，同时还实现了 Deque 接口，可以作为 FIFO 和 LIFO 队列使用。双向链表的实现使得插入和删除操作的代价降低，可以在常数时间内完成；然而查找操作需要遍历列表，尽管双向列表使得可以从两端进行查找，但在长度较长时仍然需要较长的时间。

在大多数情况下会选择使用 ArrayList，尽管插入和删除代价相较于 LinkedList 更高，但随机访问的特性使得在查找方面 ArrayList 比 LinkedList 具有更多的优势。关于 ArrayList 和 LinkedList 的使用选择上可以参考 StackOverflow 上的这个问答。

熬夜不易,点击请老王喝杯烈酒！！！！！！！

Java 容器源码分析之 LinkedList

概览

底层结构

双向链表操作

向头部添加元素

向尾部添加元素

从中间插入元素

移除头部节点

移除尾部节点

移除任意一个非空节点

清空链表

根据索引获取元素

反查一个元素的索引

迭代器

小结

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method