# 20260730 课堂笔记 — List.of / LinkedList / 自定义链表 / ArrayList 练习

- **日期**：2026-07-30
- **项目**：`c260730`
- **包路径**：`course` / `exericse.exericse01` / `homework0729.p4`
- **作者**：WanJL

---

## 目录

1. [List.of() 方法 — 不可变集合](#1-listof-方法--不可变集合)
2. [LinkedList 双链表理论](#2-linkedlist-双链表理论)
3. [手写自定义单链表 MyLinked](#3-手写自定义单链表-mylinked)
4. [Student 课程管理练习 (ArrayList 基本操作)](#4-student-课程管理练习-arraylist-基本操作)
5. [课后作业回顾：手写 MyArrayList](#5-课后作业回顾手写-myarraylist)
6. [随堂练习要点](#6-随堂练习要点)
7. [拓展阅读](#7-拓展阅读)

---

## 1. List.of() 方法 — 不可变集合

### 概念

`List.of()` 是 Java 9 引入的静态工厂方法，用于快速创建**不可变（Immutable）**的 List 集合。

- 返回的 List 不允许调用 `add()`、`set()`、`remove()` 等修改操作，否则抛出 `UnsupportedOperationException`
- 适用于创建常量列表、固定数据集合
- 支持任意数量参数（最多 10 个重载 + 1 个可变参数版本）
- 通过 `List.of()` 传入对象引用时，虽然 List 本身不可变，但**元素对象**仍可被修改（浅不可变）

### 代码示例

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

import java.util.List;

public class Demo01 {
    public static void main(String[] args) {
        // 快速创建不可变列表
        List<String> list = List.of("张三", "李四", "wangwu");
        // list.add("张三");       // ❌ 抛出 UnsupportedOperationException
        // list.set(1, "晚五");    // ❌ 抛出 UnsupportedOperationException

        // 遍历读取
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // 对象元素的不可变集合：list不可增删改，但元素对象本身可变
        Student s2 = new Student("张三2", 20, "S002");
        List<Student> studentList = List.of(s1, s2, s3, s4);
        s2.setName("李四"); // 对象本身可以修改
    }
}
```

### 注意

- `List.of()` 不接受 `null` 元素，会抛出 `NullPointerException`
- 类似的 `Set.of()`、`Map.of()` 也是 Java 9 新增的不可变集合工厂方法
- 创建空列表：`List.of()`（等价于 `Collections.emptyList()`）

---

## 2. LinkedList 双链表理论

### 概念

`LinkedList` 是 Java 集合框架中基于**双链表（Doubly Linked List）** 实现的 List 和 Deque。

- 同时实现了 `List` 接口（列表）和 `Deque` 接口（双端队列）
- 可用于实现：链表、队列、栈
- 与 `ArrayList` 相比：插入删除效率高（O(1)），随机访问效率低（O(n)）

### LinkedList 内部结构

```java
// 来源：Demo02.java (注释部分)
public class LinkedList<E> {
    // 属性
    transient int size = 0;                  // 集合元素个数
    transient Node<E> first;                 // 头节点
    transient Node<E> last;                  // 尾节点

    // 静态内部类 — 节点
    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;
        }
    }
}
```

### 节点的三种状态

| 节点类型 | prev | item | next |
|----------|------|------|------|
| **头节点（first）** | `null` | 有值 | 下一个节点地址 |
| **尾节点（last）** | 上一个节点地址 | 有值 | `null` |
| **普通节点** | 上一个节点地址 | 有值 | 下一个节点地址 |

### 核心方法

```java
// 获取头节点/尾节点
public E getFirst();    // 头节点为null则抛出 NoSuchElementException
public E getLast();     // 尾节点为null则抛出 NoSuchElementException
public E removeFirst(); // 移除头节点

// 移除头节点的核心逻辑（unlinkFirst）
private E unlinkFirst(Node<E> f) {
    // 1. 保存头节点的元素和下一个节点
    // 2. 清空头节点的item和next（帮助GC）
    // 3. 将原第二个节点设为新头节点
    // 4. 如果新头节点为空 → last也设为null
    // 5. 如果新头节点不为空 → 新头节点的prev设为null（符合头节点条件）
    // 6. size--, modCount++, 返回被删除的元素
}

// unlinkLast 是 unlinkFirst 的镜像操作，删除尾节点
```

---

## 3. 手写自定义单链表 MyLinked

### 概念

`MyLinked<N>` 是一个手写的简化版**单链表**，演示链表核心原理：

- 使用**泛型** `<N>` 支持任意类型
- 只保留 `next` 指针（单链表），不含 `prev` 指针
- 包含头节点（`firstNode`）和尾节点（`lastNode`）引用
- 实现了添加节点和遍历打印功能

### 代码示例

```java
// 来源：MyLinked.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 static class Node<N> {
        N value;           // 节点元素
        Node<N> next;      // 下一个节点的地址（单链表只保留next）

        public Node(N value, Node<N> next) {
            this.value = value;
            this.next = next;
        }
    }

    // 1. 添加节点（尾插法）
    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;        // 新节点成为尾节点
    }

    // 2. 遍历打印
    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;
            }
        }
    }
}
```

### 测试示例

```java
// 来源：Test01.java
public class Test01 {
    public static void main(String[] args) {
        MyLinked<String> linked = new MyLinked<>();
        linked.addNode("张三");
        linked.addNode("李四");
        linked.addNode("王五");
        linked.addNode(null);    // 支持 null 元素
        linked.print();
    }
}
```

### 与 LinkedList 的对比

| 对比项 | `LinkedList` (JDK) | `MyLinked` (手写) |
|--------|-------------------|-------------------|
| 数据结构 | 双链表 (prev + next) | 单链表 (只有 next) |
| 泛型 | `LinkedList<E>` | `MyLinked<N>` |
| 功能 | 增删改查 + 队列 + 栈 | 仅添加和遍历 |
| 头节点设计 | `first` 直接指向第一个有效节点 | `firstNode.next` 指向第一个有效节点 |

---

## 4. Student 课程管理练习 (ArrayList 基本操作)

### 概念

通过 `CourseManager` 练习 `ArrayList` 的常用方法：

- `add()` — 添加元素
- `contains()` — 判断是否包含
- `remove(Object)` — 按对象删除
- `indexOf()` — 获取索引位置

### 代码示例

```java
// 来源：CourseManager.java
package exericse.exericse01;

