# 2026-07-30 LinkedList 双链表专项练习（课堂练习用）

> **说明**：以下习题围绕今日授课核心内容——**LinkedList 双链表** 展开，涵盖 LinkedList 的特点与底层结构、LinkedList 作为 List 的基本操作、LinkedList 作为 Deque/Queue 的双端队列/队列操作、手写简单链表等知识点。
>
> 题目分为 **基础练习**（LinkedList 基本操作，3 题）和 **进阶挑战**（链表应用，2 题）。

---

# 第一部分：基础练习

> 以下练习围绕 LinkedList 的 List / Deque / Queue 三种角色展开，由浅入深。

---

## 练习 1：LinkedList 创建与基本操作

**难度**：⭐  
**知识点**：LinkedList 创建、add()/get()/size()/set()/remove() 方法、与 ArrayList 对比

**场景描述**：使用 LinkedList 存储一个班级的学生姓名，体验 LinkedList 作为 List 的基本操作。

**题目要求**：

在 `LinkedListDemo` 类的 `main` 方法中，完成以下操作：

```java
import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo {
    public static void main(String[] args) {
        // 1. 创建一个 LinkedList，泛型为 String，存储学生姓名
        //    提示：LinkedList<String> list = new LinkedList<>();

        // 2. 添加 5 个学生姓名："张三", "李四", "王五", "赵六", "孙七"

        // 3. 输出当前链表大小（使用 size() 方法）

        // 4. 获取并输出索引为 2 的元素（使用 get(2)）

        // 5. 将索引 1 处的"李四"修改为"李思"（使用 set() 方法）

        // 6. 删除索引为 3 的元素"赵六"（使用 remove(index) 方法）

        // 7. 使用 for 循环遍历链表，输出所有学生姓名
        //    输出格式："当前学生列表：张三, 李思, 王五, 孙七"

        // 8. 在索引 1 处插入一个新学生"周八"
        //    提示：list.add(1, "周八");

        // 9. 再次遍历输出
    }
}
```

**预期输出**：
```
链表大小：5
索引 2 的学生：王五
已修改索引 1：李四 → 李思
已删除索引 3：赵六
当前学生列表：张三, 李思, 王五, 孙七
插入后列表：张三, 周八, 李思, 王五, 孙七
```

**思考题**：
1. 上面代码中，如果换成 `ArrayList<String>` 实现，代码需要修改哪些部分？
2. `LinkedList` 的 `get(index)` 和 `ArrayList` 的 `get(index)` 在性能上有什么区别？为什么？

---

## 练习 2：LinkedList 的双端队列操作（Deque）

**难度**：⭐⭐  
**知识点**：`addFirst()` / `addLast()` / `getFirst()` / `getLast()` / `removeFirst()` / `removeLast()`

**场景描述**：LinkedList 实现了 `Deque` 接口（双端队列），可以在链表的两端高效操作元素。模拟一个"双端排队"场景——有些人从队尾排队，有些人插队到队首。

**题目要求**：

在 `DequeDemo` 类的 `main` 方法中，完成以下操作：

```java
import java.util.LinkedList;

public class DequeDemo {
    public static void main(String[] args) {
        // 1. 创建一个 LinkedList<String> 表示排队队伍

        // 2. 依次往队尾添加："张三", "李四", "王五"
        //    提示：使用 addLast() 或 offerLast()

        // 3. 查看队首和队尾的人（使用 getFirst() / getLast()）
        //    输出："队首：张三，队尾：王五"

        // 4. 一个新同学"赵六"插队到队首（使用 addFirst()）

        // 5. 输出当前队伍："当前队伍：[赵六, 张三, 李四, 王五]"

        // 6. 叫到队首的人"赵六"离开（使用 removeFirst()）
        //    输出："赵六已离开"

        // 7. 队尾的人"王五"等不及也离开了（使用 removeLast()）
        //    输出："王五已离开"

        // 8. 输出最终队伍："最终队伍：[张三, 李四]"

        // 9. 尝试获取空链表时的队首（创建一个新空链表，调用 getFirst()）
        //    观察程序发生了什么？（提示：NoSuchElementException）
    }
}
```

