LinkedList源码分析基于JDK18

50次阅读

共计 6070 个字符，预计需要花费 16 分钟才能阅读完成。

LinkedList 源码分析 – 基于 JDK1.8

LinkedList 的 UML 图：

LinkedList 真正用来存储元素的数据结构 -> Node 类
Node 类是 LinkedList 中的私有内部类，LinkedList 中通过 Node 来存储集合中的元素

  • E：节点的值
  • Node next: 当前节点的后一个节点的引用（可以理解为指向当前节点的后一个节点的指针）
  • Node prev：当前节点的前一个节点的引用（可以理解为指向当前节点的前一个节点的指针）

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

LinkedList 的元素 

//LinkedList 节点个数，用来记录 LinkedList 的大小
transient int size = 0;

/**
 * 指向第一个节点的指针。用来表示 LinkedList 的头结点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向最后一个节点的指针。用来表示 LinkedList 的尾结点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

LinkedList 的构造函数（两个）

ArrayList 的构造函数有三个，比 LinkedList 多提供了一个设置初始化容量来初始化类。LinkedList 没有提供该方法，原因： 因为 LinkedList 底层是通过链表实现的，每添加新元素的时候，都是通过链接新的节点实现的，也就是说它的容量是随着元素的个数的变化而动态变化的。而 ArrayList 底层是通过数组来存储新添加的元素的，所以我们可以为 ArrayList 设置初始容量（也就是设置数组的大小）

/**
 * 空参构造
 */
public LinkedList() {}

/**
 * 构造包含指定集合元素的列表，按照集合的迭代器返回元素的顺序
 * 传入一个结合作为参数初始化 LinkedList。*
 * @param  c 将其元素放置在此列表中的集合
 * @throws NullPointerException 如果指定的集合为空
 */
public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

LinkedList 的构造函数（带参数）

在 LinkedList 带集合参数的构造函数中有一个重要的方法 addAll(int index, Collection), 这块儿的方法有点绕，如果没看懂，建议手画一遍。

/**
 * 通过调用 addAll(int index, Collection<? extends E> c) 添加 集合
 */
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}
/**
 * checkPositionIndex(index); 检查传入的参数是否合法
 */
public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);
    // 将集合转换为数组
    Object[] a = c.toArray();
    // numNew 存储数组的长度
    int numNew = a.length;
    // 如果 c：待添加的集合为 null，直接返回 false，不进行后面的操作
    if (numNew == 0)
        return false;
    // pred：指代 待添加节点的前一个节点
    // succ：指的是待添加节点的位置
    Node<E> pred, succ;
     // 如果 index==size，说明此时需要添加 LinkedList 的集合中每一个元素都是在 LinkedList 最后面。所以把 succ 设置为 null, pred 指向尾结点
     // 否则的话 succ 指向插入待插入位置的节点。这里用到了 node(index) 方法，pred 指向 succ 节点的前一个节点
    if (index == size) {
        // 新添加的元素的位置是位于 LinkedList 最后一个元素的后面，也就是在 LinkedList 尾部追加元素
        succ = null;
        pred = last;
    } else {succ = node(index);
        pred = succ.prev;
    }
    /**
      * 遍历数组中的每一个元素。在每次遍历的时候，都新建一个节点，该节点的值存储数组 a 中遍历的值，该节点的 prev 存储 pred 节点，next 设置为 null。* 接着判断该节点的前一个节点是否为空，如果为空的话，则把当前节点设置为头结点
      * 否则的话就把当前节点的前一个节点的 next 值设置为当前节点。最后把 pred 指向当前节点，方便后续节点的添加
      */
    for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    /**
      * 当 succ 为 null 时，也就是新添加的节点位于 LinkedList 集合的最后一个元素的后面。* 上面的 for 遍历的 a 的所有元素，此时的 pred 指向的是 Linked 中的最后一个元素，所以把 last 指向 pred 指向的节点
      * 当不为空的时候，表明在 LinkedList 集合中添加的元素，需要把 pred 的 next 指向 succ 上，succ 的 prev 指向 pred
      */
    if (succ == null) {last = pred;} else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 重新设置集合的大小
    size += numNew;
    // 修改的次数 - 自增。modCount++;
    return true;
}

LinkedList 中的一些辅助方法

  • linkFirst(E e){}; 把参数中的元素作为链表的第一个元素 
/**
 * 链接 e 作为第一个元素。*/
