LinkedList 源码解析（JDK1.8）

目录

一. 前言

二. 常用方法

三. 源码解析

3.1. 属性和内部类

3.2. 构造函数

3.3. 添加元素

 3.4. 获取元素

3.5. 删除元素

3.6. 迭代器

3.6.1. 头到尾方向的迭代

3.6.2. 尾到头方向的迭代

3.6.3. add() 插入元素

3.6.4. remove() 移除元素

---

一. 前言

    LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作是一个顺序容器，又可以看作是一个队列(Queue)，同时又可以看作一个栈(Stack)。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。

特点：
1. 底层是一个双向链表结构：增删快，查询慢。
2. 包含大量操作首尾元素的方法。
3. 线程不安全。如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

LinkedList 继承了 AbstractSequentialList，而 AbstractSequentialList 又继承于 AbstractList 。详见 ArrayList 的源码，阅读后我们知道，ArrayList 同样继承了 AbstractList ， 所以LinkedList会有大部分方法和 ArrayList 相似。

简单介绍一下家族成员：
List：表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
Deque：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。
Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。
补充：
序列化是将对象转换成二进制流，持久化是将对象转换成介质数据（先转成二进制再持久化）。
序列化跟反序列化，发生在OSI的表示层。

二. 常用方法

三. 源码解析

3.1. 属性和内部类

/**
 * 集合大小
 * 当前有多少个节点
 */
transient int size = 0;
 
