LinkedList源码分析（基于jdk1.8）

桃扇骨 2022-05-17 00:35 247阅读 0赞

LinkedList源码解析

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

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。  
LinkedList 实现 List 接口，能对它进行队列操作。  
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。  
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。  
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。  
LinkedList 是非同步的。

为什么要继承自AbstractSequentialList ?

AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些骨干性函数。降低了List接口的复杂度。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。

此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

LinkedList内部是一个双端链表的结构，结构如下图：

![26a53ba685864d5e1363f98c54442a3e.jpg][]

从上图可以看出，LinkedList内部是一个双端链表结构，有两个变量，first指向链表头部，last指向链表尾部。   
LinkedtList内部的成员变量如下：

transient int size = 0;
    /**
     * 指向头部信息
     */
    transient Node<E> first;
    /**
     * 指向尾部信息
     */
    transient Node<E> last;

其中有关[transient][]关键字，请参考[Java中的关键字 transient][transient]

其中size表示当前链表中的数据个数。下面是Node节点的定义，Node类LinkedList的静态内部类。

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

从Node的定义可以看出链表是一个双端链表的结构。

构造方法：

/**
     * 初始化空的对象
     */
    public LinkedList() {
    }
    /**
     * 通过集合构造linkedList
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

空的构造函数没有什么可说的，接下来看看addAll（）方法

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

public boolean addAll(int index, Collection<? extends E> c) {
        //检查索引是否越界
        checkPositionIndex(index);
        //将集合转换成数组
        Object[] a = c.toArray();
        //获取需要赋值的数组长度
        int numNew = a.length;
        //如果长度为空，则表示不用添加，并且返回false
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
            //如果索引和size相同，表示直接将集合添加的链表尾部，并将pred指向尾部
            succ = null;
            pred = last;
        } else {
            //不相同，则从该索引添加集合
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //遍历数组，构造node，并添加到链表尾部
            Node<E> newNode = new Node<>(pred, e, null);
            //如果pred==null表示是空链表，直接赋值
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        //如果succ=null，表示将数组添加到链表尾部，此时last应该指向数组最后一个节点，即pred
        if (succ == null) {
            last = pred;
        } else {
            //如果succ!=null表示从中间插入数组，则将新插入的数组，的尾部指向succ，succ的prev指向pred
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

接下来看下add方法

public boolean addAll(Collection<? extends E> c) {
        /**
         * addAll方法上面已经介绍过了，addAll此时是直接在原有链表集合后面添加该集合
         */
        return addAll(size, c);
    }
    /**
     * 从某个位置添加一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        //检查索引是否越界
        checkPositionIndex(index);
        //判断位置是否是尾部，如果是尾部，则直接在尾部添加，如果不检查，直接去该位置寻找插入，会影响性能
        if (index == size)
            linkLast(element);
        else
            //不是尾部，则会调用node(index)添加
            linkBefore(element, node(index));
    }
    public void addFirst(E e) {
        //在首部添加该元素
        linkFirst(e);
    }
    public void addLast(E e) {
        //尾部添加
        linkLast(e);
    }

从上面可以看出，add方法，如果指定了添加位置，则必须去检查index是否越界。

并且如果指定位置，也要需要判断index是否在尾部，如果是尾部，则调用linkLast方法，否则会影响性能。为什么不判断index=0则添加到首部呢？我们看下核心的添加方法就明白了

/**
     * 在首部添加元素
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        //初始化一个元素，并将该元素指向之前的first
        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;
        //跟linkFirst相同，将pre指向之前的尾部，初始化node
        final Node<E> newNode = new Node<>(l, e, null);
        //更改尾部指向
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

从上面源码不难看出，linkFirst和linkLast消耗会很少，只是初始化一个node，并更改指向而已，因此，如果在首部或者尾部添加元素，linkedList就会很快。

但是如果指定index去添加元素，从上面源码看出都会调用node(index)方法，接下来看下该方法的源码：

/**
     * 找到index位置的元素
     */
    Node<E> node(int index) {
        //如果index小于中间位置，则从链表头部找起
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                //通过next去遍历
                x = x.next;
            return x;
        } else {
            //否则，则从链表尾部找起
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

从上面源码不难看出，node(index)就是找出该位置的元素，但是由于链表的实现，寻找指定位置的元素会变得很麻烦，必须根据node的指引一点点去遍历。

上面刚刚提出的为什么不判断index=0则添加到首部呢？不难看出，如果index=0，那么就算调用node（index）方法也是直接就会找到first，因此没必要去检查index=0的情况。

由上面的源码不难看出，其实链表如果在指定位置插入一个元素，和ArrayList中插入一个元素，哪个性能更好呢？

如果ArrayList不触发扩容机制的话，且链表的位置刚好比较靠近中间的中间的话，ArrayList的插入性能反而会比链表插入更快

如果想查看ArrayList源码解析，请查看：[http://www.lingshu.xin/article/366c5038.html][http_www.lingshu.xin_article_366c5038.html]

未完待续

![70][]

[26a53ba685864d5e1363f98c54442a3e.jpg]: http://image.ailq.net/lq/cloud/img/26a53ba685864d5e1363f98c54442a3e.jpg
[transient]: http://www.lingshu.xin/article/32456e6f.html
[http_www.lingshu.xin_article_366c5038.html]: http://www.lingshu.xin/article/366c5038.html
[70]: /images/20220517/9a78e590433a4586868b1b087d4d7e6b.png