详解LinkedList中的底层实现

1.LinkedList的构造器

• 无参构造器

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

• 构造Collection: 只要是 Collection 下的实现类都可以被 LinkedList 构造

// ? extends E: 只要是E的子类及E类型的类都可以使用

public LinkedList(Collection<? extends E> c) {
    // 调用无参构造器
    this();
    // 把集合 c 中的所有元素都添加到 LinkedList 的对象中
    addAll(c);
}

2.添加元素

• 头插: 把元素插入到链表的开头

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

// 进行头插
private void linkFirst(E e) {
    // f 指向了头节点
    final Node<E> f = first;
    // 把 newNode 连接起来, newNode.next = f;
    final Node<E> newNode = new Node<>(null, e, f);
    // 让first 重新指向头节点
    first = newNode;
    // 判空
    if (f == null)
        last = newNode;
    else
        f.prev = newNode; //连接起来后面的节点
    // 长度自增
    size++;
    modCount++;
}

• 尾插: 把元素添加到链表的最后

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

// 真正进行尾插的地方
void linkLast(E e) {
    // l 指向 last, 即链表的最后一个位置
    final Node<E> l = last;
    // newNode 绑定了 prev, 即 newNode.prev = l;
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新尾结点; last 为空, 则更新 newNode 为尾结点
    last = newNode;
    // l 为空, 则说明链表中一个节点都没有
    if (l == null)
        first = newNode; // 更新为头节点
    else
        l.next = newNode; // 把 l.next 指向 newNode;
    size++; // 链表长度 +1
    modCount++;
}

• 指定位置添加元素

public void add(int index, E element) {
    // 判断 index 是否合理
    checkPositionIndex(index);

    // index 为链表的长度
    if (index == size)
        linkLast(element); // 尾插
    else
        // node(index) 找到要插入的位置, 然后进行插入
        linkBefore(element, node(index));
}

// succ 为要插入的位置, e 为要插入的值
// 尾插上面代码已经体现, 还要头插和任意位置插入未体现
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // pred 为插入位置的前一个
    final Node<E> pred = succ.prev;
    // 绑定 newNode.prev = pred, newNode.next = succ;
    final Node<E> newNode = new Node<>(pred, e, succ);
    
    // 前面已经知道了 newNode 的 prev 和 next, 还差 pred.next 和 succ.prev
    // 这个地方是绑定 succ.prev
    succ.prev = newNode;
    // 说明要插入的节点是头节点
    if (pred == null)
        first = newNode; // 头插
    else
        // 任意位置, 绑定 pred.next
        pred.next = newNode;
    size++; // 链表长度 +1
    modCount++;
}

• 指定位置添加另一个集合中的所有元素

public boolean addAll(Collection<? extends E> c) {
    // 从 0 位置开始把集合 c 中的元素全部添加到 LinkedList 的对象中
    return addAll(size, c);
}

// 具体实现细节
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查下标是否正常
    checkPositionIndex(index);
    
    // 把集合 c 转化成 Object 数组
    Object[] a = c.toArray();
    // 获取数组长度
    int numNew = a.length;
    // 空数组, 直接返回, 无需构造
    if (numNew == 0)
        return false;
    
    // 定义前驱和后继节点
    Node<E> pred, succ;
    // index 的值和 size 相同, 则需要尾插(? 因为 size 代表当前 LinkedList 对象的元素个数)
    if (index == size) {
        succ = null; 
        pred = last; // pred 指向最后一个元素
    } else {
        // succ 指向要插入位置的节点
        succ = node(index);
        // pred 指向要插入位置节点的前驱节点
        pred = succ.prev;
    }
    
    // 循环遍历数组 a
    // 要插入的所有值, 在 pred 的后面插入, 在 succ 的前面插入
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o; // 强制类型转化, 把 Object 转为特定类型
        // 进行插入, 让 newNode.prev 指向 pred, newNode.next = null;
        Node<E> newNode = new Node<>(pred, e, null);
        // 若 pred 为空, 则说明 succ 是头节点, 即说明前面是进入了 else 语句
        if (pred == null)
            first = newNode; // 更新头节点
        else
            pred.next = newNode; // 让 pred 和 newNode 相互连接(串起来)
        pred = newNode; // 更新节点, 继续插入
    }
    
    // succ 为空, 则说明是尾插法, 即进入了 size == index 内部
    if (succ == null) {
        // last 指向最后一个元素
        last = pred;
    } else {
        // 连接 pred 和 succ 节点, 把链表串起来
        pred.next = succ;
        succ.prev = pred;
    }
    
    // 添加长度
    size += numNew;
    modCount++;
    return true;
}

3.删除元素

• 头删: 把链表的最后一个元素删掉

public E removeFirst() {
    final Node<E> f = first;
    // 链表中一个节点也没有
    if (f == null)
        throw new NoSuchElementException();
    // unlinkFirst 方法中把头节点传过去
    return unlinkFirst(f);
}

// 进行头删
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取待删除节点的值
    final E element = f.item;
    // next 指向待删除节点的下一个节点
    final Node<E> next = f.next;
    // 把头节点的值置为 null
    f.item = null;
    // 让 f(头节点)和后面的节点断开
    f.next = null; // help GC
    // 头节点重置
    first = next;
    // 说明 f 只有一个节点的情况
    if (next == null)
        last = null;
    else
        next.prev = null; // 把 next 的前驱也置为空, 彻底和 f 断开连接
    size--;
    modCount++;
    // 返回删除头节点的值
    return element;
}

