LinkedList 源码分析

概述

LinkedList 底层的实现是双向链表，因而它改查的效率较低，而在增删方面，由于不用进行数据的整体移动，所以在中间进行增删时具有较高的效率。

下面就从源码入手，对 LinkedList 的增删改查作进一步的了解。

主要属性

// 元素个数
transient int size = 0;

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

// 尾结点
transient Node<E> last;

构造方法

有两个构造方法，首先看默认构造方法：

public LinkedList() {
}

默认方法为空，也就是说在创建 LinkedList 时没有初始化任何属性。

另一构造方法传入一个 Collection 对象，根据该对象的元素进行初始化：

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Node 节点

看下链表节点的定义：

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

可以看出，这是一个双向链表。

基本操作

增

主要通过 add 系列方法增加元素，其中 add(E e) 和 addLast(E e) 在链表尾部添加元素，addFirst(E e) 在链表头部添加元素，add(int index, E element) 在链表的指定位置添加元素。

先看下 add(E e)：

add(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)：

add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);  // 检查索引是否超出边界

    if (index == size)
        linkLast(element);  // 插入到链表尾部
    else
        linkBefore(element, node(index));   
}

其中 node 方法 根据索引得到相应的节点：

node(int index)

Node<E> node(int index) {
    // 根据 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;
    }
}

这里利用到了双向链表的性质，根据 index 的值更接近哪头，来决定是要从前往后找还是从后往前找。

回到 add 方法，再看下 linkBefore 方法：

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    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++;
}

该方法将新节点插入到第 index 个节点前。

删

主要通过 remove 系列方法删除元素，其中 remove() 和 removeFirst() 方法在删除链表头部元素，removeLast() 删除链表尾部元素，remove(int index) 删除指定位置的元素。

先来看下 remove()：

remove()

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

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException(); // 链表为空时抛出异常
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    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;
}

该方法删除并返回第一个元素，如果集合中没有元素会抛出异常。

removeLast() 则是删除最后一个元素，原理类似，就不多说了。

接下来看下删除指定位置元素的 remove(int index)：

remove(int index)

public E remove(int index) {
    checkElementIndex(index);   
    return unlink(node(index));
}

在得到要删除的节点后，调用 unlink 方法：

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

从链表中删除该节点，并返回元素。

改

要修改某个位置的元素，可以调用 set(int index, E element)：

set(int index, E element)

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);    // 找到要修改的节点
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

找到要修改的节点后，更新元素并返回旧的值。

查

查询元素通过 get 系列方法，其中 getFirst() 得到第一个元素的值，getLast() 得到最后一个元素的值，get(int index) 得到指定位置的元素值。

源码也比较好理解：

getFirst() 和 getLast()

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

通过读取头结点和尾结点即可得到相应元素，注意如果集合为空会抛出异常。

get(int index)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

还是通过 node 方法得到相应节点，从而得到所要查找的元素。

总结

1. 底层使用双向链表，可以从两端进行插入和删除元素，所以可以作为栈、队列、双向队列使用。
2. 通过索引查找节点的时候，如果索引在前半部分，就从前往后找，如果索引在后半部分，就从后往前找，提高效率。
3. 在链表中间进行增删改查时，都需要根据索引进行查找操作。
4. 在进行增加和删除操作时，modCount 都会增加。