**预期输出**：
```
队首：张三，队尾：王五
当前队伍：[赵六, 张三, 李四, 王五]
赵六已离开
王五已离开
最终队伍：[张三, 李四]
```

**异常观察**：
```
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.LinkedList.getFirst(LinkedList.java:250)
```

**提示**：
- `addFirst(e)` 等价于 `offerFirst(e)` — 在双端队列头部插入
- `addLast(e)` 等价于 `offerLast(e)` — 在双端队列尾部插入
- `getFirst()` 获取头部元素，队列为空则抛 `NoSuchElementException`
- `getLast()` 获取尾部元素，队列为空则抛 `NoSuchElementException`

**思考题**：
1. `getFirst()` 与 `peekFirst()` 有什么区别？（提示：空队列时行为不同）
2. LinkedList 的双端队列操作的时间复杂度是多少？为什么？

---

## 练习 3：LinkedList 的队列操作（Queue）

**难度**：⭐⭐  
**知识点**：`offer()` / `poll()` / `peek()`、FIFO（先进先出）队列特性

**场景描述**：LinkedList 实现了 `Queue` 接口，可以用作**队列（FIFO）**。模拟银行叫号系统——客户先到先服务。

**题目要求**：

在 `QueueDemo` 类的 `main` 方法中，完成以下操作：

```java
import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        // 1. 创建一个 Queue<String>，使用 LinkedList 实现
        //    提示：Queue<String> queue = new LinkedList<>();

        // 2. 三个客户依次取号排队：
        //    "客户A" → offer() 入队
        //    "客户B" → offer() 入队
        //    "客户C" → offer() 入队

        // 3. 查看当前排队人数（size()）

        // 4. 查看队首是谁但不离开队列（peek()）
        //    输出："当前排队人数：3，队首：客户A"

        // 5. 叫号服务：队首"客户A"出队（poll()）
        //    输出："请客户A前往1号窗口"

        // 6. 新客户"客户D"取号排队

        // 7. 再次叫号：队首"客户B"出队
        //    输出："请客户B前往1号窗口"

        // 8. 输出剩余排队客户
        //    输出："剩余排队客户：[客户C, 客户D]"

        // 9. 演示 poll() 与 peek() 的空队列安全行为：
        //    创建一个空队列，调用 poll() 和 peek()
        //    观察它们返回什么，而不是抛异常
    }
}
```

**预期输出**：
```
当前排队人数：3，队首：客户A
请客户A前往1号窗口
请客户B前往1号窗口
剩余排队客户：[客户C, 客户D]
空队列 poll() 返回：null
空队列 peek() 返回：null
```

**Queue 方法对比**：

| 操作 | 抛出异常 | 返回特殊值 |
|------|----------|-----------|
| 插入 | `add(e)` | `offer(e)` |
| 移除 | `remove()` | `poll()` |
| 查看 | `element()` | `peek()` |

**思考题**：
1. `poll()` 和 `remove()` 在空队列时行为有什么不同？
2. 队列的 FIFO 特性和栈的 LIFO 特性在实际开发中分别适用于什么场景？

---

# 第二部分：进阶挑战

> 以下练习综合运用 LinkedList、链表数据结构、手写链表等知识。

---

## 进阶 1：LinkedList 与 ArrayList 性能对比实验

**难度**：⭐⭐⭐  
**知识点**：LinkedList vs ArrayList 性能差异、时间复杂度、`add(index)` 头部插入、`get(index)` 随机访问

**场景描述**：通过实验数据直观对比 LinkedList 和 ArrayList 在不同操作上的性能差异，加深对双链表和数组两种数据结构的理解。

**题目要求**：

