LinkedList

LinkedList 是 Java 集合框架中 List 接口和 Deque 接口的一个实现类，它位于 java.util 包下。与 ArrayList 不同，LinkedList 底层是基于双向链表实现的。下面将详细介绍其底层数据结构和实现原理。

底层数据结构概述

LinkedList 底层使用双向链表来存储元素。双向链表由一系列节点（Node）组成，每个节点包含三个部分：指向前一个节点的引用（prev）、存储的元素（item）和指向后一个节点的引用（next）。这种结构使得 LinkedList 在插入和删除元素时效率较高，但随机访问元素的效率较低。

核心内部类 Node

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

• item：用于存储节点所包含的元素。
• next：指向下一个节点的引用。
• prev：指向前一个节点的引用。

核心属性

LinkedList 类中有几个核心属性，它们在实现双向链表的过程中起着关键作用：

// 链表的大小，即链表中元素的数量
transient int size = 0;
// 指向链表的第一个节点
transient Node<E> first;
// 指向链表的最后一个节点
transient Node<E> last;

• size：表示 LinkedList 中实际存储的元素数量。
• first：指向链表的第一个节点，如果链表为空，则为 null。
• last：指向链表的最后一个节点，如果链表为空，则为 null。

构造方法

LinkedList 提供了两个构造方法：

// 默认构造方法，创建一个空的 LinkedList
public LinkedList() {
}

// 构造一个包含指定集合元素的列表，顺序由集合的迭代器返回
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

• 默认构造方法：创建一个空的 LinkedList，first 和 last 都为 null，size 为 0。
• 包含指定集合元素的构造方法：先调用默认构造方法创建一个空的 LinkedList，然后将指定集合中的元素添加到链表中。

元素的增删改查操作

添加元素

• 在链表末尾添加元素：

// 在链表末尾添加元素
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++;
}

• 在指定位置插入元素：

// 在指定位置插入元素
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// 在指定节点之前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    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++;
}

// 根据索引查找节点
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;
    }
}

删除元素

• 删除指定位置的元素：

// 删除指定位置的元素
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;
}

• 删除指定元素：

// 删除指定元素
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;
}

修改元素

// 修改指定位置的元素
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

查找元素

// 根据索引查找元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

总结

LinkedList 底层基于双向链表实现，通过节点的 prev 和 next 引用将各个节点连接起来。这种结构使得 LinkedList 在插入和删除元素时效率较高，因为只需要修改节点的引用即可，不需要像 ArrayList 那样移动大量元素。但在随机访问元素时，LinkedList 需要从头或尾开始遍历链表，效率较低。因此，LinkedList 适用于需要频繁插入和删除元素，而随机访问操作较少的场景。