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

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

前言

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

要点

LinkedList底层是通过基于双向链表实现数据持久化存储的。
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类中，对节点的定义。

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 集合源码分析(最新版)

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

构造

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等常规操作，其中对节点的处理逻辑，是和这两段说明有对应联系的。

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

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

/*** 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;elsel.next = newNode;size++;modCount++;}

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

首先把旧的last节点引用指向l；
创建新的节点来，pre指向旧的last节点，那么不言而喻，newNode节点就是新的last节点。
如果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有两个构造方法：

/*** 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的尾部。

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;elsepred.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操作

/*** 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方法

/*** 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方法。

 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操作

public boolean add(E e) {
    linkLast(e);return true;}

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

public void add(int index, E element) {
    checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}

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

/*** 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;elsepred.next = newNode;size++;modCount++;}

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

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

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，方便回收。

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接口，所以也就有了队列的操作。比如：

offer(E e)

poll()

peek()

…

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

扫码加入我的个人微信公众号：Android开发圈，一起学习Android知识！！