编写 `PerformanceCompare` 类，完成以下对比实验：

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PerformanceCompare {
    public static void main(String[] args) {
        int dataSize = 100000;  // 数据量

        // === 实验 1：尾部添加性能对比 ===
        // 分别用 ArrayList 和 LinkedList 添加 dataSize 个元素，
        // 记录并比较耗时（使用 System.currentTimeMillis()）

        // === 实验 2：头部插入性能对比 ===
        // 分别在 ArrayList 和 LinkedList 的索引 0 位置插入 10000 个元素
        // 记录并比较耗时
        // 提示：list.add(0, element)

        // === 实验 3：随机访问性能对比 ===
        // 分别在 ArrayList 和 LinkedList 中执行 100000 次 get(index) 随机访问
        // 记录并比较耗时
        // 提示：list.get(randomIndex)

        // === 实验 4：遍历性能对比 ===
        // 分别用 for 循环 + get(index) 遍历 ArrayList 和 LinkedList
        // 记录并比较耗时
        // 思考：LinkedList 用 for+get 遍历为什么慢？
    }

    // 辅助方法：计算并输出耗时
    public static void printElapsed(String label, long start, long end) {
        System.out.println(label + ": " + (end - start) + " ms");
    }
}
```

**预期输出示例**（实际数值因机器而异）：
```
========== LinkedList vs ArrayList 性能对比 ==========
数据量：100000
--- 实验 1：尾部添加 ---
ArrayList 尾部添加：15 ms
LinkedList 尾部添加：18 ms

--- 实验 2：头部插入（10000 次） ---
ArrayList 头部插入：892 ms
LinkedList 头部插入：5 ms

--- 实验 3：随机访问（100000 次） ---
ArrayList 随机访问：3 ms
LinkedList 随机访问：9786 ms

--- 实验 4：for+get 遍历 ---
ArrayList 遍历：4 ms
LinkedList 遍历：84321 ms
```

**分析题（笔试面试高频）**：
1. 为什么 LinkedList 头部插入比 ArrayList 快得多？
   - 答：LinkedList 头部插入只需修改节点的 `prev` / `next` 指针（O(1)），而 ArrayList 头部插入需要将后续所有元素向后移动（O(n)）
2. 为什么 LinkedList 的随机访问比 ArrayList 慢得多？
   - 答：ArrayList 底层是数组，支持通过索引直接寻址（O(1)）；LinkedList 需要从头节点开始逐个遍历找到目标索引（O(n)）
3. 为什么 LinkedList 用 `for + get(i)` 遍历非常慢？
   - 答：每次 `get(i)` 都从头部开始遍历到第 i 个节点，总时间复杂度为 O(n²)
4. **如何正确遍历 LinkedList？**
   - 提示：使用 **foreach** 或 **迭代器（Iterator）**，让链表沿着 `next` 指针逐个访问，时间复杂度 O(n)

---

## 进阶 2：手写单链表 —— 完善 MyLinked 类

**难度**：⭐⭐⭐⭐  
**知识点**：链表数据结构、泛型、节点操作、链表增删改查

**场景描述**：课堂示例 `MyLinked` 类只实现了添加和遍历两个方法。请基于已有的单链表框架，补全缺失的方法，并编写测试类验证。

**题目要求**：

完善 `MyLinked.java` 中的以下方法：

```java
package course;

public class MyLinked<N> {
    private Integer size;
    private Node<N> firstNode;  // 头节点（哨兵节点，不存有效数据）
    private Node<N> lastNode;   // 尾节点

    public MyLinked() {
        firstNode = new Node<>(null, null);
        lastNode = firstNode;
    }

    public int size() {
        return this.size;
    }

    // ========== 已有方法 ==========

    // 添加节点（尾插法）
    public void addNode(N value) {
        Node<N> n = new Node<>(value, null);
        if (firstNode.next == null) {
            this.firstNode.next = n;
            this.lastNode = n;
        }
        lastNode.next = n;
        lastNode = n;
    }

    // 遍历打印
    public void print() {
        Node<N> node = firstNode.next;
        while (true) {
            System.out.println(node.value);
            node = node.next;
            if (node.next == null) {
                System.out.println(node.value);
                break;
            }
        }
    }

    // ========== 待完善方法（请补全代码） ==========

    /**
     * 获取指定索引位置的节点值
     * @param index 索引（从 0 开始）
     * @return 节点值
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public N get(int index) {
        // TODO: 检查索引是否越界（index < 0 || index >= size）
        //       从头节点开始遍历到第 index 个节点
        //       返回该节点的 value
        //       提示：Node<N> node = firstNode.next; 然后循环 index 次
    }

    /**
     * 删除指定索引位置的节点
     * @param index 索引（从 0 开始）
     * @return 被删除的节点值
     * @throws IndexOutOfBoundsException 如果索引越界
     */
    public N remove(int index) {
        // TODO: 检查索引越界
        //       找到要删除节点的前一个节点（prevNode）
        //       让 prevNode.next = 要删除节点的下一个节点
        //       如果删除的是尾节点，更新 lastNode
        //       size--
        //       返回被删除节点的 value
    }

