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)方法中分两种情况，

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

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

LinkedList源码分析基于JDK18

LinkedList源码分析–基于JDK1.8

LinkedList的元素

LinkedList的构造函数（两个）

LinkedList的构造函数（带参数）

LinkedList中的一些辅助方法

LinkedList中的contains(Object o);

评论

发表回复取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

LinkedList源码分析基于JDK18

LinkedList源码分析–基于JDK1.8

LinkedList的元素

LinkedList的构造函数（两个）

LinkedList的构造函数（带参数）

LinkedList中的一些辅助方法

LinkedList中的contains(Object o);

评论

发表回复 取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

发表回复取消回复