不一样的List 02——LinkedList解析

在List中，LinkedList也是一个非常常见的实现，LinkedList内部是一个双向链表。所有的元素都会以节点的形式保存在内存中，然后通过对链表的操作，来变动这个数据结构。

节点对象

上面提到所有的元素都会以节点的形式保存在内存中, 那么来观察这个内部的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. item：当前元素值
2. next：下一个节点
3. prev：前一个节点

另外在这个类中，最重要的两个参数头节点和尾节点：

transient Node<E> first;

transient Node<E> last;

初始化

相比ArrayList,LinkedList只有两个构造方法：

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c); // 将Collection利用添加元素的方法直接加入链表中
}

这两个构造函数都非常简单，几乎没有什么内容。

添加元素

LinkedList会通过add()方法完成最基本的插入操作：

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

由上述可以看出，添加一个元素到LinkedList之中就是将元素添加到这个链表的尾部。详细地探究下linkLast()方法：

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

这里linkLast()函数会构建一个新的Node节点（如果first节点为空，会将这个节点设置成头节点），并将这个节点设置为last尾节点。将上一个尾节点的下一个节点设置为新的节点。

除此之外，还有addAll()函数：

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    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;
    }
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

由以上可以看出addAll()函数会将c转换成数组，然后找到index元素的位置，将数组的元素循环添加到尾节点上。

删除节点

根据索引位置删除节点的位置：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

node()函数是一个查找元素的方法：

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

这个函数先判断索引的位置在前半段还是后半段，然后通prev或者next遍历直到index的位置。

unlink()函数则将传入的节点从链表中移除，并将这个元素的前后元素链接起来：

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.item = null;
    size--;
    modCount++;
    return element;
}

查询

LinkedList查询特别简单,就是利用了之前已经看过的node()方法：

public E get(int index) {
    checkElementIndex(index); // 检查数组是否会越界
    return node(index).item;
}

总结

很明显相比ArrayList，LinkedList在增加和删除的时候，不需要大动干戈，自然会节约很多资源（但依然没有办法避免GC），但是在查询元素上，LinkedList就会费劲很多，需要遍历整个链表才能找到数据。