集合框架 --------- LinkedList源码分析

前言

在写这篇文章之前，我也在网上看了类似的博客，但是总觉得记忆的不够深刻，毕竟别人写的终究是别人的，无法彻底理解，所以决定自己从头看一遍，做一个系统的总结，希望大家可以指出错误，共同进步！

一、LinkedList简介

既然要介绍一个类，那么首先要从这个类的继承结构入手了，我们可以通过这个类继承了那些父类，实现那些接口来大体了解这个类主要提供的功能，如下图所示：

LinkedList继承结构

由上图可以看出，LinkedList直接继承了以下接口：

• List接口：定义了一个有序、可重复的集合（也称序列）。
• Deque接口：双向队列，即队列两端的元素既能入队(offer)也能出队(poll)。
• Serializable接口：类实现此接口以启用其序列化功能。可序列化类的所有子类型本身都是可序列化的。序列化接口没有方法或字段，仅用于标识可序列化的语义。
• Cloneable接口：类实现了 Cloneable 接口，以指示Object.clone()方法可以合法地对该类实例进行按字段复制。按照惯例，实现此接口的类应该使用公共方法重写 Object.clone（它是受保护的）。

底层实现

LinkedList的内部维护了一个双向链表，通过对链表进行操作来实现增删改查等基本功能，因此，相对于ArrayList而言，LinkedList具有插入删除快而查找修改慢的特点。

下面看一下内部代码：

    //定义头结点的引用
    transient Node<E> first;
    //定义尾结点的引用
    transient Node<E> last;

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

看完上边的代码，我们再来看一下具体的数据结构图示：

数据结构图

问题一

看到这里，我不禁想问一个问题，为什么first 和 last等字段要用transient关键字修饰呢？换句话说，是出于什么样的考虑禁止这些字段序列化呢？

经过在下的一顿分析，发现LinkedList类中自己实现了一个writeObject方法，下面把代码献上：

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

通过上面的代码可以看到，在进行序列化时，序列化了所有非静态和非瞬态字段和链表中的元素，并手动序列化了size字段，也就是说，并没有序列化first和last字段，这是为什么呢？再来看一下readObject方法：

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

readObject方法从流中读取数据，并调用linkLast方法重新将数据添加到集合中，而在这个过程中会重新初始化first和last引用字段，也就是说序列化first和last字段是没有任何意义的。

问题二

乐于探（zuo）究（si）的我仅仅解决了上面的问题怎么能满足，很快我又发现了一个奇怪的字段 ---- modCount，继承于抽象类AbstractList，这货又是干什么的呢？

通过查找API，看到的解释是从结构上修改此列表的次数，所谓从结构上修改指的是更改列表的大小、或者打乱列表，从而使正在进行的迭代产生错误的结果。

例如add(E e)方法会令modCount加一，而set(E e)则不会。LinkedList内部维护了一个双向迭代器，其中有一个方法checkForComodification()，在迭代时，迭代器会记下集合的修改次数modCount并将其存到本地字段expectedModCount中，每个方法执行前都会调用checkForComodification() 方法验证本地值是否与最新值相等，若不等则抛出ConcurrentModificationException()异常，这是由于在并发情景下进行迭代，另一线程修改集合，容易使正在进行的迭代产生错误的结果，所以ArrayList,LinkedList,HashMap等等这些非线程安全类中都有modCount字段。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

二、主要方法

了解了LinkedList的主要字段和底层实现，我们再来看一下常用方法的实现，首先我们先看一下它的构造方法，LinkedList提供了一个无参构造，和一个有参构造方法，有参方法在初始化时会将给定集合中的元素添加到LinkedList中，代码如下：

    public LinkedList() {
    }
    //初始化LinkedList,并将给定集合的全部元素添加进去
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

接下来再看一下常用的增删改查方法，首先看一下add方法。

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

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

    //根据指定位置获取结点
    Node<E> node(int 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;
        }
    }

    void linkBefore(E e, Node<E> succ) {
        //得到上一个结点引用
        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++;
    }

为了方便理解，又画了个add(E e)方法执行的流程图，如下：

boolean add(E e)方法

再来个remove方法的代码,执行流程就不画了，无非是修改一下前后元素的指针指向，判断一下特殊情况（结点为首结点时）。

    //从此集合中移除首次出现的指定元素（如果存在）。
    public boolean remove(Object o) {
        //判断指定元素是否为null
        if (o == null) {
            //遍历整个集合，查找值为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;
    }

三、总结

文章的最后，我们来总结一下LinkedList的特点：

• LinkedList不是线程安全的（迭代器通过对比modCount字段来判断集合是否被其它线程修改）
• 底层维护了一个双向链表，而链表由于存储空间不连续，各个集合元素通过指针相互关联，所以增删快，查询慢，但是具体到不同情况时，性能表现也不同，比如LinkedList频繁操作集合中间的元素，性能下降的就很厉害（这是因为LinkedList在操作一个元素时，需要判断它是在集合前半段还是后半段，之后从首/尾结点遍历查询，而越靠近中间，查询损耗的时间越长）。