从源码上分析 LinkedList（附图）

前言

上一篇我们介绍了 ArrayList，这次，我们再看看一下它的兄弟：LinkedList 。

LinkedList 同样也实现了 List 接口，底层原理是双向链表，那么它又是如何实现的呢？继续来看吧。

源码分析

成员变量

LinkedList 只有三个成员变量：

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

size 属性不用说，肯定是表示链表的逻辑长度，first 应该是链表的第一个元素，last 表示最后一个元素。

构造方法

先来看无参构造：

1 2	public LinkedList() { }

无参构造没有任何逻辑，那么再来看看其他的构造方法：

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

这里牵扯到要给 addAll 方法，一会在常用方法里我们会讲到，这里先放一放。

这次我们带上内存图来分析，会更直观一些，首先用无参构造来创建一个对象：

1	List<Student> list = new LinkedList<>();

注：为了节省篇幅，本图省略了一些细节上东西，如常量池，方法区等内容。

常用方法

add

首先是 add 方法：

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

void linkLast(E e) {
    final Node<E> l = last;  // last 节点表示添加前最后一个节点
    final Node<E> newNode = new Node<>(l, e, null);  // 要添加的节点的上一个节点应该是 last 节点。
    last = newNode;          // 添加了节点后，添加的新节点应该为 last 节点。
    if (l == null)           // 如果当前元素没有上一个元素，则表示为第一次添加，
        first = newNode;     // 那么当前节点应该也算是 first 节点。
    else
        l.next = newNode;
    size++;                  // 逻辑长度 + 1
    modCount++;              // 修改次数 + 1
}

这里提到了 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;
    }
}

原来 Node 类是 LinkedList 的静态内部类，表示链表的一个节点。

那么当我们执行这段代码后，会发送什么呢？

1	list.add(new Student("张三", 20));

那我们再添加一个元素呢?

1	list.add(new Student("李四", 21));

可能看起来有写复杂，其实也不难理解，耐下心对照源码好好看一下，应该就能理解这张图的意思了。

我们再添加两个元素看看效果。

1 2	list.add(new Student("王五", 22)); list.add(new Student("赵六", 23));

remove

添加了这么多，我们删除一个试试，先来看看源码：

// 根据索引删除
public E remove(int index) {
    checkElementIndex(index);   // 检查要删除的元素索引是否有效，即 0 <= index < size
    return unlink(node(index)); // node(index) 方法找到第 index 个元素
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

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;             // 删除头节点后，更换 first 指向
    } else {                      // 如果不是头节点
        prev.next = next;         // 将前驱节点的 next 指向要删除节点的后继节点
        x.prev = null;            // 将要删除的节点不再指向任何节点
    }

    if (next == null) {           // 如果当前节点为最后一个节点
        last = prev;              // 将 last 指向倒数第二个
    } else {                      // 如果不是最后一个节点
        next.prev = prev;         // 将后继节点的 prev 指向要删除元素的前驱节点
        x.next = null;            // 将要删除的节点不再指向任何节点
    }

    x.item = null;                // 将要删除的元素的数据清空
    size--;                       // 逻辑长度 - 1
    modCount++;                   // 修改次数 + 1
    return element;               
}

可能这里的这 10 和 17 行不太容易理解：

1 2	prev.next = next; // 将前驱节点的 next 指向要删除节点的后继节点 next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点

举个简单的例子:
张三 <==> 李四 <==> 王五

那么要删除李四的话，应该要将张三的 “下一个” 指向王五吧，也就是 prev.next = next;。同样，应为是双向链表，所以也应该让王五的 “上一个” 指向张三，即 next.prev = prev;。

这里讲解的是根据索引删除，还有根据元素删除，其实原理是一样的，主要是 unlink 这个方法，先根据传入的参数，找到要删除的元素，然后进行 unlink 方法的逻辑即可，这里就不再展开，如果你看懂了根据索引删除，相信你也能理解根据元素删除。

但是需要注意的是：如果删除的是引用数据类型的话，需要重写 equals 方法，不然可能会无法进行删除操作哦。

其实仔细想想也能理解，既然需要 找到要删除的元素，那么如何判断传入的参数和要删除的是同一个呢？只有 equals 方法了，而默认从 Object 继承的 equals 方法可不一定能满足我们的需求，因为它只比较地址值，所以我们需要重写 equals 方法。

get

 public E get(int index) {
    checkElementIndex(index);    // 检查要获取的元素索引是否有效，即 0 <= index < size
    return node(index).item;     // 根据索引来找到这个元素，返回它的 item 值
}

 Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {   // 如果要删除的元素在前半段, 则从 first 开始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                     // 如果要删除的元素在后半段, 则从 last 开始查找
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这里用了一个很巧妙的小算法，既然我们知道链表的长度，那么当要删除的元素 索引 < 长度 / 2，就从第一个开始找，反之从最后一个开始找，长度 / 2 可以改写为位运算即：size >> 1，效率更高一些。

先讲这么多，如果你看懂了这些，相信 LinkedList 的其他方法，你也能够轻松的理解。

总结

根据上方的源码分析，我们可以总结出 LinkedList 的一些特性：

LinkedList 底层数据结构是双向链表。
不能对元素进行随机访问，虽然提供了 get 方法，但这个方法是通过遍历来实现的。
删除、添加元素的效率很高，但查找元素的的效率较差。