Java 中 LinkedList 的底层数据结构及相关分析
1. 概述
LinkedList 是 Java 集合框架（Java Collections Framework，JCF）中的一个双向链表实现，它位于 java.util 包下，支持 列表（List） 和 队列（Queue） 相关操作。
在 LinkedList 中，元素的存储方式不同于 ArrayList，它使用 链表 结构来存储元素，因此在某些场景下比 ArrayList 具有更好的性能表现。
2. LinkedList 的底层数据结构
2.1 底层实现
LinkedList 的底层是一个 双向链表（Doubly Linked List），它的基本存储单元是 Node（内部静态类），每个节点包含：
- 数据域 (
item)：存储当前节点的数据。 - 前驱指针 (
prev)：指向前一个节点。 - 后继指针 (
next)：指向后一个节点。
2.2 源码解析（JDK 8）
Node 内部类的实现如下：
java">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 维护头尾节点：
java">transient Node<E> first;
transient Node<E> last;
3. LinkedList 的实现原理
3.1 添加元素
add(E e) (默认尾部添加)
- 创建新节点。
- 让新节点的
prev指向旧的last，并更新last指针。 - 若链表为空，则
first也指向该节点。
示例代码：
java">public boolean add(E e) {linkLast(e);return true;
}private 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;elsel.next = newNode;
}
add(int index, E element) (指定位置插入)
- 先找到索引位置的前驱和后继节点。
- 让新节点的
prev和next指向前驱和后继。 - 更新前驱和后继节点的指针。
3.2 删除元素
- removeFirst()：删除
first指向的节点，调整first指针。 - removeLast()：删除
last指向的节点，调整last指针。 - remove(index)：找到索引对应节点，调整前后指针。
示例代码（删除头节点）：
java">private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;return element;
}
3.3 查找元素
- get(int index)：通过索引访问元素。
- contains(Object o)：遍历链表检查是否包含该元素。
- indexOf(Object o)：遍历链表查找元素的索引。
get(int index) 方法会从 first 或 last 开始遍历（优化访问）：
java">Node<E> node(int 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;}
}
4. LinkedList 的应用场景
4.1 适用场景
- 频繁插入和删除元素（避免
ArrayList频繁扩容和移动元素）。 - 作为队列（Queue）使用，如
Deque结构（poll()、peek()操作）。 - 作为栈（Stack）使用，如
push()、pop()操作。 - 需要双向遍历的场景。
4.2 不适用场景
- 需要频繁随机访问的情况，
get(index)需要 O(n) 时间。 - 存储大量数据时，链表结构的额外指针占用较多内存。
5. LinkedList 的优缺点
5.1 优点
✅ 插入和删除操作效率高，时间复杂度 O(1)。
✅ 适用于 FIFO 队列和 LIFO 栈操作。
✅ 动态分配内存，避免 ArrayList 频繁扩容。
5.2 缺点
❌ 访问元素效率低，查找时间复杂度 O(n)。
❌ 额外的 prev 和 next 指针增加内存占用。
❌ 不适用于高并发场景（非线程安全）。
6. 替代方案
| 需求 | 适用数据结构 |
|---|---|
| 频繁插入、删除 | LinkedList |
| 频繁随机访问 | ArrayList |
| 线程安全的队列 | ConcurrentLinkedQueue |
| 线程安全的栈 | Stack（不推荐），Deque（推荐） |
| 需要自动扩容 | ArrayList |
示例：如果希望使用线程安全的队列，可以使用 ConcurrentLinkedQueue：
java">Queue<Integer> queue = new ConcurrentLinkedQueue<>();
queue.add(10);
queue.add(20);
System.out.println(queue.poll()); // 输出 10
7. 总结
LinkedList底层是 双向链表，适用于 频繁插入/删除，但 随机访问较慢。- 适用于 队列（FIFO）、栈（LIFO） 相关应用。
- 在大多数情况下，
ArrayList比LinkedList更合适，除非有特殊需求。 - 需要线程安全时，可使用
ConcurrentLinkedQueue、CopyOnWriteArrayList等。
