Java数据结构之LinkedList

Java 中的 LinkedList —— 这是一个基于双向链表的集合类，与 ArrayList 的数组结构形成鲜明对比。

一、LinkedList 的底层结构

1. 底层实现：双向链表

• LinkedList 是基于 双向链表（Doubly Linked List） 实现的，每个节点包含：
  • 数据（element）
  • 前驱节点指针（prev）
  • 后继节点指针（next）

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 维护两个头尾指针：
  • first：指向链表的第一个节点
  • last：指向链表的最后一个节点

二、LinkedList 的核心特性

 三、时间复杂度对比（与 ArrayList 对比）

一句话：

• 随机访问：ArrayList 更快
• 中间插入/删除：LinkedList 更快
• 尾部操作：两者接近（LinkedList 无扩容开销）

四、LinkedList vs ArrayList 的核心区别

如果业务中主要是频繁在中间插入或删除，且不常随机访问，LinkedList 更合适；如果是频繁按索引查询或尾部操作，ArrayList 性能更好。

五、LinkedList 的常见操作源码解析

1. 添加元素（尾部）

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

• 时间复杂度：O(1)

2. 插入元素（指定位置）

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size) {
        linkLast(element);
    } else {
        Node<E> succ = node(index); // 找到指定位置的节点
        Node<E> pred = succ.prev;
        Node<E> newNode = new Node<>(pred, element, succ);
        succ.prev = newNode;
        if (pred == null) {
            first = newNode;
        } else {
            pred.next = newNode;
        }
        size++;
        modCount++;
    }
}

• 时间复杂度：O(n)（需定位节点）

六、LinkedList 的线程安全问题

1. 线程不安全

• LinkedList 不是线程安全的。多线程环境下，如果多个线程同时修改（如 add/remove），可能导致数据不一致或异常。

2. 如何保证线程安全？

// 方式1：同步包装
List<String> syncList = Collections.synchronizedList(new LinkedList<>());

// 方式2：使用 CopyOnWriteArrayList
List<String> cowList = new CopyOnWriteArrayList<>();

对比：

• synchronizedList：所有操作加锁，性能较低。
• CopyOnWriteArrayList：写操作复制整个数组，开销大，但读操作无锁，适合“读多写少”场景（如监听器列表）。

七、LinkedList 的 fail-fast 机制

• LinkedList 的迭代器同样基于 modCount 实现 fail-fast 机制。
• 原理：
  • 迭代器创建时保存 expectedModCount = modCount。
  • 每次 next() 前检查 modCount == expectedModCount，不一致则抛出 ConcurrentModificationException。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

• 单线程下，边遍历边修改也会触发异常。
• 正确删除方式：使用 Iterator.remove()，它会同步更新 expectedModCount。

八、LinkedList 的一些理论问题

1. 为什么 LinkedList 的随机访问效率低？

因为 LinkedList 是基于链表实现的，访问第 n 个元素需要从头节点或尾节点遍历到目标位置，时间复杂度为 O(n)。

// LinkedList 的 get(index) 实现
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // 如果 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;
    }
}

2. LinkedList 和 ArrayList 的适用场景？

3. LinkedList 的内存占用为什么比 ArrayList 高？

LinkedList 的每个节点除了存储元素外，还需要存储 prev 和 next 指针，导致内存开销比 ArrayList 大。

4. 如何高效删除 LinkedList 中的所有值为 100 的元素？

推荐方式：

// 使用迭代器（避免并发修改异常）
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 100) {
        it.remove(); // ✅ 安全删除
    }
}

// 或使用 removeIf（Java 8+）
list.removeIf(x -> x == 100);

 九、LinkedList 的优缺点总结

十、实际应用

1. 何时选择 LinkedList？

   • 需要频繁在头部或中间插入/删除元素（如任务队列、历史记录）。
   • 不需要频繁随机访问元素。

2. 何时避免 LinkedList？

   • 需要频繁按索引访问元素（如日志查询、缓存）。
   • 内存敏感场景（链表节点指针占用额外内存）。

 十一、得到的技巧

题目：如何高效合并两个有序的 LinkedList？

 参考：

// 使用双指针合并两个有序链表
public static LinkedList<Integer> mergeTwoSortedLists(LinkedList<Integer> l1, LinkedList<Integer> l2) {
    LinkedList<Integer> result = new LinkedList<>();
    Node<Integer> p1 = l1.getFirstNode(), p2 = l2.getFirstNode();

    while (p1 != null && p2 != null) {
        if (p1.item <= p2.item) {
            result.add(p1.item);
            p1 = p1.next;
        } else {
            result.add(p2.item);
            p2 = p2.next;
        }
    }

    // 添加剩余元素
    while (p1 != null) {
        result.add(p1.item);
        p1 = p1.next;
    }

    while (p2 != null) {
        result.add(p2.item);
        p2 = p2.next;
    }

    return result;
}

解释：

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)

最后总结：LinkedList 核心要点