JDK源码分析（4）之 LinkedList 相关

LinkedList 是继承于 AbstractSequentialList 的双向链表实现。它通过维护两个指针（head 和 tail）实现对链表的遍历。这个类的特点是可以在 O(1) 的时间内插入或删除元素，所以适合需要频繁操作的场景。

下面我们来分析一下 LinkedList 的源码实现。

# 内部实现

LinkedList 实现了 List、Deque 和 Queue 接口，拥有多种访问和操作元素的方法，如：add、offer、remove、peek 等等。下面是一些常用方法的源码实现：

## add

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

}

## remove

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) {

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

    return element;

}

## peek

public E peek() {

    final Node<E> f = first;

    return (f == null) ? null : f.item;

}

通过这些方法的源码实现，我们可以看到 LinkedList 的设计理念是，尽量使操作时间复杂度为 O(1)。

# 应用场景

LinkedList 适用于在内存中频繁地开辟、释放空间的场景，如文件缓存、内存池等等。同时也适合在数据量较小的情况下进行操作。

然而，由于内部实现原因，LinkedList 并不适合在数据量较大的情况下进行操作，因为会产生大量 GC 垃圾回收。在这种情况下，建议使用 ArrayList 或者其他的数据结构。

# 总结

LinkedList 的设计思路是典型的时间换空间，通过维护头尾指针，实现操作的快速响应。它适合在数据量较小或在内存频繁开辟、释放空间的场景使用。但对于数据量较大的情况，需要注意会产生大量 GC 垃圾回收的问题。