# 20260731 课堂笔记 — LinkedList 多接口形态 / Iterator 迭代器

- **日期**：2026-07-31
- **项目**：`c260731`
- **包路径**：`course`
- **作者**：WanJL

---

## 目录

1. [LinkedList 多接口形态（List / Queue / Deque）](#1-linkedlist-多接口形态list--queue--deque)
2. [Iterator 迭代器](#2-iterator-迭代器)
3. [Collection 体系回顾：Iterable → Collection](#3-collection-体系回顾iterable--collection)
4. [随堂练习要点](#4-随堂练习要点)
5. [拓展阅读](#5-拓展阅读)

---

## 1. LinkedList 多接口形态（List / Queue / Deque）

### 概念

`LinkedList` 是 Java 集合框架中功能最「全面」的实现类之一，它**同时实现了多个接口**：

- `List<E>` 接口 —— 列表（线性表），有序、可重复、带索引
- `Queue<E>` 接口 —— 队列，先进先出（FIFO）
- `Deque<E>` 接口 —— 双端队列（Double Queue），两端都可以入队 / 出队

同一个 `LinkedList` 对象，可以用不同的**接口类型**去引用。声明类型不同，「看得见」的方法就不同——这是**接口多态**（编译看左边：接口类型决定可用方法；运行看右边：真实对象是 LinkedList）。

| 声明类型 | 语义 | 可见的核心方法 |
|----------|------|----------------|
| `LinkedList<Object>` | 最全的方法集合（链表本体） | 链表 + List + Queue + Deque 全部方法 |
| `List<Object>` | 列表线性表 | `add/get/set/remove`、`indexOf`、`contains` 等 |
| `Queue<Object>` | 队列（FIFO） | `offer` 入队、`poll` 出队、`peek` 查看队头 |
| `Deque<Object>` | 双端队列 | `addFirst/addLast`、`pollFirst/pollLast`、`peekFirst/peekLast`、`push/pop`（栈） |

### 代码示例

```java
// 来源：course/Demo01.java
package course;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Demo01 {
    public static void main(String[] args) {
        // 使用最全的方法 --- 链表
        LinkedList<Object> list = new LinkedList<>();
        // 如果想使用 List 的方法 --- 列表线性表
        List<Object> list1 = new LinkedList<>();
        // 如果想使用队列 --- Queue
        Queue<Object> queue = new LinkedList<>();
        // 如果想使用双端队列 --- Double Queue
        Deque<Object> deque = new LinkedList<>();
    }
}
```

### 关键理解

1. **一个对象，多种身份**：`new LinkedList<>()` 创建的是同一个对象，但可以赋予 `List`、`Queue`、`Deque` 三种「身份」。
2. **接口作为引用类型 = 能力限定**：用 `Queue` 引用时只能调用队列方法（如 `offer/poll/peek`），无法调用 `get(int)` 这类 List 方法——把能力「收窄」到所需范围。
3. **实际应用**：需要栈/队列场景时，用 `Queue`/`Deque` 引用 `LinkedList`，语义更清晰，也方便后续替换实现类。

---

## 2. Iterator 迭代器

### 概念

由于 `Collection` 集合接口继承了 `Iterable` 接口，所以我们使用的**所有单列集合**都具备 `Iterable` 的方法（`iterator()`），并且各个实现类都重写了它。

- 通过集合对象的 `iterator()` 方法获取该集合对应的**迭代器对象**（`Iterator<E>`）
- 迭代器提供**统一的遍历方式**，与集合的内部结构（数组 / 链表）无关
- 特别适合遍历没有索引的集合（如 `Set`、`LinkedList`）

### Iterator 核心方法

| 方法 | 返回值 | 说明 |
|------|--------|------|
| `boolean hasNext()` | `boolean` | 判断迭代器是否还有下一个元素 |
| `E next()` | `E` | 返回下一个元素，并把指针向后移动一位 |
| `void remove()` | `void` | 从集合中移除上次 `next()` 返回的元素（可选操作） |

迭代器内部有一个**指针**，初始位置在第一个元素之前：

```
 [元素1] → [元素2] → [元素3] → [元素4]  …  → null
   ↑
 iterator 初始位置（第一个元素之前）
```

- `hasNext()`：判断指针后是否还有元素
- `next()`：取出当前元素并把指针后移

### 代码示例

```java
// 来源：course/Demo02.java
package course;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class Demo02 {
    /*
        由于Collection集合接口继承了Iterable接口
        所以我们使用的所有的单列集合，都具有Iterable的方法，并且重写了方法
     */
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("元素1");
        list.add("元素2");
        // ... 共添加10个元素

        // 方式一：我们遍历集合 —— for + 索引（ArrayList 有索引才支持）
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // 方式二：通过迭代器进行迭代遍历
        Iterator<String> iterator = list.iterator();   // 通过集合对象获取它对应的迭代器对象
        while (iterator.hasNext()) {                   // 判断迭代器有没有下一个元素，有就继续
            String element = iterator.next();          // 通过迭代器对象获取下一个元素
            System.out.println(element);
        }

        // 创建字符串泛型的 LinkedList 集合
        LinkedList<String> list1 = new LinkedList<>();
        // 添加10个元素 ...

        // LinkedList 同样可以使用迭代器（链表没有索引，for+get 效率低）
        Iterator<String> iterator1 = list1.iterator();
        while (iterator1.hasNext()) {
            String s = iterator1.next();
            System.out.println(s);
        }
    }
}
```

### 迭代器使用模板

```java
Iterator<E> it = 集合对象.iterator();  // 1. 获取迭代器
while (it.hasNext()) {                 // 2. 判断是否有下一个
    E e = it.next();                   // 3. 获取下一个元素并后移指针
    // 处理元素
}
```

### 注意

- **指针只能单向移动**：`next()` 只能向后，不能回退。
- `next()` 会**移动指针**，多次调用 `next()` 会跳过元素。
- 迭代过程中若集合被修改（`add/remove`），会抛出 `ConcurrentModificationException`（快速失败机制）。

---

## 3. Collection 体系回顾：Iterable → Collection

### 继承结构

```
Iterable<E>                        —— 根接口，定义了 iterator()
    │
Collection<E>                      —— 单列集合根接口（继承 Iterable）
    ├── List<E>                    —— 列表：有序、可重复、带索引
    │      ├── ArrayList<E>        —— 数组结构，随机访问快
    │      └── LinkedList<E>       —— 双链表结构，插入删除快
    ├── Queue<E>                   —— 队列：先进先出（FIFO）
    │      └── Deque<E>            —— 双端队列（LinkedList 实现）
    └── Set<E>                     —— 集合：不可重复
```

### LinkedList 与多个接口的关系

```
                 LinkedList<E>
                      │
        ┌─────────────┼─────────────┐
        ▼             ▼             ▼
      List<E>      Queue<E>      Deque<E>
      （线性表）   （队列FIFO）  （双端队列/栈）
```

所以代码中才能写出：

```java
List<Object> list1 = new LinkedList<>();
Queue<Object> queue = new LinkedList<>();
Deque<Object> deque = new LinkedList<>();
```

### 遍历集合的三种方式对比

| 方式 | 适用场景 | 示例 |
|------|----------|------|
| `for + size() + get(i)` | 有索引的 List（ArrayList 效率高） | `for (int i = 0; i < list.size(); i++)` |
| **Iterator 迭代器** | 所有单列集合（通用方式） | `while (it.hasNext()) { it.next(); }` |
| 增强 for（foreach） | 所有集合与数组（底层也是迭代器） | `for (String s : list)` |

---

## 4. 随堂练习要点

### 练习一：LinkedList 多接口引用

**核心步骤**：
1. 创建 `LinkedList<Object>` 对象
2. 分别用 `LinkedList`、`List`、`Queue`、`Deque` 四种类型引用它
3. 体会「声明类型不同 → 可见方法不同」的接口多态

**思考**：
- 用 `Queue` 引用时，能否调用 `get(int)`？—— 不能，编译错误，Queue 接口中没有该方法
- 为什么说 LinkedList 既能当队列又能当栈？—— 它实现了 Deque，Deque 提供了 `push/pop`（栈）和 `addFirst/addLast`（双端队列）

### 练习二：Iterator 迭代器遍历

**核心步骤**：
1. 创建一个 `ArrayList<String>`，添加 10 个元素
2. 用 `for + get(i)` 遍历
3. 用 `iterator()` 获取迭代器，`while (hasNext())` + `next()` 遍历
4. 再对 `LinkedList<String>` 执行同样的迭代器遍历

**思考**：
1. `hasNext()` 和 `next()` 分别做什么？—— 判断是否存在下一个元素 / 取出下一个元素并移动指针
2. 为什么 LinkedList 用 `for + get(i)` 效率低？—— 每次 `get(i)` 都要从头遍历节点，时间复杂度 O(n)，而迭代器沿链表逐个移动只需 O(1)
3. 增强 for 的底层机制是什么？—— 编译器会把 foreach 翻译成迭代器遍历

---

## 5. 拓展阅读

### 官方文档

- [Iterable 接口 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Iterable.html)
- [Iterator 迭代器 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Iterator.html)
- [LinkedList (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html)
- [Queue (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html)
- [Deque (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html)

### 推荐阅读

- 《Java 核心技术 卷 I》第 9 章 集合 —— 迭代器与 foreach 的关系
- 《Effective Java》第 3 版 第 58 条：优先使用 foreach 循环而非传统 for 循环

### 相关知识点

| 前置知识 | 当前知识 | 后续知识 |
|----------|----------|----------|
| ArrayList 底层原理（0729） | LinkedList 多接口形态（List/Queue/Deque） | ListIterator（双向迭代） |
| LinkedList 双链表理论（0730） | Iterator 迭代器 | 增强 for / forEach 方法 |
| 泛型与集合体系（0729） | Iterable → Collection 继承体系 | Set 集合与 Map 迭代 |