private void linkFirst(E e) {
    final Node<E> f = first;// LinkedList 中的第一个元素 first 赋给 f
    // 组建新的 node，新添加的元素的 succ（后指针指向给 f）final Node<E> newNode = new Node<>(null, e, f);
    // 将新插入的节点 e，赋给 first
    first = newNode;
    // 如果 f== null ; 说明是空链表，把新节点设置为尾结点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
  • linkLast(E e){}; 把参数中的元素作为链表的最后一个元素 
/**
 * 链接 e 作为最后一个元素。*/
void linkLast(E e) {
    // 获取尾部元素
    final Node<E> l = last; 
    // 以尾部元素为前继结点创建一个新节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新尾部节点为需要插入的节点
    last = newNode;

    if (l == null)
        // 如果为空链表的情况：同时更新 first 节点为需要插入的节点。（也就是说，该节点即是头结点也是尾节点 last）first = newNode;
    else
        // 不是空链表的情况：将原来的尾部节点（现在是倒是第二个节点）的 next 指向需要插入的节点
        l.next = newNode;
    size++;  // 更新链表大小和修改次数，插入完毕
    modCount++;
}
  • linkBefore(E e,Node succ); 在非空节点 succ 之前插入元素 e 
/**
 * 将元素 e 插入到非空节点 succ 之前。*/
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 创建一个 pred 变量指向 succ 节点的前一个节点
    final Node<E> pred = succ.prev;
    // 创建一个新节点，他的 prev 设置为我们新建的 pred 变量，后节点设置为 succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // succ 的上节点（prev）指向新建的节点
    succ.prev = newNode;
    // 判断 succ 的前节点是否为 null，为 null，则把新节点设置为链表的头结点
    if (pred == null)
        first = newNode;
    else
        // 不为空把，succ 的前一个节点的 next 指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
  • unlinkFirst(Node f){}; 删除 LinkedList 中的第一个节点。（该节点不为空，返回删除节点的值）。这是一个私有方法，我们不能够调用，assert f == first && f != null; 参数 f 是头结点，而且 f 不能为 null
/**
 * 解除非空第一个节点 f 的链接。*/
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 定义一个变量 element，值为待删除节点的值。final E element = f.item;
    // 定义变量 next，值为：待删除的节点的下一个节点
    final Node<E> next = f.next;
    // f 节点的值设置为空
    f.item = null;
    f.next = null; // help GC
    // 将变量 next 设置为头节点
    first = next;
    // 判断 f 的下一个节点是否为空，为空：把 last 设置为空
    if (next == null)
        last = null;
    else
        // 不为空，将 next 的前节点设置为空。next 为头结点
        next.prev = null;
    size--;
    modCount++;
    return element;
}
  • unlinkLast(Node l){}; 删除 LinkedList 的最后一个节点（该节点不为空，并返回删除节点对应的值）
/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 创建变量 element，值为: 待删除的节点的值
    final E element = l.item;
    // 创建变量 prev：值为：待删除的节点的前节点
    final Node<E> prev = l.prev;
    // 待删除的节点的值赋空
    l.item = null;
    l.prev = null; // help GC
    // 将 last 指向 新建的节点 prev 
    last = prev;
    // 判断待删除的节点的前节点是否为空，为空：该链表则为空链表，将头结点 first 赋 null 值
    if (prev == null)
        first = null;
    else
        // 不为空，将待删除的前节点的 next 指向 null
        prev.next = null;
    size--;
    modCount++;
    return element;// 返回删除的节点的值
}
  • unlink(Node e); 删除一个节点，该节点不为空 
/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    // 变量 element：值：要删除的节点的值
    final E element = x.item;
    // 新建变量：next，值：要删除的节点的下一个节点
    final Node<E> next = x.next;
    // 新建变量：prev，值：要删除的节点的上一个节点
    final Node<E> prev = x.prev;
    // 判断要删除的节点的上一个节点为空，为空：则删除的是头结点，将 first 指向新建的 next
    if (prev == null) {first = next;} else {
        // 不为空：将要删除的节点的上一个节点的 next 指向要删除的节点的下一个节点
        prev.next = next;
        x.prev = null;
    }
    // 判断要删除的节点的下一个节点是否为空，为空：则删除的尾结点，将 last 指向 prev，也就是指向要删除的节点的上一个节点
    if (next == null) {last = prev;} else {
        // 不为空，将要删除的节点的下一个节点的上节点指向 -》要删除的节点的上个节点
        next.prev = prev;
        x.next = null;
    }
    // 这一步就把要删除的节点赋了空值，有助于 gc 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}
  • Node node(int index); 计算指定索引上的节点，并返回。这里 LinkedList 不是从头开始进行遍历，而是先比较一下 index 更靠近链表的头结点还是尾结点，然后进行遍历，获取对应 index 的节点 
/**
 * 返回指定元素索引处的（非空）节点。*/
Node<E> node(int index) {// assert isElementIndex(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;
    }
}

以上是一些辅助方法，在 LinkedList 的 add，get,remove 等方法中都会使用到相应的方法。

LinkedList 中的 contains(Object o);

public boolean contains(Object o) {return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)
                return index;
            index++;
        }
    } else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

indexOf(Object o) 方法中分两种情况，

  1. 首先判断传入的参数 o 是不是空，

    1. 为空：for 循环进行查找，找第一个节点的 item 的值 ==null 的，找到返回对应的下标，没有则返回 -1
    2. 不为空，for 循环进行查找，找第一个节点的 item 的值与 o 相等的，找到返回对应的下标，没有返回 -1；

个人认为看懂了上面的方法，其他的方法都简单明了。

正文完
java
发表至： java
2020-06-18
 0
关于java:AOP的理解及例子
关于java:源码解读包装类型xxx看完大呼过瘾
关于java:后端从入门到熟悉序言
Android四大组件之Service