import java.util.ArrayList;

public class CourseManager {
    public static void main(String[] args) {
        // 1. 创建学生对象
        Student s = new Student("张三", 20, "S001");

        // 2. 添加课程
        ArrayList<String> courseList = s.getCourses();
        courseList.add("Java基础");
        courseList.add("数据结构");
        courseList.add("数据库原理");

        // 3. 输出已选课程
        System.out.println(s.getName() + "的已选课程" + courseList);
        // 输出：张三的已选课程[Java基础, 数据结构, 数据库原理]

        // 4. 判断是否包含
        System.out.println("是否已选数据结构？" + courseList.contains("数据结构"));
        // 输出：是否已选数据结构？true

        // 5. 退选课程
        System.out.println("已退选课程：" +
                (courseList.remove("数据结构") ? "数据结构" : "没找到课程"));
        // 输出：已退选课程：数据结构

        // 6. 再次输出
        System.out.println("退选后的课程：" + courseList);
        // 输出：退选后的课程：[Java基础, 数据库原理]

        // 7. 查询索引
        System.out.println("'Java基础'的索引位置：" + courseList.indexOf("Java基础"));
        // 输出：'Java基础'的索引位置：0
    }
}
```

### ArrayList 常用方法总结

| 方法 | 说明 | 时间复杂度 |
|------|------|-----------|
| `add(E e)` | 尾部添加元素 | 均摊 O(1) |
| `add(int index, E e)` | 指定位置插入 | O(n) |
| `get(int index)` | 获取元素 | O(1) |
| `set(int index, E e)` | 修改元素 | O(1) |
| `remove(int index)` | 按索引删除 | O(n) |
| `remove(Object o)` | 按对象删除 | O(n) |
| `contains(Object o)` | 是否包含 | O(n) |
| `indexOf(Object o)` | 获取首次出现索引 | O(n) |
| `size()` | 元素个数 | O(1) |
| `isEmpty()` | 是否为空 | O(1) |
| `clear()` | 清空所有元素 | O(n) |

---

## 5. 课后作业回顾：手写 MyArrayList

### 概念

手写简化版 `MyArrayList<E>`，综合运用 **泛型 + 数组操作 + 扩容机制**，加深对 ArrayList 源码的理解。

### 作业要求

| 方法 | 说明 |
|------|------|
| `MyArrayList()` | 无参构造，默认容量 10 |
| `MyArrayList(int initialCapacity)` | 指定初始容量 |
| `boolean add(E e)` | 添加元素（自动扩容） |
| `E get(int index)` | 获取元素（检查越界） |
| `E set(int index, E element)` | 修改元素 |
| `E remove(int index)` | 删除元素 |
| `int size()` | 返回元素个数 |
| `boolean isEmpty()` | 判断是否为空 |
| `void clear()` | 清空所有元素 |
| `String toString()` | 返回格式 `[元素1, 元素2, ...]` |

### 代码框架

```java
// 来源：homework0729/p4/MyArrayList.java
package homework0729.p4;

