LinkedList详解

LinkedList初始化和添加元素

       在数组/ArrayList中读取和存储(get/set)的性能非常高，为O(1)，但插入(add(int index, E element))和删除(remove(int index))却花费了O(N)时间，效率并不高。

       下面看看Java中的另一种List即LinkedList，LinkedList是基于双向链表来实现的。

       看如下代码：

public static void main(String[] args) {
    List<Person> perList = new LinkedList<>();
    perList.add(new Person("张三", 21));
    perList.add(new Person("李四", 19));
    perList.add(new Person("王五", 25));
    perList.add(new Person("赵六", 24));
    System.out.println("perList.size()" + perList.size());
}

       进入LinkedList源码可以看到：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

       LinkedList有三个成员变量，size是LinkedList的逻辑长度，初始化为0，并持有两个Node引用，first是第一个，last是最后一个，看下图：

       初始化结束，在堆内存中就是这个样子，size为0。引用类型的成员变量初始化为null，再来看看Node，定义了一个泛型为E的变量，也持有两个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;
    }
}

       这是一个内部静态私有类，该类只能在LinkedList中访问，debug看一下：

       和图中一致，继续执行码里的add方法，看源码：

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

       e是我们往里添加的Person对象“张三”，继续跟踪linkLast方法：

void linkLast(E e) {
    final Node<E> l = last;//第一次添加，这里last为null
    final Node<E> newNode = new Node<>(l, e, null);//new一个node对象
    last = newNode;//新new出来的对象赋值给last
    if (l == null)
        first = newNode;//l为null，执行代码，新new出来的对象赋值给first
    else
        l.next = newNode;
    size++;//逻辑长度+1
    modCount++;//修改次数+1
}

       第一次往LinkedList里添加元素，first为null，last也为null，把Person对象“张三”传给了Node的构造函数，再看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;//把张三这个Person对象给了item
        this.next = next;//传过来的next为null
        this.prev = prev;//传过来的prev为null
    }
}

       用Person张三为入参构造了一个Node对象，如下图：

       debug如下：

       继续添加“李四”这个Person对象，再打开源码分析一下：

void linkLast(E e) {//e现在是李四这个对象的引用
    final Node<E> l = last;//这时候last已经是包含张三这个Person对象的Node对象，赋值给l
    final Node<E> newNode = new Node<>(l, e, null);//包含 Person张三的node，Person李四作为参数创Node
    last = newNode;//last赋值为新的newNode
    if (l == null)
        first = newNode;
    else//l不为null，执行代码，张三这个Node的next指向新的Node
        l.next = newNode;
    size++;//逻辑长度+1
    modCount++;//修改次数+1
}

       张三这个Node指向新new出来的Node对象，再看Node是怎么创建的

Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;//item指向传进来的李四这个Person对象
    this.next = next;//next还是null
    this.prev = prev;//prev指向传进来的Node对象(包含有张三的 Person对象)
}

       创建Node对象，新new出来的Node对象的prev引用指向包含Person张三的Node对象。item引用指向Person李四对象，如下图：

       看上图，原来的next引用指向新new出来的Node，同时新new出来的Node的prev引用指向原来的Node对象，item指向新new出来的Person李四这个对象，同时perList这个LinkedList对象的last引用指向新new出来的这个Node，再debug看一下：

       继续添加“王五”，“赵六”：

       很简单，没有了底层数组，新增加了一个Node对象，记录了Person的内容，每个Node对象都持有next引用(下一个)和prev引用(上一个)，其实就是双向链表，下面是一张张简化版的图：

LinkedList元素的删除原理

       下面删除王五这个用户，代码如下：

public static void main(String[] args) {
    List<Person> perList = new LinkedList<>();
    perList.add(new Person("张三", 21));
    perList.add(new Person("李四", 19));
    perList.add(new Person("王五", 25));
    perList.add(new Person("赵六", 24));

    System.out.println("删除前的perList.size()：" + perList.size());
    boolean delState = perList.remove(new Person("王五",25));//删除王五，返回删除状态
    System.out.println("打印删除状态：" + delState);
    System.out.println("删除后的perList.size()：" + perList.size());
}

       如果不重写equals方法，删除是失败的，看一下remove源码：

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

       if…else里的逻辑是一样的，只不过前者删除为null的元素，可以看出来LinkedList支持放入null的值。else代码从第一个Node节点（first节点）开始对比item的值，如果equals成功就执行unlink()方法，并返回删除成功的布尔值true。如下图是查找王五的过程：

       对比王五的查找删除操作，来看看unlink()方法：

unlink(Node<E> x) {//这儿E就是Person，x是包含“王五”的Node节点
    // assert x != null;
    final E element = x.item;//定义一个element保存item的值
    //分别定义了ー个next、pre常量来保存“王五”节点的next、prev
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {//如果王五的prev引用为null（王五是第一个Node节），把first引用指向王五的next也就星赵六Node（例子中不是这种情况，此处并不会执行）
        first = next;
    } else {//否则就把王五的prev(李四Node)的next引用指向原来王五的next引用(赵六Node)同时把王五的prev置为null
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {//如果王五的next引用为null(王五是最后一个Node节点)，把last引用指向王五的prev，也就是李四Node（例子中不是这种情况，此处并不会执行）
        last = prev;
    } else {//否则就把王五的next（赵六Node)的prev引用指向原来王五的prev引用(李四Node)同时把王五的next置为null
        next.prev = prev;
        x.next = null;
    }

    x.item = null;//item也指向null
    size--;//逻辑长度减少
    modCount++;
    return element;//返回删除王五这个Person对象
}

       上面代码逻辑简单，就是把包含王五的这个Node从双向链表中移出来，然后把王五相邻的两个Node的next和prev重新指向一下，如下图：

       重写equals方法，打印结果如下：

删除前的perList.size()：4
打印删除状态：true
删除后的perList.size()：3

与ArrayList删除比较

       删除用的是List的如下API：

public boolean remove(Object o);

       两者都在元素中循环查找，LinkedList是把Node（包含Person）从链表移出（通过修改上下节点的引用来实现），ArrayList删除底层数组元素后又把底层数组都往前复制了一格内容。

       假设要删除的元素都在这两个List中的第n位置，由于两者都循环查找了n次，省略循环查找这个步骤，直接看删除，由于ArrayList删除元素后，底层数组要往前复制一格，ArrayList底层数组删除元素时间复杂度为Ｏ(n)。再来看LinkedList，LinkedList底层链表删除元素只是简单的修改了一下引用地址，时间复杂度为O(1)。

参考资料：
清浅池塘 LinkedList初探、LinkedList元素的删除原理