LinkedList源码解析-Java8

private static class Node {
    E item;  // 保存元素值
    Node next;// 后继节点
    Node prev;// 前驱结点

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

/**
 * 链表中元素的数量，transient表示持久化时不计入该字段
 */
transient int size = 0;

/**
 * 头结点（指向第一个元素，链表为空时，first为null）
 */
transient Node first;

/**
 * 尾结点（指向最后一个元素，链表为空时，last为null）
 */
transient Node last;

/**
 * 实例化一个空的LinkedList
 */
public LinkedList() {
}

/**
 * 传入集合对象，转换为链表形式
 */
public LinkedList(Collection extends E> c) {
    this();
    addAll(c);
}

/**
 * 获取链表第一个元素
 */
public E getFirst() {
    // first指向头结点
    final Node f = first;

    // first为null，证明链表为空
    if (f == null) {
        throw new NoSuchElementException();
    }

    // 链表不为空，first就是第一个元素，返回元素值
    return f.item;
}

/**
 * 获取最后一个元素
 */
public E getLast() {
    // last指向尾结点
    final Node l = last;

    // 如果last为null，证明链表为空
    if (l == null) {
        throw new NoSuchElementException();
    }
    
    // 链表不为空，last就是尾结点，返回元素值即可
    return l.item;
}

/**
 * 获取指定位置（顺序）的元素
 */
public E get(int index) {
    // 判断index是否合法
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 返回链表中index位置的Node节点
 */
Node node(int index) {
    // 判断index是在链表的前半部分还是后半部分
    if (index > 1)) {
        // index在前半部分，就从第一个元素往后开始找
        Node x = first;
        for (int i = 0; i  x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}

/**
 * 判断指定的index是否越界
 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index)) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

/**
 * 判断index是否合法
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index 

/**
 * 新增元素到链表中（追加append）
 */
public boolean add(E e) {
    // 将新元素加入链表的最后位置
    linkLast(e);
    return true;
}

/**
 * 在指定位置插入元素（index从0开始）
 */
public void add(int index, E element) {
    // 检测指定位置是否发生数组越界
    checkPositionIndex(index);

    if (index == size) {
        // 如果index==size表示将元素加入到链表末尾
        linkLast(element);
    } else {
        // 将元素element放入
        linkBefore(element, node(index));
    }
}

/**
 * 将元素链入链表的最后位置
 */
void linkLast(E e) {
    // l指向链表的尾结点
    final Node l = last;

    // 创建一个Node节点，next为null
    final Node newNode = new Node(l, e, null);
    // last指向新节点
    last = newNode;

    if (l == null) {
        // 如果尾结点为null，证明链表为空（没有元素）
        // 则新加入的元素就是第一个元素
        first = newNode;
    } else {
        // 旧的last不为null，证明链表不为空，则将新元素加入old last的后面
        l.next = newNode;
    }

    // 元素数量加1
    size++;

    // 修改次数modCount加1
    modCount++;
}

/**
 * 将元素e插入succ前面
 */
void linkBefore(E e, Node succ) {
    // 获取succ的前驱结点
    final Node pred = succ.prev;

    // 创建新节点（包含新插入的元素），pre=succ.prev，next=succ
    final Node newNode = new Node(pred, e, succ);

    // 将新节点的作为succ的前驱节点
    succ.prev = newNode;

    if (pred == null) {
        // 如果pred=succ.prev节点为null，证明没有前驱结点，则新加入的元素作为首元素
        first = newNode;
        // 插入后结果就是 newNode  succ
    } else {
        // 将新节点作为succ前驱节点后继节点
        pred.next = newNode;
        // 最终就是 succ.prev  newNode  succ
    }

    // 链表数量加1
    size++;

    // 修改次数加1
    modCount++;
}

/**
 * 将元素加入链表（作为头结点）
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 将元素加入到链表中，作为尾结点
 */
public void addLast(E e) {
    // 调用linkLast，参考add()中linkLast
    linkLast(e);
}

/**
 * 将元素e插入链表，作为头结点
 */
private void linkFirst(E e) {
    final Node f = first;
    // 创建新节点，next为当前的头结点
    final Node newNode = new Node(null, e, f);

    // first指向新节点
    first = newNode;
    if (f == null) {
        // 如果f为null，证明插入元素前，链表为空，插入新元素后，链表就只有1个元素
        // 所以修改last指向新插入的元素（first和last指向同一个元素）
        last = newNode;
    } else {
        // 插入之前，链表不为空，则维护旧的头结点和新节点的关系
        f.prev = newNode;
    }
    // 元素数量加1，修改次数加1
    size++;
    modCount++;
}

/**
 * 将元素链入链表的最后位置
 */
void linkLast(E e) {
    // l指向链表的尾结点
    final Node l = last;

    // 创建一个Node节点，next为null
    final Node newNode = new Node(l, e, null);
    // last指向新节点
    last = newNode;

    if (l == null) {
        // 如果尾结点为null，证明链表为空（没有元素）
        // 则新加入的元素就是第一个元素
        first = newNode;
    } else {
        // 旧的last不为null，证明链表不为空，则将新元素加入old last的后面
        l.next = newNode;
    }

    // 元素数量加1，修改次数modCount加1
    size++;
    modCount++;
}

/**
 * 移除链表首元素
 *
 * @return 返回移除的元素
 */
public E removeFirst() {
    final Node f = first;

    // 如果f头结点为null，证明链表为空，此时删除头结点是非法的
    if (f == null) {
        throw new NoSuchElementException();
    }

    // 删除头结点元素
    return unlinkFirst(f);
}

/**
 * 移除链表最后一个元素，并返回移除的元素
 */
public E removeLast() {
    final Node l = last;

    // 如果尾结点为null，证明链表为空，所以删除最后一个元素是非法的
    if (l == null) {
        throw new NoSuchElementException();
    }

    // 删除链表最后一个元素
    return unlinkLast(l);
}

/**
 * 移除首节点（f就是首节点）
 */
private E unlinkFirst(Node f) {
    final E element = f.item;
    final Node next = f.next;

    // 将f节点清空，GC的时候会清除f节点的数据
    f.item = null;
    f.next = null; // help GC

    // 将next节点作为新的头结点
    first = next;

    if (next == null) {
        // 如果新的头结点为null，证明链表之前就只有f节点一个元素
        // 删除f后，链表元素为空，last指向最后一个元素，也为null
        last = null;
    } else {
        // next作为首节点，则需要将其前驱结点设置null
        next.prev = null;
    }

    // 元素数量减1，修改次数加1，并发挥删除的元素
    size--;
    modCount++;
    return element;
}

/**
 * 删除尾结点l
 */
private E unlinkLast(Node l) {
    final E element = l.item;
    final Node prev = l.prev;

    // 将l节点（当前的last节点）设置为null，GC时回收
    l.item = null;
    l.prev = null; // help GC

    // 将last指针向前移动
    last = prev;
    if (prev == null) {
        // 如果prev为null，表示最后一个元素的前驱为null->最后一个元素就是首元素
        // 移除最后一个元素后，链表就为空，此时将指向头元素的first设置为null
        first = null;
    } else {
        // 将prev的next设置为null，取消对最后一个元素的引用
        prev.next = null;
    }

    // 元素数量减1，修改次数加1，并返回删除的元素
    size--;
    modCount++;
    return element;
}

/**
 * 删除指定index的元素
 *
 * @return 被删除的元素
 */
public E remove(int index) {
    // 检测index是否发生越界
    checkElementIndex(index);

    // node(index)是返回链表中index位置的Node节点，也就是包含要删除元素的Node
    return unlink(node(index));
}

/**
 * 移除指定元素（只移除第一个匹配的）
 *
 * @param o 要移除的元素
 * @return true移除成功；false未找到要溢出的元素
 */
public boolean remove(Object o) {
    // 如果要删除的元素为null，则使用==进行比较，否则使用equals进行比较
    // 遍历整个链表，找到第一个匹配的Node节点，并调用unlink进行删除Node
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * 将节点x从链表中移除
 */
E unlink(Node x) {
    final E element = x.item;
    final Node next = x.next;
    final Node prev = x.prev;
    // prev  x  next

    if (prev == null) {
        // prev为null，表示x是首节点，此时删除x，则直接将first指向next节点即可
        first = next;
    } else {
        // prev不为null，表示x不是首节点，则修改指针，关联prev和next
        prev.next = next;
        // 取消x.prev的引用（help GC）
        x.prev = null;
    }

    if (next == null) {
        // next为null，表示x是尾结点，此时删除x，则直接将last指向prev节点即可
        last = prev;
    } else {
        // next不为null，表示x不是尾结点，则将prev和next进行关联
        next.prev = prev;
        // 取消x.next的引用（help GC）
        x.next = null;
    }

    // 将x的元素置为null（help GC）
    x.item = null;

    // 元素数量减1，修改次数加1，并返回删除的元素
    size--;
    modCount++;
    return element;
}

/**
 * 元素入队（作为尾结点）
 */
public boolean offer(E e) {
    return add(e);
}

// Deque operations

/**
 * 元素入队（作为头结点）
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * 元素入队（作为尾结点）
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * 头结点出队（队列为空，则返回null）
 */
public E poll() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 头结点出队（队列为空，则返回null）
 */
public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 尾结点出队（队列为空，则返回null）
 */
public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}

/**
 * 返回队首元素（不出队）
 */
public E peek() {
    final Node f = first;
    return (f == null) ? null : f.item;
}

/**
 * 返回队首元素（不出队）
 */
public E peekFirst() {
    final Node f = first;
    return (f == null) ? null : f.item;
}

/**
 * 返回队尾元素（不出队）
 */
public E peekLast() {
    final Node l = last;
    return (l == null) ? null : l.item;
}

/**
 * 模拟栈数据结构的push
 */
public void push(E e) {
    addFirst(e);
}

/**
 * 模拟栈数据结构的pop
 */
public E pop() {
    return removeFirst();
}