LinkedList源码分析

LinkedList源码分析(基于Jdk 11.0.2)

LinkedList和ArrayList都是实现了List接口，这两个类也经常拿来作比较。

总体来讲，它们有以下不同：

• 1，ArrayList底层是数组，LinkedList底层是双向链表
• 2，ArrayList由于底层是数组，所以查找和修改元素快，因为它可以直接操作角标，但是增加、删除操作就慢些，因为要移动大量元素；LinkedList则恰恰相反，因为是用指针指向下一个元素，所以增删只要修改指针的指向就可以达到，而且只需要修改一个，但是LinkedList查找和修改就效率低一些，因为要定位到元素，对于LinkedList来说会慢一些(不想数组一样有下标可以直接操作)
• 3，LinkedList和ArrayList都不是线程安全的

public LinkedList() {

}

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

构造函数没做什么。
Node节点：

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

可以看出它是双向链表。

1，增加元素

//addAll ,在尾部批量增加
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);//以size为插入下标，插入集合c中所有元素
}

//以index为插入下标，插入集合c中所有元素
public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);//检查越界 [0,size] 闭区间
        //检查越界 [0,size] 闭区间
        Object[] a = c.toArray();
        //新增元素的数量
        int numNew = a.length;
        //如果新增元素数量为0，则不增加，并返回false
        if (numNew == 0)
            return false;
        //index节点的前置节点，后置节点
        Node<E> pred, succ;
        //在链表尾部追加数据
        if (index == size) {
            //size节点（队尾）的后置节点一定是null
            succ = null;
            //前置节点是队尾
            pred = last;
        } else {
            //取出index节点，作为后置节点
            succ = node(index);
            //前置节点是，index节点的前一个节点
            pred = succ.prev;
        }
        //链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过
        //System.arraycopy完成批量增加的
        for (Object o : a) {//遍历要添加的节点
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);//以前置节点 和 元素值e，构建new一个新节点，
            if (pred == null)//如果前置节点是空，说明是头结点
                first = newNode;
            else//否则 前置节点的后置节点设置问新节点
                pred.next = newNode;
            pred = newNode;//当前的节点为前置节点了，为下次添加节点做准备
        }

        if (succ == null) {//循环结束后，判断，如果后置节点是null。 说明此时是在队尾append的
            last = pred;//则设置尾节点
        } else {
            pred.next = succ;// 否则是在队中插入的节点 ，更新前置节点 后置节点
            succ.prev = pred;//更新后置节点的前置节点
        }
         // 修改数量size
        size += numNew;
        //修改modCount
        modCount++;
        return true;
    }

//检查index是否越界(0,size)
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//如果没有越界返回true
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

插入单个节点

//在尾部插入一个节点： add
public boolean add(E e) {
    linkLast(e);
    return true;
}

//生成新节点 并插入到 链表尾部， 更新 last/first 节点
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加1
        size++;
        ////修改modCount
        modCount++;
}

删除节点

public E remove(int index) {
    //先检查index是否越界
    checkElementIndex(index);
    //删除元素
    return unlink(node(index));
}

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 {
            //这里跳过了x节点
            prev.next = next;
            x.prev = null;//将当前节点的 前置节点置空
        }
        //如果后置节点为空（说明当前节点原本是尾节点）
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            //将当前节点的 后置节点置空
            x.next = null;
        }
        //将当前元素值置空
        x.item = null;
        //数量减1
        size--;
        //修改modCount
        modCount++;
        //返回被删除的元素值
        return element;
}

##