LinkedList 源码分析

上篇文章分析了 ArrayList 的源码，面试过程中经常会被面试官来问 LinkedList 和 ArrayList 的区别，这篇文章从源码的角度来看下 LinkedList 以后，再和上篇文章做个对比，相信你会有一个自己的判断的。

LinkedList 简介

老规矩，先来看下官方 Api 对 LinkedList 的介绍：

从图中可以看出，LinkedList 和 ArrayList 都是直接或者间接继承于 AbstractList 的，但是和 ArrayList 不同的是 LinkedList 是直接继承于 AbstractSequentialList 的。

先来看下这个 AbstractSequentialList ：

Api 中也描述了 AbstractSequentialList 提供了一个基本的List接口实现,为实现序列访问的数据结构存储提供了所需要的最小化接口实现，而对于支持随机访问数据的List比如数组，应该优先使用 AbstractList。

和 AbstractList 实现随机访问相反，AbstractSequentialList 采用的迭代器实现的 get、set、add 和 remove 等党阀

为了实现这个列表。仅仅需要拓展这个类，并且提供ListIterator和size方法。 对于不可修改的List，编程人员只需要实现Iterator的hasNext、next和hasPrevious、previous和index方法 对于可修改的List还需要额外实现Iterator的的set的方法 对于大小可变的List，还需要额外的实现Iterator的remove和add方法

LinkedList 实现的所有接口有：

• 实现了 Serializable 是序列化接口，因此它支持序列化，能够通过序列化传输。
• 实现了 Cloneable 接口，能被克隆。
• 实现了Iterable 接口，可以被迭代器遍历
• 实现了 Collection ，拥有集合操作的方法
• 实现 Deque/Queue 可以当作队列/双端队列使用
• 实现了 List 接口，拥有增删改查等方法

先看下LinkedList 的特点，对 LinkedList 有一个大体上的认识：

1. LinkedList 底层数据结构是双向链表，但是头节点不存放数据，只有后置节点的引用；
2. 集合中的元素允许为 null，可以看到源码中在查找和删除时，都划分为该元素为null和不为null两种情况来处理。
3. 允许内部元素重复
4. 不存在扩容问题，所以是没有扩容的方法
5. 元素在内部是有序存放的，依次在链表上添加节点
6. 实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用
7. 由于是链表实现，并且没有实现RandomAccess ，虽然在查找的时候，会先判断是在前半部分或者后半部分，然后依次从前或者从后查找，但是查找效率还是很低，不过增删效率高，但是查找和修改大部分情况下不如 ArrayList。
8. 线程不安全，可以用个 Collections.SynchronizedList(new LinkedList()) 返回一个线程安全的 LinkedList

下面从源码的角度进行分析：

LinkedList 源码分析

一些属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
		// 大小
    transient int size = 0;

    // 头节点
    transient Node<E> first;

    // 尾节点
    transient Node<E> last;
    // 序列化ID
    private static final long serialVersionUID = 876323262645176354L;
}
复制代码

前面讲了，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;
    }
}
复制代码

很明显的双向链表的结构。

构造方法

// 空的构造方法，什么都没做，只是生成了对象
public LinkedList() {
}
// 传入了集合 c，并将其插入到链表中。
public LinkedList(Collection<? extends E> c) {
    this();
  	// 添加方法稍后分析
    addAll(c);
}
复制代码

构造方法也很简单，没有什么特殊的操作。

前面讲了，LinkedList 可以当做一个 List 使用，也可以当做队列使用，依次进行分析：

作为列表使用的一些方法：

添加(add)的一些方法

先看下 add 方法：

// 这个方法实现的效果和 addLast(E e) 是一样的
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 顾名思义，链接到最后。也就是把添加的元素添加到尾节点。
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++;
}
复制代码

add(int index, E element)

在指定位置添加

