LinkedList源码分析

LinkedList的继承体系

主要属性

// 元素的个数
transient int size = 0;
// 链表首节点
transient Node<E> first;
// 链表末节点
transient Node<E> last;

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

构造方法

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

添加元素

// 从首添加元素
private void linkFirst(E e) {
    // 首节点
    final Node<E> f = first;
    // 创建一个新节点，把首节点作为新节点的next
    final Node<E> newNode = new Node<>(null, e, f);
    // 设置首节点为新节点
    first = newNode;
    // 判断是否是第一个添加元素的，
    // 如果是，把尾节点也设置为当前元素node
    // 如果不是，把原有的节点上一个节点指向新节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 元素的个数+1
    size++;
    // 操作次数+1
    modCount++;
}
// 从尾部添加元素
void linkLast(E e) {
    // 尾节点
    final Node<E> l = last;
    // 创建一个新节点，设置上一个节点为尾节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 设置尾节点为当前新节点
    last = newNode;
    // 判断是第一个添加的元素
    // 如果是，设置首节点为当前节点Node
    // 如果不是，设置尾节点的下一个元素为点前节点Node
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 元素个数+1
    size++;
    // 操作次数+1
    modCount++;
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

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

// 作为无界队列，添加元素总是会成功的
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

指定位置插入元素

// succ前插入E
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 获取succ上一个的节点
    final Node<E> pred = succ.prev;
    // 设置新的节点，上一个节点为原succ前节点，下节点为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 重新设置succ的上一个节点
    succ.prev = newNode;
    // 如果succ前节点为空，那么新的节点为第一个节点
    // 否则设置前置节点的下一个元素为当前元素
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 元素个数+1
    size++;
    // 操作次数+1
    modCount++;
}
// 指定位置添加元素
public void add(int index, E element) {
    // 判断是否越界
    checkPositionIndex(index);
    // 判断当前位置是否等于元素的个数
    // 如果相等的话直接插入到最后
    // 不相等的话调用上一个方法
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// 指定位置查找节点
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 将集合的size进行二分
    // 判断元素位置在前一段还是后一段
    // 如果在前一段，循环首节点的下一个元素，直到当前
    // 如果在后一段，循环尾节点的上一个元素，直到当前
    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;
    }
}

删除元素

// 删除首节点
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取自身信息
    final E element = f.item;
    // 获取下一节点
    final Node<E> next = f.next;
    // 设置当前节点和下一节点为空，协助GC
    f.item = null;
    f.next = null; // help GC
    // 设置首节点为下一个节点
    first = next;
    // 如果下一节点为空
    // 那么设置尾节点为空
    // 下一节点不为空，设置下一节点的上一个节点为空
    if (next == null)
        last = null;
    else
        next.prev = null;
    // 元素个数-1
    size--;
    // 操作次数+1
    modCount++;
    // 返回当前元素
    return element;
}
// 移除尾节点
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 当前节点
    final E element = l.item;
    // 上一节点
    final Node<E> prev = l.prev;
    // 设置当前节点和上一节点为空，协助GC
    l.item = null;
    l.prev = null; // help GC
    // 设置尾节点为上一节点
    last = prev;
    // 判断上一节点是否为空
    // 为空，设置首节点为null
    // 不为空设置上一节点的下个节点为null
    if (prev == null)
        first = null;
    else
        prev.next = null;
    // 集合数-1
    size--;
    // 操作次数+1
    modCount++;
    // 返回当前元素
    return element;
}
// 指定节点删除
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
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    // 判断下一节点是否为空
    // 为空，设置最后一个节点为上一节点
    // 不为空，设置下一节点的上一节点为当前元素的上一节点，当前元素的下一节点设置为null
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    // 当前元素设置为null
    x.item = null;
    // 元素个数-1
    size--;
    // 操作次数+1
    modCount++;
    // 返回当前元素
    return element;
}
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);
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

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

栈操作

public void push(E e) {
    addFirst(e);
}

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

栈的特性是LIFO(Last In First Out)，所以作为栈使用也很简单，添加删除元素都只操作队列首节点即可。

总结

• LinkedList是一个以双链表实现的List；
• LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；
• LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
• LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
• LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；
• LinkedList在功能上等于ArrayList + ArrayDeque；