public class MyArrayList<E> {
    private Object[] elementData;  // 底层存储数组
    private Integer size;          // 实际元素个数

    // 无参构造
    public MyArrayList() {
        elementData = new Object[0];  // 待完善为默认容量10
    }

    // 指定容量构造
    public MyArrayList(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    // 添加元素（需实现自动扩容）
    public boolean add(E e) {
        if (size + 1 >= elementData.length) {
            // 扩容 — 复制
        }
        return false;
    }
}
```

### 关键设计点

1. **扩容机制**：参考 JDK 的 1.5 倍扩容（`oldCapacity + (oldCapacity >> 1)`）
2. **类型安全**：使用泛型 `<E>`，`get()` 返回时需强制转换
3. **边界检查**：`get()`、`set()`、`remove()` 需校验 `index` 是否越界
4. **缩容考虑**：`remove()` 后可考虑 `elementData[--size] = null` 帮助 GC

---

## 6. 随堂练习要点

### 练习：课程管理系统 (Exercise01)

**包路径**：`src/exericse/exericse01/`

**核心步骤**：
1. 创建 `Student` 对象（含 `ArrayList<String> courses` 属性）
2. 通过 `getCourses()` 获取课程列表并用 `add()` 添加课程
3. 使用 `contains()` 判断课程是否存在
4. 使用 `remove(Object)` 按值删除课程
5. 使用 `indexOf()` 查询课程索引

**Student 类要点**：
- `courses` 字段类型为 `ArrayList<String>`，在构造方法中初始化
- 重写了 `equals()` / `hashCode()` / `toString()` 方法

### 思考题

1. `List.of()` 返回的 List 为什么不能修改？—— 底层是 `ImmutableCollections` 内部类
2. 单链表和双链表的主要区别？—— 单向遍历 vs 双向遍历，`prev` 指针有无
3. 为什么 ArrayList 扩容是 1.5 倍而不是 2 倍？—— 平衡空间利用率和扩容频率

---

## 7. 拓展阅读

### 官方文档

- [Java 9 List.of() 文档](https://docs.oracle.com/javase/9/docs/api/java/util/List.html#of-E...-)
- [LinkedList 源码 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html)
- [ArrayList 源码 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayList.html)

### 推荐阅读

- 《Java 核心技术 卷 I》第 9 章 集合
- 《Effective Java》第 3 版 第 47 条：优先使用 Collection 而非 Stream 来返回序列

### 相关知识点

| 前置知识 | 当前知识 | 后续知识 |
|----------|----------|----------|
| ArrayList 底层原理（0729） | List.of() 不可变集合 | Collections.unmodifiableList() |
| 泛型（0729） | 自定义泛型链表 | 迭代器 Iterator |
| 数组扩容（0729） | 1.5 倍扩容公式 | 红黑树（TreeMap） |