    /**
     * 判断链表是否包含某个值
     * @param value 要查找的值
     * @return true 如果存在
     */
    public boolean contains(N value) {
        // TODO: 从头节点开始遍历
        //       如果 value == null，用 node.value == null 判断
        //       否则用 value.equals(node.value) 判断
        //       找到返回 true，遍历完没找到返回 false
    }

    /**
     * 将链表转换为数组（方便 toString 等操作）
     * @return 包含所有节点值的数组
     */
    @SuppressWarnings("unchecked")
    public N[] toArray() {
        // TODO: 创建一个泛型数组 (N[]) new Object[size];
        //       遍历链表，将每个节点的 value 放入数组
        //       返回数组
    }

    /**
     * 清空链表
     */
    public void clear() {
        // TODO: 将 firstNode.next 设为 null
        //       lastNode 指向 firstNode
        //       size = 0
        //       提示：链表中的节点对象会被 GC 自动回收
    }
}
```

**测试类要求**：

编写 `MyLinkedTest` 类，测试所有完善后的方法：

```java
package course;

public class MyLinkedTest {
    public static void main(String[] args) {
        MyLinked<String> linked = new MyLinked<>();

        // 1. 添加测试
        linked.addNode("A");
        linked.addNode("B");
        linked.addNode("C");
        linked.addNode("D");
        System.out.println("链表大小：" + linked.size());  // 4

        // 2. 获取测试
        System.out.println("索引 0：" + linked.get(0));  // A
        System.out.println("索引 2：" + linked.get(2));  // C

        // 3. 包含测试
        System.out.println("包含 A？" + linked.contains("A"));  // true
        System.out.println("包含 E？" + linked.contains("E"));  // false

        // 4. 删除测试
        String removed = linked.remove(1);
        System.out.println("已删除索引 1：" + removed);  // B
        System.out.println("删除后大小：" + linked.size());  // 3

        // 5. 遍历测试
        System.out.print("当前链表：");
        linked.print();  // A C D

        // 6. 清空测试
        linked.clear();
        System.out.println("清空后大小：" + linked.size());  // 0
    }
}
```

**预期输出**：
```
链表大小：4
索引 0：A
索引 2：C
包含 A？true
包含 E？false
已删除索引 1：B
删除后大小：3
当前链表：A C D
清空后大小：0
```

**提示**：
1. `get(index)` 方法的边界检查：`index < 0 || index >= size` 时抛 `IndexOutOfBoundsException`
2. `remove(index)` 需要找到**前一个节点**（prevNode），然后执行 `prevNode.next = nodeToRemove.next`
3. `contains()` 需要考虑 `null` 值的处理（`value == null` 时用 `==` 判断）
4. `toArray()` 由于泛型擦除，需要强制转换 `(N[]) new Object[size]`
5. `clear()` 只需断开头节点引用，JVM 会自动回收其他节点

**附加思考题**：
1. 为什么 `remove(0)` 删除头节点时需要特殊处理？代码中如何体现？
2. 如果链表中有重复值，`contains()` 返回第一个找到的，如何实现返回所有匹配的索引？
3. 手写单链表的 `get(index)` 和 JDK LinkedList 的 `get(index)` 实现思路有什么不同？
   - 提示：JDK 的双链表可以从头或尾双向搜索（`node(index)` 方法中 `index < (size >> 1)` 时从头找，否则从尾找）

---

# 参考答案要点

## 练习 1 参考

```java
LinkedList<String> list = new LinkedList<>();

list.add("张三");
list.add("李四");
list.add("王五");
list.add("赵六");
list.add("孙七");

System.out.println("链表大小：" + list.size());
System.out.println("索引 2 的学生：" + list.get(2));

list.set(1, "李思");
System.out.println("已修改索引 1：李四 → 李思");

String removed = list.remove(3);
System.out.println("已删除索引 3：" + removed);

System.out.print("当前学生列表：");
for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i));
    if (i < list.size() - 1) System.out.print(", ");
}
System.out.println();

