容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

前言

上篇文章 容器类源码解析系列(一) ArrayList 源码分析——基于最新Android9.0源码 对ArrayList集合的源码进行了详细的分析,通过源码分析,使得我们对ArrayList的理解更加深刻,使用起来会更得心应手。本文将要讲解的是LinkedList的底层原理。建议在阅读本文之前,先回顾一下上篇介绍ArrayList的文章,毕竟它们都是开发中的常用的集合类。

要点

  • LinkedList底层是通过基于双向链表实现数据持久化存储的。

arch

  • LinkedList可以存储Null值,可以存储重复的值。

  • LinkedList是非线程安全的,在多线程并发环境下,需要加锁来做同步处理,也可通过Collections.synchronizedList(new LinkedList(…))方法,获得一个加过锁的List。

  • LinkedList也是具有fail-fast特性的集合类。关于fail-fast机制,容器类源码解析系列(一) ArrayList 源码分析——基于最新Android9.0源码 这篇文章有详细讲解。

  • current节点的prev等于null,则该节点是first节点;current节点的next等于null,则该节点是last节点。

Node 节点

分析LinkedList源码,Node这个类,我们必要要知道。Node(节点)是在链表结构中的基本组成单位。我们看一下LinkedList类中,对节点的定义。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

根据代码再结合图片,很容易知道Node的含义,element表示存储的Value值,pre、next分别指向当前节点的上一个节点和下一个节点。

构造

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

先看上面的成员变量,他们都被transient关键字修饰,表示不会被序列化。size是容器大小;first,last分别表示开始的节点和最后一个节点。我们发现first和last上面还有两段说明。这两段说明,是很有必要注意一下的,因为后面的一些add,remove等常规操作,其中对节点的处理逻辑,是和这两段说明有对应联系的。

1
Invariant: (first == null && last == null) || (first.prev == null && first.item != null)

这段说明是形容first节点的,如果first是null,那么last节点也应该是null;first.prev等于null,first.item不能等于null。这两个条件至少有一个成立,这是对first节点的定理约束。第一个判断还比较好理解,第二个判断可能不好理解,我们来通过一些例子感受一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
     * Links e as last element.
     */
    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++;
    }

上面的代码是LinkedList源码中把一个value值插入链表尾部的方法,实现逻辑如下:

  1. 首先把旧的last节点引用指向l;
  2. 创建新的节点来,pre指向旧的last节点,那么不言而喻,newNode节点就是新的last节点。
  3. 如果l节点,也就是pre指向的节点等于null,这个newNode同是也被指向first节点,成为first节点。

后面的就不分析了,此时我们看,newNode节点(即first节点),它的pre(l)是等于null的,newNode节点的next也是null,如果此刻e也等于null,则第二个条件(first.prev == null && first.item != null) 没有满足,但是不要忘了newNode既是first节点也是last节点,满足了第一个条件(first == null && last == null) 所以,定理还是满足的。

第二个不变的定理是指向last节点的Invariant: (first == null && last == null) || (last.next == null && last.item != null) 就不在细说了,这两个不变的定理,在LinkedList的源码实现逻辑中,会表现出现。


LinkedList不像ArrayList默认有10个capacity,linkedlist的size默认是0。所以LinkedList每次add数据都需要创建Node节点。

LinkedList有两个构造方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

我们主要看第二个构造函数。传入有个list集合,把它放在当前LinkedList的尾部。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);//(注释1)

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) { //(注释2)
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

主要调用这个方法,表示吧指定集合添加到index对应的节点之前。通过构造函数调用这个方法的话,index是size值的大小,表示,把指定集合添加到当前链表的尾部。

(注释1)会先对index做一个数组越界的异常检测。

(注释2)如果size = index,表示吧传进来的指定集合add到链表尾部。不相等的话,就先通过node(index)拿到对应的节点,然后把pred = succ.prev;表示,之后添加的节点是插在index对应节点之前的地方。

接下来就比较简单了,就是循环创建节点,然后是修改next,prev指向问题。

常规操作

get,set操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

先看get方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

在做一个判断来确定区间后,接着用for循环,遍历查找出目标节点。而ArrayList是通过数组直接拿到的。我们看set方法。

1
2
3
4
5
6
7
 public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

和get方法一样,也是要通过node(index)方法,遍历获取目标节点,然后替换目标节点的element的值。所以相较于ArrayList,对于get,set操作,还是ArrayList更方便,效率些。

Add,Remove操作

1
2
3
4
public boolean add(E e) {
        linkLast(e);
        return true;
    }

添加元素,默认是添加到尾部,linkLast()这个方法前文有介绍,这里就不在重复了,内部逻辑就是new一个Node节点,然后赋给last,再把旧的last指向新的节点的prev。

1
2
3
4
5
6
7
8
public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

我们着重看linkBefore方法,该方法的第二个参数是调用了之前说的node(index)方法,找到对应index的目标节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/**
     * Inserts element e before non-null Node 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;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

总的来说就是new一个节点,然后设置其的prev,next,以及它前一个节点的确定。add操作系列的方法还有addAll、addFirst、等等。addAll方法上面已经介绍过了。它们的逻辑都大差不差,有index要求的,就先遍历确定index对应的节点,然后创建Node节点,再做pre,next这些引用的调整,没有index要求的,就创建节点,默认放在最前面,或者最后面,最后重新设置一下first,last的引用。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
        if (o == 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;
    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

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

先遍历找到目标节点,然后重新指定目标节点的prev,next指向关系,把目标节点的prev,element,next值置为null,方便回收。

1
2
3
4
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

这个方法,是根据index,先找到目标节点,然后在对目标节点进行处理。通过分析ArrayList和LinkedList的插入,删除源码实现,可以得出如下结论。

总结

有些说法认为LinkedList做插入和删除更快,这种说法其实不是绝对的:

(1)LinkedList做插入、删除的时候,慢在寻址,快在只需要改变前后Node节点的prev,next的引用地址。

(2)ArrayList做插入、删除的时候,慢在数组元素的批量copy,快在寻址。

顺序插入(add)的话,建议选择LinkedList,因为ArrayList有扩容和批量copy的消耗。

随机插入,如果插入点在集合的前面部分靠近头,后面部分靠近尾端的部分,LinkedList更合适。

对于ArrayList,插入的越靠后,即index越大,size-index越小,copy的数量就越小。会更快些。(但是存在扩容的损耗)

删除操作,如果是remove(Object o),删除节点的位置越靠后,效率越差,如果是remove(int index)操作,则删除节点的位置在两端的效率高,中部的效率差。

ArrayList的删除操作效率表现和插入类似,越往后,copy的数量越少,越快些。

上面说的是在大量数据下,数据量少的情况下,其实差别不大。随便用!(ps:ArrayList用的多点)。

队列操作

因为LinkedList实现了Deque接口,所以也就有了队列的操作。比如:

1
offer(E e)
1
poll()
1
peek()

等等,比较简单,就不说了,知道有这回事。