public void add(int index, E element) {
  	//检查插入位置的合法性，即是否比 0 大，比当前的 size 小
    checkPositionIndex(index);
  	// 如果是等于当前大小，就是相当于在尾部再插入一个节点
  	// 否则就是插入到 index 所在位置的节点的前面
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

// 返回指定索引处的一个非空节点 
// 这里是 LinkedList 做的一个优化，先判断索引是在前半部分和后半部分
// 如果前半部分，从头节点开始找，正序找
// 如果后半部分，从尾节点开始找，倒序找
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;
    }
}

// 插入到指定节点的前面
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
  	// 取出查找到指定位置的节点
    final Node<E> pred = succ.prev;
  	// 构建新节点，前置节点找到节点的原前置节点，e 是元素值，后置节点是根据位置找到的 succ
    final Node<E> newNode = new Node<>(pred, e, succ);
  	// 原位置的前置节点设置为要插入的节点。
    succ.prev = newNode;
  	// 如果原位置的前置节点为空，即原位置 succ 是头节点，即 add(0 ,E )然后把新建节点赋值为头节点。
    if (pred == null)
        first = newNode;
    else
    // 不为空，原位置的前置节点的后置节点设置为新节点。
        pred.next = newNode;
    size++;
    modCount++;
}
复制代码

总的来说就是： 先检查是否在可插入的范围内，不在抛异常，如果 index 和当前 size 相等，直接插入到尾节点，如果小于当前 size，那么就插入到 index 节点的前面。

看下 addAll

// 没有传入位置，直接加到最后
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 加入到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
  	// 检查 index 合法性
    checkPositionIndex(index);
		// 传入的 Collection 转换成数组
    Object[] a = c.toArray();
    int numNew = a.length;
		// 空数组，直接返回插入失败
    if (numNew == 0)
        return false;
		// pred 是 succ 的前置节点 ，succ指向当前需要插入节点的位置的节点
    Node<E> pred, succ;
  	// index 等于 size，尾插
  	// 不等于，找到需要插入位置的节点，以及其前置节点，pred 可能为空
    if (index == size) {
        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 后置节点设置为新节点
            pred.next = newNode;
      	// 每次设置完，pred 表示刚插入的节点，依次往后插入
        pred = newNode;
    }

  	// 如果是从 size 位置开始添加，最后添加的节点成了尾节点
    if (succ == null) {
        last = pred;
    } else {
    // 如果不是从 size 开始添加，数组中最后一个元素的后置节点指向为 原 index 位置节点
    //  原 index 位置节点的前置节点置为数组中最后一个元素构建的节点。
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}
复制代码

addFirst 、addLast

// 添加元素到链表头。
public void addFirst(E e) {
    linkFirst(e);
}
// 添加元素到链表尾
public void addLast(E e) {
    linkLast(e);
}
复制代码

linkLast 前面在讲 add 的时候已经分析过了，再来看下 linkFirst

private void linkFirst(E e) {
  	// 保存头节点
    final Node<E> f = first;
  	// 创建新节点
    final Node<E> newNode = new Node<>(null, e, f);
  	// 头节点设置为新节点
    first = newNode;
  	// 如果头节点为空，表名链表为里面没数据，尾节点也需要设置为新节点
    if (f == null)
        last = newNode;
    else
    // 头节点不为空，设置原头节点的前置节点为 新节点。
        f.prev = newNode;
    size++;
    modCount++;
}
复制代码

删除(remove)的一些方法

//移除指定位置的元素
public E remove(int index) {
    checkElementIndex(index);
  	// 先拿到指定位置的节点
    return unlink(node(index));
}

// 移除指定元素
// 这里和 ArrayList 里面移除比较相似，分为 null 和 不为 null 两种情况。先从头节点遍历找到要移除的元素，
// 然后执行移除第一个元素对应的节点的操作。。
// 是移除第一个相等的元素！
// 是移除第一个相等的元素！
// 是移除第一个相等的元素！
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;
  	// 前置节点为 null ，表明要移除头节点，把下一个节点设置为头节点
  	// 前置节点不为 null ，x 的前置节点的后置节点指向 x 的后置节点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
  	// 后置节点为 null ，表明要移除尾节点，把上一个节点设置为尾节点
  	// 后置节点不为 null ，x 的后置节点的前置节点指向 x 的前置节点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
  	// 释放引用的元素，gc 可回收
    x.item = null;
    size--;
    modCount++;
    return element;
}
复制代码

