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 核心要点