LinkedList源码分析-JDK1.8

1.概述

LinkedList 是基于双向链表来编写的，不需要考虑容量的问题，但节点需要额外的空间存储前驱和后继的引用。有序可重复，可存储 null 值，非线程安全。

1.1继承体系

LinkedList 实现了 Deque 接口，这样 LinkedList 就具备了双端队列的功能，本文旨在介绍 LinkedList 的 List 功能，队列功能不再进行说明。

LinkedList 没有实现 RandomAccess 接口，所以不要通过访问下标方式（ for(int i=0;i<size;i++) ）遍历，否则效率极差。

2.源码分析

本文主要针对 LinkedList 的常用操作进行分析，代码如下。

List<String> linkedList = new LinkedList<>();
//add(E e)
linkedList.add("QQ");
linkedList.add("WW");
linkedList.add("EE");
linkedList.add("RR");
linkedList.add("TT");
linkedList.add("YY");
linkedList.add("UU");
linkedList.add("II");
linkedList.add("OO");
//add(int index, E element)插入元素到指定结点
linkedList.add(2, "BaseC");
//get
System.out.println(linkedList.get(2));
//traverse(遍历)
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
iterator.next();
}
//remove(Object o)
linkedList.remove("EE");
//remove(int index)删除中间元素
linkedList.remove(3);
//remove(int index)删除链表头元素
linkedList.remove(0);
//remove(int index)删除链表尾元素
linkedList.remove(linkedList.size() - 1);
System.out.println(linkedList);

2.1属性

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

//链表首结点
transient Node<E> first;

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

//链表结点类
private static class Node<E> {
    //结点中的值
    E item;
    //指向之前的节点
    Node<E> prev;
    //指向之后的节点
    Node<E> next;

    //构造方法
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.2新增

2.2.1 add(E e)

//将元素添加到列表尾部
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    //将e元素添加链表末端
    void linkLast(E e) {
        //声明l变量保存当前last对象
        final Node<E> l = last;
        //以e为item声明一个新的last对象
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //第一次添加元素时
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

首次添加元素如下图所示：

非首次添加元素如下如图所示：

2.2.2 add(int index, E element)

//将元素插入到指定index，之前在此index及其之后的元素向右移动。
public void add(int index, E element) {
    //判断index是否在[0,size]之间，注意包含0和size。
    checkPositionIndex(index);
    //如果index等于当前size，调用linkLast(E e)方法，否则调用linkBefore(E e)方法
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

//返回指定index上的非空结点
Node<E> node(int index) {
    //假设index合法
    //size>>1返回size的一半，判断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;
    }
}

//在非空的succ结点之前插入元素
void linkBefore(E e, Node<E> succ) {
    //获取succ结点的prev结点
    final Node<E> pred = succ.prev;
    //在pred和succ之间生成item为e的结点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //将succ的prev指向newNode
    succ.prev = newNode;
    //如果succ是头元素，将first指向newNode
    if (pred == null)
        first = newNode;
    else
        //否则将pred的next结点指向newNode
        pred.next = newNode;
    size++;
    modCount++;
}

添加流程如下图所示：

在链表首尾添加元素很高效，时间复杂度为 O(1) 。

在链表中间添加元素比较低效，时间复杂度为 O(N) 。

2.3查找

//返回指定位置上的值
public E get(int index) {
    //检查index是否合法
    checkElementIndex(index);
    //node(int index)方法已在上文列出，此处不在展示。
    return node(index).item;
}

查找方法的重点在于 node(int index) 方法。由于需要通过从头或从尾查找元素，时间复杂度为 O(N) 。

2.4遍历

在分析源码之前，先看下 iterator() 的调用流程。首先调用 linkedList.iterator() 进入 AbstractSequentialList 的 iterator() 方法。

public Iterator<E> iterator() {
    return listIterator();
}

此方法调用了其父类 AbstractList 的 listIterator() 方法。

public ListIterator<E> listIterator() {
    return listIterator(0);
}

而在此方法中调用了 listIterator(final int index) 方法，此方法 LinkedList 将其重写了，所以程序就会去调用 LinkedList 中的 listIterator(int index) 方法。通过这个流程我们也巩固下 Java 多继承下方法的调用流程。下面咱们就来看源码吧。

public ListIterator<E> listIterator(int index) {
    //判断index是否在[0,size]之间，注意包含0和size。
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    //上一次返回的值
    private Node<E> lastReturned;
    //当前要返回的值
    private Node<E> next;
    //当前index值
    private int nextIndex;
    //用于fail-fast校验
    private int expectedModCount = modCount;

    ListItr(int index) {
        //如果index是当前size值，则next为null，否则返回对应index的结点。
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        //fail-fast判断
        checkForComodification();
        //判断当前是否还有值，调用方可直接调用next()方法获取下个值，不必额外进行hasNext（）的判断。
        if (!hasNext())
            throw new NoSuchElementException();

        //即将返回next，将next传给lastReturned
        lastReturned = next;
        //获取下次将要返回的结点
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    
    //省略其余代码。。。
}

2.5删除

2.5.1 remove(Object o)

//删除o在列表中第一次存储的位置
public boolean remove(Object o) {
    //当o为null时
    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结点,将被删除结点的prev置为null
        prev.next = next;
        x.prev = null;
    }

    //删除尾元素时
    if (next == null) {
        last = prev;
    } else {
        //将next结点的prev指针指向prev结点,将被删除结点的next置为null
        next.prev = prev;
        x.next = null;
    }

    //将x的item变为null，便于GC
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink(Node x) 其流程如下图所示：

2.5.2 remove(int index)

//删除指定index处的元素，后面的元素向左移动一位，返回被删除的元素。
public E remove(int index) {
    //检验index是否在[0,index)之内
    checkElementIndex(index);
    //通过node(int index)查找结点，将其传入unlink(Node node)方法
    return unlink(node(index));
}

在链表首尾删除元素很高效，时间复杂度为 O(1) 。

在链表中间删除元素比较低效，时间复杂度为 O(N) 。

3.参考

LinkedList 源码分析(JDK 1.8)

死磕 java集合之LinkedList源码分析