• 尾删: 把链表的最后一个元素删掉

public E removeLast() {
    final Node<E> l = last;
    // 一个节点都不存在
    if (l == null)
        throw new NoSuchElementException();
    // 把尾结点传到 unlinkLast 方法中
    return unlinkLast(l);
}

// 进行尾删
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 获取待删除节点的值
    final E element = l.item;
    // 获取待删除节点的前一个节点
    final Node<E> prev = l.prev;
    
    // 把待删除节点的值域和 next 域均置为空
    l.item = null;
    l.prev = null; // help GC
    // 把尾结点重置到待删除节点的前一个节点
    last = prev;
    // 只有一个节点的情况, 则 prev 为空, 则需要把头节点也置为空
    if (prev == null)
        first = null;
    else
        // 删掉最后一个节点, 即和链表前面的链表断开连接
        prev.next = null;
    size--;
    modCount++;
    return element;
}

• 删除指定节点: 那个节点值和传入要删除的值相同, 则删除该节点

// 删掉节点值与 o 相等的节点
public boolean remove(Object o) {
    // 判空
    if (o == null) {
        // 从头开始遍历节点
        for (Node<E> x = first; x != null; x = x.next) {
            // 判断那个的节点值为 null, 则删除这个节点
            if (x.item == null) {
                // 待删除的节点传到 unlink 中
                unlink(x);
                return true;
            }
        }
    } else { // 给的值不为 null
        // 遍历链表
        for (Node<E> x = first; x != null; x = x.next) {
            // 相等则删除
            if (o.equals(x.item)) {
                // 待删除的节点传到 unlink 中
                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;
        // 把待删除节点的前驱置为空
        x.prev = null;
    }
    
    // 如果待删除节点的下一个节点为空, 则说明待删除节点是尾结点
    if (next == null) {
        // 重置尾结点, 注: 后继还没有置空
        last = prev;
    } else {
        // 不是尾结点, 则让待删除节点的下一个节点的前驱指向待删除节点的上一个节点
        next.prev = prev;
        // 把待删除节点的后继置为空
        x.next = null;
    }
    // 到达这点, 已经删掉了 x 节点
    // 把x节点的值置为空
    x.item = null;
    size--;
    modCount++;
    return element;
}

4.获取/修改元素

• 获取index处的节点值

public E get(int index) {
    // 判断下标是否合法
    checkElementIndex(index);
    // 获取 index 处的值后, 返回
    return node(index).item;
}

// 查找 index 处的节点值
Node<E> node(int index) {
    // assert isElementIndex(index);
    
    // 判断 index 是否在 size 的 1/2 内, 这个设计的目的是提高查找效率
    if (index < (size >> 1)) {
        // 定义查询节点
        Node<E> x = first;
        // 从头节点开始进行遍历, 一直到 index 处的节点位置
        for (int i = 0; i < index; i++)
            x = x.next;
        // 返回 index 处的节点的位置
        return x;
    } else {
        // 查找的节点在后半段
        Node<E> x = last;
        // 从尾结点向前遍历
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        // 返回 index 处的节点
        return x;
    }
}

• 修改index处节点的节点值

public E set(int index, E element) {
    // 判断下标是否合法
    checkElementIndex(index);
    // 获取 index 处的节点值
    Node<E> x = node(index);
    // 获取原来节点的节点值
    E oldVal = x.item;
    // 把节点的节点值进行更新
    x.item = element;
    // 返回原先的节点值
    return oldVal;
}

5.获取元素第一次/最后一次出现的位置

• 获取元素第一次出现的位置

public int indexOf(Object o) {
    // 计数器, 用于获取目标节点处于那个下标
    int index = 0;
   
    if (o == null) {
        // 若是 o 为空, 也需要找到 null 在链表中的那个位置, 把这个位置返回
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 不为空, 那么就判断那个节点值和当前的 o 相等, 相等则返回对应的下标
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    // 没有找到的情况
    return -1;
}

• 获取元素最后一次出现的位置

public int lastIndexOf(Object o) {
    // 计数器, 下标从链表的最后一个位置开始
    int index = size;

    if (o == null) {
        // 若是 o 为空, 也需要找到 null 在链表中的那个位置, 把这个位置返回
        // 从尾向头开始进行遍历
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        // 不为空, 那么就判断那个节点值和当前的 o 相等, 相等则返回对应的下标
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    // 链表中不存在对应的值
    return -1;
}

6.链表长度

public int size() {
    return size;
}

// size 是 LinkedList 中的一个计数器, 用于记录链表长度的
transient int size = 0;

7.清空链表

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    // 遍历链表, 从头开始一个一个释放所占空间
    for (Node<E> x = first; x != null; ) {
        // 记录 x 的下一个节点
        Node<E> next = x.next;
        // 把 x 节点释放
        x.item = null;
        x.next = null;
        x.prev = null;
        // 指向下一个节点
        x = next;
    }
    // 头节点和尾结点置为 null
    first = last = null;
    // 长度置为 0
    size = 0;
    modCount++;
}