Java Academy · 课时

LinkedList 内部原理

Q: 「LinkedList 内部原理」这节课中我会学到什么？

探索 LinkedList 的双向链节点结构及其时间复杂度特征 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

探索 LinkedList 的双向链节点结构及其时间复杂度特征

LinkedList 内部原理 是 CoddyKit 上的免费 Java Academy 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

LinkedList 内部原理

Java 的 LinkedList 是一个双向链表：每个节点都保存对前一个节点和后一个节点的引用，以及元素值。与 ArrayList 不同，它没有底层数组——内存按节点分别分配。

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

时间复杂度概览

LinkedList 的性能特征与 ArrayList 有显著差异：

addFirst / addLast：O(1)
get(index)：O(n)——必须从头部或尾部遍历
remove(index)：查找需要 O(n)，解除链接需要 O(1)
迭代器遍历：O(n)

当您需要频繁在头部或尾部插入元素，而不需要随机访问时，请使用 LinkedList。

创建和遍历 LinkedList

创建 LinkedList 并进行迭代时，使用的仍是您已经熟悉的 List 接口。区别在于内部结构。

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst、addLast、removeFirst、removeLast

LinkedList 提供了 ArrayList 无法高效提供的头部和尾部操作：

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

解除节点链接：找到节点后以 O(1) 删除

通过迭代器获得节点的引用后，删除操作的时间复杂度为 O(1)，因为只需更新 next/prev 指针——不像 ArrayList 那样需要移动元素。

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

与 ArrayList 的内存开销比较

每个 LinkedList 节点都包含两个额外的引用（prev、next）以及元素引用——在 64 位 JVM 上每个条目约占 48 字节。ArrayList 只在连续数组中存储元素引用（8 字节）。

对于大型且以读取为主的数据集，ArrayList 通常更有利于缓存，并且占用更少内存。

双端队列操作：栈和队列

LinkedList 实现了 Deque 接口，因此既可以用作栈，也可以用作队列。

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

PriorityQueue 概览

PriorityQueue 是一种基于堆的队列，其中最小元素（按自然顺序或比较器确定）总是最先出队。它不是由链表支持的——而是使用二叉堆数组。

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

使用自定义比较器的 PriorityQueue

传入一个 Comparator，即可反转排序顺序或按自定义字段排序：

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

选择 LinkedList 还是 ArrayList

经验法则：

在需要随机访问、迭代以及大多数场景中，请使用 ArrayList。
当您需要在两端频繁进行 O(1) 插入或删除，且不需要按索引访问时，请使用 LinkedList。
当您需要按顺序处理元素（例如任务调度、Dijkstra 算法）时，请使用 PriorityQueue。

常见问题

避免在循环中对 LinkedList 调用 get(i)——总时间复杂度为 O(n²)：

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

快速检查

无论列表大小如何，哪项 LinkedList 操作的时间复杂度都是 O(1)？

回顾：LinkedList 与双端队列

关键要点：

LinkedList 是双向链表，头部和尾部操作的时间复杂度为 O(1)
随机访问（按索引执行 get/set）的时间复杂度为 O(n)
实现了 Deque，可用作栈或队列
PriorityQueue 提供基于堆顺序的处理
大多数使用场景优先选择 ArrayList；频繁修改头部或尾部时，LinkedList 更具优势

常见问题解答

「LinkedList 内部原理」课时是免费的吗？

是的 — 「LinkedList 内部原理」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「LinkedList 内部原理」这节课中我会学到什么？

探索 LinkedList 的双向链节点结构及其时间复杂度特征你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「LinkedList 内部原理」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Java Academy