LinkedList 原理与源码解析

1、原理

2、源码解析

2.1、构造方法

//空参构造方法
public LinkedList() {
}

2.2、linkFirst 方法

private void linkFirst(E e) {
    final Node<E> f = first;
    //构造新节点
    final Node<E> newNode = new Node<>(null, e, f);
    //链表头节点为新节点
    first = newNode;
    //后继为空，即链表插入后只有一个元素，那么尾节点也是新节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

2.3、linkLast 方法

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

2.4、linkBefore 方法

//往某节点前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //查出前驱节点
    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++;
}

2.5、unlinkFirst 方法

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //获取要删除的节点得值
    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;
}

2.6、unlinkLast 方法

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    //获取要删除的节点的值
    final E element = l.item;
    //获取到倒数第二个节点
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    //倒数第二个设置为为节点
    last = prev;
    //删除后链表为空的情况
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

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