源码解读之 LinkedList

ArrayList 和 LinkedList 的区别以及优缺点

• ArrayList 使用数组保存元素；LinkedList 使用双向链表保存元素；
• 查找数据时，ArrayList 性能高于 LinkedList。因为 ArrayList 由于是数组的实现方式，支持使用 index 查找数据；LinkedList 使用双向链表在查找数据上性能比 ArrayList 差；
• 在固定位置添加、删除数据时，LinkedList 性能高于 ArrayList。
  • 因为 ArrayList 存在数组扩容和数组元素的移动，要插入、删除的 index 的位置越靠前，要移动的元素越多，性能越差。
  • 注意，如果比较两者往末尾处添加数据，假设 数组也不需要扩容，那么此时二者的性能没有差别。因为 ArrayList 此时不需要移动元素和扩容了。

LinkedList 类结构

1. LinkedList 实现了 Deque 接口，因此支持 Deque 所有特性，底层是一个双向链表。是一个直线型的链表结构。

2. LinkedList 集合中的字段

   • size：用来记录 LinkedList 的大小
   • Node first：用来表示 LinkedList 的头节点。
   • Node last：用来表示 LinkedList 的尾节点

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
 }

3. LinkedList 通过 Node 来存储集合中的元素，Node 类是 LinkedList 中的私有内部类。
   • 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 提供了两个构造器，ArrayList 比它多提供了一个通过设置初始化容量来初始化类。

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

public LinkedList() {
}
// 首先调用一下空的构造器。然后调用addAll(c)方法。
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

add(E e) 方法

public boolean add(E e) {
    linkLast(e);
    return true;
}
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++;
}

add(int index, E element) 方法

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        // node(index) 代码参见下一章节：get(int index) 方法
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

get(int index) 方法

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // 折半查找一次，然后for遍历
    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;
    }
}

remove(int index) 方法

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
E unlink(Node<E> x) {
    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;
}

size() 方法

public int size() {
    return size;
}

clear() 方法

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}