这两个删除的方法基本都是先找到要删除元素对应的节点，然后再去执行 unlink 方法去对节点的 前置节点、后置节点进行重新指向。然后把引用的元素 置为 null ，便于 gc 回收移除的元素，最后返回移除元素。

此外还有移除第一个和最后一个

//  移除第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
//  移除最后一个元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 移除第一个元素，调整指针指向，并把头部部元素置空，便于 gc 回收
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
// 移除最后一个元素，调整指针指向，并把尾部元素置空，便于 gc 回收
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;
}
复制代码

修改(set)的一些方法

// 修改一个元素
public E set(int index, E element) {
  	// 检查index 是否在合法位置
    checkElementIndex(index);
  	// 通过 node 函数找到要修改位置对应的节点
    Node<E> x = node(index);
  	// 然后直接修改元素里面的 item 属性，完成修改
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
复制代码

查找(get)的一些方法

// 查找指定位置的元素
public E get(int index) {
	  // 检查index 是否在合法位置
    checkElementIndex(index);
  	// 通过 node 函数找到要修改位置对应的节点，并返回其 item 属性，即为元素值。
    return node(index).item;
}
// 查找第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
// 查找最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
复制代码

上面的都比较简单。

清除(clear) 的一些方法

// 移除列表中的所有元素
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
  
  	// 遍历所有的不为 null 的节点，把所有数据全部置为 null，便于gc 回收
    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++;
}
复制代码

作为队列使用的一些方法

队列是什么？

队列是一种比较特殊的线性结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列中最先插入的元素也将最先被删除，对应的最后插入的元素将最后被删除。因此队列又称为“先进先出”（FIFO—first in first out）的线性表，与栈(FILO-first in last out)刚好相反。

队列的抽象是 Queue，而 LinkedList 是实现了 Deque 接口的，Deque 又继承了 Queue，所以LinkedList 是可以当做队列来使用的。

先看下 Queue 接口：

public interface Queue<E> extends Collection<E> {
  	// 增加一个元素到队列尾部，如果队列有大小限制，并且队列已满，会抛出异常 IllegalArgumentException
    boolean add(E e);

  	// 增加一个元素到队列尾部，和 add 不同的是：如果队列有大小限制，并且队列已满，则返回 false，不抛出异常
    boolean offer(E e);
  	
  	// 检索到队列头部元素，并且将其移出队列。和 poll 方法不同的是如果队列是空的，那么抛出 NoSuchElementException 异常
    E remove();

  	// 检索到队列头部元素，并且将其移出队列。如果队列是空的，那么返回 null；
    E poll();
  
  	// 检索队列头部的元素，并不会移除，和 peek 方法不同的是：如果队列是空的，那么抛出 NoSuchElementException 异常；
    E element();

  	// 检索队列头部的元素，并不会移除，如果队列是空的，那么返回 null；
    E peek();
}
复制代码

LinkedList 里面的实现

add 、offer

add 前面已经分析过了，这里来看下 offer：

public boolean offer(E e) {
    return add(e);
}
复制代码

前面队列中的定义已经写了，在 add 会在队列满的时候抛出异常，但是这个发现 offer 方法也调用的 add 方法，所以只是对 add 的一种包装，实际使用效果是一样的。这是为什么呢？

这是因为前面注释里面讲了，add 添加的时候抛出异常只会在队列大小有限制的情况，在LinkedList 中并没有设置大小的地方，所以也就不存在超过队列大小的限制了。

remove 、poll

public E remove() {
    return removeFirst();
}

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
复制代码

同理，这两个也不会抛出异常。

remove 会直接调用 removeFirst 从头部移除元素，并且在 removeFirst 方法移除的过程中可能会抛出异常。

poll 则先把头部元素取出来，进行判空。

