20260730-笔记.md 13 KB
20260730 课堂笔记 — List.of / LinkedList / 自定义链表 / ArrayList 练习
- 日期：2026-07-30
- 项目：
c260730 - 包路径：
course/exericse.exericse01/homework0729.p4 - 作者：WanJL
目录
- List.of() 方法 — 不可变集合
- LinkedList 双链表理论
- 手写自定义单链表 MyLinked
- Student 课程管理练习 (ArrayList 基本操作)
- 课后作业回顾：手写 MyArrayList
- 随堂练习要点
- 拓展阅读
1. List.of() 方法 — 不可变集合
概念
List.of() 是 Java 9 引入的静态工厂方法，用于快速创建不可变（Immutable）的 List 集合。
- 返回的 List 不允许调用
add()、set()、remove()等修改操作，否则抛出UnsupportedOperationException - 适用于创建常量列表、固定数据集合
- 支持任意数量参数（最多 10 个重载 + 1 个可变参数版本）
- 通过
List.of()传入对象引用时，虽然 List 本身不可变，但元素对象仍可被修改（浅不可变）
代码示例
// 来源：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 内部结构
// 来源：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 |
| 普通节点 | 上一个节点地址 | 有值 | 下一个节点地址 |
核心方法
// 获取头节点/尾节点
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）引用 - 实现了添加节点和遍历打印功能
代码示例
// 来源：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;
}
}
}
}
测试示例
// 来源：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()— 获取索引位置
代码示例
// 来源：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, ...] |
代码框架
// 来源：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;
}
}
关键设计点
- 扩容机制：参考 JDK 的 1.5 倍扩容（
oldCapacity + (oldCapacity >> 1)） - 类型安全：使用泛型
<E>，get()返回时需强制转换 - 边界检查：
get()、set()、remove()需校验index是否越界 - 缩容考虑：
remove()后可考虑elementData[--size] = null帮助 GC
6. 随堂练习要点
练习：课程管理系统 (Exercise01)
包路径：src/exericse/exericse01/
核心步骤：
- 创建
Student对象（含ArrayList<String> courses属性） - 通过
getCourses()获取课程列表并用add()添加课程 - 使用
contains()判断课程是否存在 - 使用
remove(Object)按值删除课程 - 使用
indexOf()查询课程索引
Student 类要点：
courses字段类型为ArrayList<String>，在构造方法中初始化- 重写了
equals()/hashCode()/toString()方法
思考题
List.of()返回的 List 为什么不能修改？—— 底层是ImmutableCollections内部类- 单链表和双链表的主要区别？—— 单向遍历 vs 双向遍历，
prev指针有无 - 为什么 ArrayList 扩容是 1.5 倍而不是 2 倍？—— 平衡空间利用率和扩容频率
7. 拓展阅读
官方文档
推荐阅读
- 《Java 核心技术 卷 I》第 9 章 集合
- 《Effective Java》第 3 版 第 47 条：优先使用 Collection 而非 Stream 来返回序列
相关知识点
| 前置知识 | 当前知识 | 后续知识 |
|---|---|---|
| ArrayList 底层原理（0729） | List.of() 不可变集合 | Collections.unmodifiableList() |
| 泛型（0729） | 自定义泛型链表 | 迭代器 Iterator |
| 数组扩容（0729） | 1.5 倍扩容公式 | 红黑树（TreeMap） |