JAVA源码解读之LinkedList

简介

LinkedList是一个双端队列，它对内部元素的新增或删除操作，时间复杂度为O(1)，但是访问时时间复杂度为O(N)，内部的写操作是否高效，所以如果你需要做一些频繁写但是又少量查询到操作，那么就到了LinkedList的发挥时间。

重点属性

transient int size = 0;

/**
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * Pointer to last node.
 */
transient Node<E> last;
// 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;
    }
}

构造器

// 空的构造函数
public LinkedList() {
}
// 带参构造函数
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

关键方法

添加数据

add(e)

将一个元素添加到队列尾部，如果添加成功，返回True。

构造一个新的Node，并将这个Node指向last。然后这里有了分支，

l == null 说明内部元素是空的，此时LinkedList中first和last都是同一个Node
否则，说明内部已经有数据了，此时将之前的最后一个元素的next指针指向新Node

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

void linkLast(E e) {
    // 声明一个变量l，表示最后一个元素
    final Node<E> l = last;
    // 构造一个新的Node，并指定这个Node的prev为l，next为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 将新Node指向last
    last = newNode;
    if (l == null)
        // 如果内部元素为空，将新Node指向first，所以此时LinkedList中first和last都是同一个Node
        first = newNode;
    else
        // 将之前的最后一个元素的next指针指向新Node
        l.next = newNode;
    size++;
    modCount++;
}

add(int index, E element)

在列表中的指定位置插入element元素，之前在该位置以及该位置右边的所有元素都要向右移动。

public void add(int index, E element) {
    // 校验index的合法性，该index必须满足条件：index >= 0 && index <= size， 否则抛出IndexOutOfBoundsException
    checkPositionIndex(index);
	
    if (index == size)
        // 如果索引与数组大小相等，将元素放到最后即可，这点和add()方法是一致的
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// succ为原索引位置的值
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 原值的前一个Node
    final Node<E> pred = succ.prev;
    // 构造一个新Node，前置节点为原Node的前置Node，后置节点为原值
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将原Node的前置索引指向新Node
    succ.prev = newNode;
    if (pred == null)
        // 如果是第一个元素，将新Node赋值给first
        first = newNode;
    else
        // 否则，将原值的前置Node的next指针指向新Node
        pred.next = newNode;
    size++;
    modCount++;
}

// 返回索引位置元素，这里做了查找上的优化，即如果索引在前半段就从前往后搜到索引位置，如果索引在后半段就从后往前搜到索引位置
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;
    }
}

addFirst(E e)

将元素插入到队首的位置。大体逻辑为构造一个新Node，其中前置节点为null，后置节点原first指向的Node，然后分为两种情况

first节点为null，就将last也指向新Node
first节点不为null，将它的前置引用指向新Node

1
2
3

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

addLast(E e)

将元素插入到队尾都位置。可以看到它底层调用的是linkLast方法，这与add()方法的逻辑是一致的，这里不多阐述。

1
2
3

public void addLast(E e) {
    linkLast(e);
}

offer(E e)

也是往队列中插入元素，它与add()的逻辑是完全一致的，其它的几个offer方法如下：

offer(E e) 同 add(E e)
offerFirst(E e) 同 addFirst(E e)
offerLast(E e) 同 addLast(E e)

push(E e)

将元素插入队首，同addFirst(E e)

1
2
3

public void push(E e) {
    addFirst(e);
}

addAll()

将c中所有元素依次插入到队列中

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; // 此时pred就是最后一个Node
    } else { // 否则，从指定位置开始插入，此时pred是插入位置Node
        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;
}

删除操作

remove()

删除队首的数据。将first指向的节点数据删除，同时将first指向节点的next节点作为首节点。

1
2
3

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

remove(int index)

删除指定位置的节点，同时将删除节点的上下游节点关联起来。

public E remove(int 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 {
        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;
}

remove(Object o)

删除队列中第一个等于o的Node

public boolean remove(Object o) {
    if (o == null) { // null要特殊处理
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // 底层还是调用unlinx()方法
                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;
}

数据访问

get(index)

获取指定索引的值。

public E get(int index) {
    // 校验索引
    checkElementIndex(index);
    // node方法获取指定位置的值，前面已解释过，这里不多说
    return node(index).item;
}

poll()

移除并返回链表的第一个元素

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

pop()

移除并返回链表的第一个元素

1
2
3

public E pop() {
    return removeFirst();
}

peek()

返回链表头部的元素

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

element()

返回链表头部的元素，如果链表为空时调用此方法，抛出NoSuchElementException。等同于getFirst()。

与ArrayList做下比较

ArrayList和LinkedList都是Java中的List接口的实现，但它们在内部数据结构和性能上有所不同：

内部数据结构：ArrayList是基于动态数组实现的，它可以通过索引直接访问元素，因此在访问元素时具有较高的性能。而LinkedList是基于双向链表实现的，每个元素都包含了指向前一个和后一个元素的链接，因此在添加或删除元素时具有较高的性能。
性能：由于ArrayList是基于数组实现的，所以在随机访问元素时，ArrayList的性能要优于LinkedList。但是，LinkedList在添加或删除元素时，尤其是在列表的开头或结尾，性能要优于ArrayList，因为LinkedList不需要移动其他元素。
内存占用：LinkedList的每个元素都需要更多的内存，因为它需要存储两个指向前后元素的链接。而ArrayList的内存占用较少，因为它只需要存储元素本身。
扩容：当ArrayList的容量不足以容纳更多的元素时，它会创建一个新的数组，并将旧数组的所有元素复制到新数组中，这是一个相对耗时的操作。而LinkedList在添加元素时不需要进行这样的操作，因为它是基于链表的。