list.add(1, "周八");
System.out.println("插入后列表：" + list);
```

## 练习 2 参考

```java
LinkedList<String> deque = new LinkedList<>();

deque.addLast("张三");
deque.addLast("李四");
deque.addLast("王五");

System.out.println("队首：" + deque.getFirst()
    + "，队尾：" + deque.getLast());

deque.addFirst("赵六");
System.out.println("当前队伍：" + deque);

System.out.println(deque.removeFirst() + "已离开");
System.out.println(deque.removeLast() + "已离开");
System.out.println("最终队伍：" + deque);

// 空队列异常演示
LinkedList<String> empty = new LinkedList<>();
try {
    empty.getFirst();  // 抛出 NoSuchElementException
} catch (Exception e) {
    System.out.println("空队列调用 getFirst()：" + e);
}
```

## 练习 3 参考

```java
Queue<String> queue = new LinkedList<>();

queue.offer("客户A");
queue.offer("客户B");
queue.offer("客户C");

System.out.println("当前排队人数：" + queue.size()
    + "，队首：" + queue.peek());

System.out.println("请" + queue.poll() + "前往1号窗口");
queue.offer("客户D");
System.out.println("请" + queue.poll() + "前往1号窗口");
System.out.println("剩余排队客户：" + queue);

// 空队列安全行为
Queue<String> emptyQueue = new LinkedList<>();
System.out.println("空队列 poll() 返回：" + emptyQueue.poll());
System.out.println("空队列 peek() 返回：" + emptyQueue.peek());
```

## 进阶 1 参考（核心代码）

```java
// 头部插入实验
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

// 先预填充数据
for (int i = 0; i < dataSize; i++) {
    arrayList.add("元素" + i);
    linkedList.add("元素" + i);
}

// ArrayList 头部插入
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    arrayList.add(0, "新元素");
}
long end = System.currentTimeMillis();
printElapsed("ArrayList 头部插入", start, end);

// LinkedList 头部插入
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    linkedList.add(0, "新元素");
}
end = System.currentTimeMillis();
printElapsed("LinkedList 头部插入", start, end);

// 正确遍历 LinkedList 的方式：用 Iterator 或 foreach
start = System.currentTimeMillis();
for (String s : linkedList) {
    // 只遍历，不做其他操作
}
end = System.currentTimeMillis();
printElapsed("LinkedList foreach 遍历", start, end);
```

## 进阶 2 参考（get / remove / contains 方法）

```java
public N get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("索引越界: " + index);
    }
    Node<N> node = firstNode.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node.value;
}

public N remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("索引越界: " + index);
    }
    Node<N> prev = firstNode;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }
    Node<N> target = prev.next;
    prev.next = target.next;
    if (target == lastNode) {
        lastNode = prev;
    }
    size--;
    return target.value;
}

public boolean contains(N value) {
    Node<N> node = firstNode.next;
    while (node != null) {
        if (value == null ? node.value == null : value.equals(node.value)) {
            return true;
        }
        node = node.next;
    }
    return false;
}
```

---

# 涵盖知识点总览

| 知识点 | 对应练习 | 说明 |
|--------|---------|------|
| LinkedList 创建与 List 操作 | 练习 1 | `add()` / `get()` / `set()` / `remove(index)` / `size()` |
| LinkedList 双端队列操作 | 练习 2 | `addFirst()` / `addLast()` / `getFirst()` / `getLast()` / `removeFirst()` / `removeLast()` |
| LinkedList 队列操作 | 练习 3 | `offer()` / `poll()` / `peek()`、FIFO 特性 |
| LinkedList vs ArrayList 性能对比 | 进阶 1 | 头部插入 O(1) vs O(n)、随机访问 O(n) vs O(1)、遍历方式 |
| 手写单链表增删改查 | 进阶 2 | 泛型、Node 节点、`get(index)`、`remove(index)`、`contains()`、`clear()` |
| 链表节点结构 | 进阶 2 | 单链表 Node（value + next）vs 双链表 Node（item + next + prev） |
| 链表遍历的正确方式 | 进阶 1、2 | foreach / Iterator 方式 O(n) vs for+get 方式 O(n²) |
| 空集合操作的异常处理 | 练习 2、3 | `getFirst()` 抛异常 vs `peek()` 返回 null |