/**
 * 头部节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node first;
 
/**
 * 尾部节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node last;

private static class Node {
    E item; // 节点值
    Node next; // 指向的下一个节点（后继节点）
    Node prev; // 指向的前一个节点（前驱结点）
 
    // 初始化参数顺序分别是：前驱结点、本身节点值、后继节点
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

3.2. 构造函数

LinkedList 中有一个无参构造函数和一个有参构造函数。

// 创建一个空的链表对象
public LinkedList() {
}
 
// 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection c) {
    this();
    addAll(c);
}

3.3. 添加元素

LinkedList 除了实现了List接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。我们这里以List接口中相关的插入方法为例进行源码讲解，对应的是 add()、addAll() 方法。
add(E e)：用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。
add(int index, E element)：用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
addAll(int index, Collection c)：从指定位置开始，将指定集合中的所有元素插入此列表。当不是构造方法调用时，它会在其最后节点追加新的元素。
offer(E e)：内部调用 add(E e) 方法。
offerFirst(E e)：内部调用 addFirst(E e) 方法。
offerLast(E e)：内部调用 addLast(E e) 方法。
push(E e)：内部调用addFirst方法实现

// 在链表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}
 
// 在链表指定位置插入元素
public void add(int index, E element) {
    // 下标越界检查
    checkPositionIndex(index);
 
    // 判断 index 是不是链表尾部位置
    if (index == size)
        // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
        linkLast(element);
    else
        // 如果不是则调用 linkBefore 方法将其插入指定元素之前
        linkBefore(element, node(index));
}
 
// 将元素节点插入到链表尾部
void linkLast(E e) {
    // 将最后一个元素赋值（引用传递）给节点 l
    final Node l = last;
    // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
    final Node newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空
    // 如果 l 是 null，意味着这是第一次添加元素
    if (l == null)
        // 如果是第一次添加，将first赋值为新节点，此时链表只有一个元素
        first = newNode;
    else
        // 如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
        l.next = newNode;
    size++;
    modCount++;
}
 
// 在指定元素之前插入元素
void linkBefore(E e, Node succ) {
    // assert succ != null;断言 succ不为 null
    // 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息
    final Node pred = succ.prev;
    // 初始化节点，并指明前驱和后继节点
    final Node newNode = new Node<>(pred, e, succ);
    // 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空，为空表示当前链表还没有节点
    if (pred == null)
        first = newNode;
    else
        // succ 节点前驱的后继引用指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

/**
 * 从指定位置开始，将指定集合中的所有元素插入此列表。
 * 将当前位于该位置的元素（如果有）和任何后续元素向右移动（增加其索引）。
 * 新元素将按照指定集合的迭代器返回的顺序出现在列表中。
 *
 * @param 插入指定集合中第一个元素的索引
 * @param c 包含要添加到此列表的元素的集合
 * @return {@code true} 如果此列表因调用而更改，则为true
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection c) {
	// 检查index是否越界 判断是否是有效下标 此时index必须为0
	checkPositionIndex(index);
 
	Object[] a = c.toArray();
	// 数组length
	int numNew = a.length;
	if (numNew == 0)
		return false;
	// 创建两个双向链表节点 pred末游节点 succ首节点 初始值为null
	Node pred, succ;
	if (index == size) {
	// 初始首节点为null
		succ = null;
		// 存储第一个node
		pred = last;
	} else {
		succ = node(index);
		pred = succ.prev;
	}
	// 此时开始创建双向链表进行链接
	for (Object o : a) {
		// 获取值
		@SuppressWarnings("unchecked") E e = (E) o;
		// 创建一个新的节点（上一个节点，当前数值，下一个节点）
		Node newNode = new Node<>(pred, e, null);
		if (pred == null)// 第一个节点时 他的上一个节点时null
			first = newNode; // 此时最后一个节点就是它本身
		else
			// 此时将上一个节点的下游节点链接就是当前生成的
			pred.next = newNode;
		// 记录当前末游节点
		pred = newNode; 
	}
	// 此时数据链接完
	if (succ == null) {
		// 将最后一个节点赋值给last
		last = pred;
		// 如果存在首届
	} else {
		// 将最后一个的下游节点链接为第一个节点
		pred.next = succ;
		// 将第一个的上游节点链接为末游节点
		succ.prev = pred;
	}
	//size=length+1
	size += numNew;
	modCount++;
	return true;
}

public boolean offer(E e) {
    return add(e);
}
 
public boolean offerFirst(E e) {
	addFirst(e);
	return true;
}
 
public boolean offerLast(E e) {
	addLast(e);
	return true;
}
 
public void push(E e) {
    addFirst(e);
}

 3.4. 获取元素

LinkedList获取元素相关的方法一共有 3 个：
getFirst()：获取链表的第一个元素。
getLast()：获取链表的最后一个元素。
get(int index)：获取链表指定位置的元素。

// 获取链表的第一个元素
public E getFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
 
// 获取链表的最后一个元素
public E getLast() {
    final Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
 
// 获取链表指定位置的元素
public E get(int index) {
  // 下标检查
  checkElementIndex(index);
  // 返回链表中对应下标的元素
  return node(index).item;
}

添加元素时，都返回了node(int index)方法，我们分析一下该方法：

// 返回指定下标的非空节点
Node node(int index) {
    // 断言下标未越界
    // assert isElementIndex(index);
 
    // 如果index小于size的二分之一  从前开始查找（向后查找），反之向前查找
    if (index < (size >> 1)) {
        Node x = first;
        // 遍历，循环向后查找，直至 i == index
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        //遍历，循环向前查找，直至 i == index
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

get(int index) 或 remove(int index) 等方法内部都调用了该方法来获取对应的节点。
不难看出，该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是链表尾开始遍历。
1. 如果索引值小于 size 的一半，就从链表头开始遍历
2. 如果索引值大于 size 的一半，就从链表尾开始遍历。
这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。

3.5. 删除元素

LinkedList 删除元素相关的方法一共有 5 个：
removeFirst() ：删除并返回链表的第一个元素。
removeLast() ：删除并返回链表的最后一个元素。
remove(E e) ：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
remove(int index) ：删除指定索引处的元素，并返回该元素的值。
void clear() ：移除此链表中的所有元素。
E pop()：调用removeFirst()。
E poll()：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除。
E pollFirst：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除。
E pollLast：判断last元素是否为空，不为空则调用unlinkLast(E e)删除。

// 删除并返回链表的第一个元素
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
 
// 删除并返回链表的最后一个元素
public E removeLast() {
    final Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
 
// 删除链表中首次出现的指定元素，如果不存在该元素则返回 false
public boolean remove(Object o) {
    // 如果指定元素为 null，遍历链表找到第一个为 null 的元素进行删除
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 如果不为 null ，遍历链表找到要删除的节点
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
 
// 删除链表指定位置的元素
public E remove(int index) {
    // 下标越界检查，如果越界就抛异常
    checkElementIndex(index);
    return unlink(node(index));
}

我们可以看到，均调用了 unlink(Node x)，对该方法解析：

E unlink(Node x) {
    // 断言 x 不为 null
    // assert x != null;
 
    // 获取当前节点（也就是待删除节点）的元素
    final E element = x.item;
    // 获取当前节点的下一个节点
    final Node next = x.next;
    // 获取当前节点的前一个节点
    final Node prev = x.prev;
 
    // 如果前一个节点为空，则说明当前节点是头节点
    if (prev == null) {
        // 直接让链表头指向当前节点的下一个节点
        first = next;
    } else { // 如果前一个节点不为空
        // 将前一个节点的 next 指针指向当前节点的下一个节点
        prev.next = next;
        // 将当前节点的 prev 指针置为 null，方便 GC 回收
        x.prev = null;
    }
 
    // 如果下一个节点为空，则说明当前节点是尾节点
    if (next == null) {
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else { // 如果下一个节点不为空
        // 将下一个节点的 prev 指针指向当前节点的前一个节点
        next.prev = prev;
        // 将当前节点的 next 指针置为 null，方便 GC 回收
        x.next = null;
    }
 
    // 将当前节点元素置为 null，方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink() 方法的逻辑如下：
1. 首先获取待删除节点 x 的前驱和后继节点；
2. 判断待删除节点是否为头节点或尾节点：
    1>. 如果 x 是头节点，则将 first 指向 x 的后继节点 next。
    2>. 如果 x 是尾节点，则将 last 指向 x 的前驱节点 prev。
    3>. 如果 x 既不是头节点也不是尾节点，执行下一步操作。
3. 将待删除节点 x 的前驱的后继指向待删除节点的后继 next，断开 x 和 x.prev 之间的链接；
4. 将待删除节点 x 的后继的前驱指向待删除节点的前驱 prev，断开 x 和 x.next 之间的链接；
5. 将待删除节点 x 的元素置空，修改链表长度。

public E pop() {
    return removeFirst();
}
 
public E poll() {
	// 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
	final Node f = first;
	return (f == null) ? null : unlinkFirst(f);
}
 
public E pollFirst() {
	// 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
	final Node f = first;
	return (f == null) ? null : unlinkFirst(f);
}
 
public E pollLast() {
	// 判断last元素是否为空，不为空则调用unlinkLast(E e)删除
	final Node l = last;
	return (l == null) ? null : unlinkLast(l);
}

3.6. 迭代器

推荐使用 for-each 循环来遍历 LinkedList 中的元素，for-each 循环最终会转换成迭代器形式。

LinkedList 遍历的核心就是它的迭代器的实现。

// 双向迭代器
private class ListItr implements ListIterator {
    // 表示上一次调用 next() 或 previous() 方法时经过的节点；
    private Node lastReturned;
    // 表示下一个要遍历的节点；
    private Node next;
    // 表示下一个要遍历的节点的下标，也就是当前节点的后继节点的下标；
    private int nextIndex;
    // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
    private int expectedModCount = modCount;
    …………
}

下面我们对迭代器 ListItr 中的核心方法进行详细介绍。

3.6.1. 头到尾方向的迭代

// 判断还有没有下一个节点
public boolean hasNext() {
    // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
    return nextIndex < size;
}
// 获取下一个节点
public E next() {
    // 检查在迭代过程中链表是否被修改过
    checkForComodification();
    // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 将 lastReturned 指向当前节点
    lastReturned = next;
    // 将 next 指向下一个节点
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

3.6.2. 尾到头方向的迭代

// 判断是否还有前一个节点
public boolean hasPrevious() {
    return nextIndex > 0;
}
 
// 获取前一个节点
public E previous() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果没有前一个节点，则抛出异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 将 lastReturned 和 next 指针指向上一个节点
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

3.6.3. add() 插入元素

LinkedList list = new LinkedList<>();
list.add("apple");
list.add(null);
list.add("banana");
 
//  Collection 接口的 removeIf 方法底层依然是基于迭代器
list.removeIf(Objects::isNull);
 
for (String fruit : list) {
    System.out.println(fruit);
}

3.6.4. remove() 移除元素

// 从列表中删除上次被返回的元素
public void remove() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果上次返回的节点为空，则抛出异常
    if (lastReturned == null)
        throw new IllegalStateException();
 
    // 获取当前节点的下一个节点
    Node lastNext = lastReturned.next;
    // 从链表中删除上次返回的节点
    unlink(lastReturned);
    // 修改指针
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    // 将上次返回的节点引用置为 null，方便 GC 回收
    lastReturned = null;
    expectedModCount++;
}