如果为空，则返回 null，什么都不做，不会抛出异常，直接返回 null；

如果不为空，那么就执行 unlinkFirst(f) ，这个 unlinkFirst 前面已经讲了，把头部元素移除。

element、peek();

public E element() {
    return getFirst();
}

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
复制代码

和上面注释的一样，两个都是取头部元素，element 会抛出异常，peek 只是取头部元素，不会抛出异常。

作为双向队列使用的一些方法

双向队列是队列 (Queue) 的一个子接口 Deque，双向队列两端的元素都可以入队列和出队列。可以实现先进先出或者先进后出的数据结构。

如果把 Deque 限制为只能从一端入队和出队，那么就可以实现 栈 的结构数据结构，遵循 先进后出 的规则。

如果不对 Deque 进行限制，用作双向队列，那么就是先进新出。

主要方法如下：

public interface Deque<E> extends Queue<E> {
    //  将指定元素插入此双端队列的开头（如果可以直接这样做而不违反容量限制）
    void addFirst(E e);

    //将指定元素插入此双端队列的末尾（如果可以直接这样做而不违反容量限制）。
    void addLast(E e);

    //在不违反容量限制的情况下，将指定的元素插入此双端队列的开头。
    boolean offerFirst(E e);

    // 在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾。
    boolean offerLast(E e);

    // 获取并移除此双端队列第一个元素。
    E removeFirst();

    // 获取并移除此双端队列的最后一个元素。
    E removeLast();

    //获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    E pollFirst();

    //获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    E pollLast();

    // 获取，但不移除此双端队列的第一个元素。
    E getFirst();

    // 获取，但不移除此双端队列的最后一个元素。
    E getLast();

    // 获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    E peekFirst();

    //获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    E peekLast();

    //从此双端队列移除第一次出现的指定元素。
    boolean removeFirstOccurrence(Object o);

    // 从此双端队列移除最后一次出现的指定元素。
    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    // 将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；
  	// 如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
    boolean add(E e);

    // 将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；
  	// 如果成功，则返回 true，如果当前没有可用的空间，则返回 false。
    boolean offer(E e);

    //获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。
    E remove();

    //获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
    E poll();

    //获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。
    E element();

    //获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
    E peek();


    // *** Stack methods ***

    // 将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部），如果可以直接这样做而不违反容量限制的话；
  	// 如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
    void push(E e);

    // 从此双端队列所表示的堆栈中弹出一个元素
    E pop();


    // *** Collection methods ***

    //  从此双端队列中移除第一次出现的指定元素
    boolean remove(Object o);

    // 是否包含一个元素
    boolean contains(Object o);

    // 队列大小
    int size();

    // 返回此双端队列的迭代器
    Iterator<E> iterator();

    // 返回一个迭代器，该迭代器具有此双端队列的相反顺序
    Iterator<E> descendingIterator();

}
复制代码

具体的就不在分析，在 LinkedList 无非是比队列多一些操作而已，有兴趣的可以去看下关于双端队列相关的部分源码。

总结

1. LinkedList 底层数据结构是双向链表，但是头节点不存放数据，只有后置节点的引用；
2. 集合中的元素允许为 null，可以看到源码中在查找和删除时，都划分为该元素为null和不为null两种情况来处理。
3. 允许内部元素重复
4. 不存在扩容问题，所以是没有扩容的方法
5. 元素在内部是有序存放的，依次在链表上添加节点
6. 实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用
7. 由于是链表实现，并且没有实现RandomAccess ，虽然在查找的时候，会先判断是在前半部分或者后半部分，然后依次从前或者从后查找，但是查找效率还是很低，不过增删效率高，但是查找和修改大部分情况下不如 ArrayList。
8. 线程不安全，可以用个 Collections.SynchronizedList(new LinkedList()) 返回一个线程安全的 LinkedList

大多数情况下使用 ArrayList 即可，其他的还是根据具体的业务场景根据两者的不同特性进行不同的选择。

关于 ArrayList 和 LinkedList 的性能对比，可以参考这篇文章