【UCB CS 61B SP24】Lecture 4 - Lists 2: SLLists学习笔记

embedded/2025/2/25 4:17:36/

本文内容为重写上一节课中的单链表，将其重构成更易于用户使用的链表，实现多种操作链表的方法。

1. 重构单链表SLList

在上一节课中编写的 IntList 类是裸露递归的形式，在 Java 中一般不会这么定义，因为这样用户可能需要非常了解引用，并且能够递归地思考，才能使用这个类。

因此我们需要实现一个更容易使用的单链表（Singly Linked List），首先我们定义节点类 IntNode：

java">package CS61B.Lecture4;public class IntNode {public int val;public IntNode next;public IntNode(int val, IntNode next) {this.val = val;this.next = next;}
}

现在就可以创建单链表类 SLList：

java">package CS61B.Lecture4;public class SLList {private IntNode head;public SLList(int val) {this.head = new IntNode(val, null);}public static void main(String[] args) {SLList L = new SLList(5);}
}

之前用户使用单链表需要这样定义：IntList L = new IntList(5, null);，他需要有递归考虑的思想，必须指定所指向的下一个链表的空值。

由于 IntNode 类只有在 SLList 类中使用才有意义，且用户一般不会单独去使用 IntNode 类，因此可以将其作为嵌套类放入 SLList 中，并且可以使用 private 关键字控制其权限：

java">package CS61B.Lecture4;public class SLList {private static class IntNode {public int val;public IntNode next;public IntNode(int val, IntNode next) {this.val = val;this.next = next;}}private IntNode head;public SLList(int val) {this.head = new IntNode(val, null);}public static void main(String[] args) {SLList L = new SLList(5);}
}

注意到我们还将 IntNode 类定义为静态的，静态嵌套类与外部类的实例无关，它更像是一个独立的类，但逻辑上仍然属于外部类的范畴，静态嵌套类可以直接访问外部类的静态字段和方法，但不能直接访问外部类的实例字段和方法（除非通过外部类的实例），因此静态嵌套类通常用于逻辑上与外部类相关，但不需要依赖外部类实例的场景。

2. 实现操作链表的方法

现在我们实现操作链表的几种方法：

java">package CS61B.Lecture4;public class SLList {private static class IntNode {public int val;public IntNode next;public IntNode(int val, IntNode next) {this.val = val;this.next = next;}}private IntNode head;public SLList(int val) {this.head = new IntNode(val, null);}// 获取首部节点值public int getFirst() {return this.head.val;}// 在首部添加节点public void addFirst(int val) {this.head = new IntNode(val, this.head);}// 删除首部节点并返回其值public int removeFirst() {if (this.head == null) {System.out.println("Already Empty!");return 0;}int val = this.head.val;this.head = this.head.next;return val;}// 获取尾部节点值public int getLast() {IntNode p = this.head;while (p.next != null) p = p.next;return p.val;}// 在尾部添加节点public void addLast(int val) {IntNode p = this.head;while (p.next != null) p = p.next;p.next = new IntNode(val, null);}// 删除尾部节点并返回其值public int removeLast() {if (this.head == null) {System.out.println("Already Empty!");return 0;}int val;if (this.head.next == null) {val = this.head.val;this.head = null;} else {IntNode p = this.head;while (p.next.next != null) p = p.next;val = p.next.val;p.next = null;}return val;}// 获取链表长度public int size() {return this.size(this.head);  // 无法在该方法中直接实现递归，需要一个额外的辅助方法}// size()递归辅助方法private int size(IntNode p) {if (p.next == null) return 1;return 1 + size(p.next);}// 重写输出SLList对象的信息@Overridepublic String toString() {if (this.head == null) return "[]";StringBuilder res = new StringBuilder("SLList: [");IntNode p = this.head;while (p != null) {res.append(p.val);if (p.next != null) res.append(", ");else res.append("]");p = p.next;}return res.toString();}public static void main(String[] args) {SLList L = new SLList(5);L.addFirst(10);System.out.println(L.getFirst());  // 10L.addLast(15);System.out.println(L.getLast());  // 15System.out.println(L.size());  // 3System.out.println(L);  // SLList: [10, 5, 15]System.out.println(L.removeFirst());  // 10System.out.println(L.removeLast());  // 15System.out.println(L.size());  // 1System.out.println(L);  // SLList: [5]}
}

需要重点思考的是如何用递归的方式求解链表的长度，我们使用的是构造一个辅助方法 size(IntNode p) 使得用户可以通过 size() 方法直接获取链表长度。

3. 优化效率

我们现在关注 size() 方法，发现每次用户需要查看链表长度时都需要遍历一次链表，因此我们可以用一个变量实时记录链表的长度，也就是用空间换时间，这样每次查询只需要 O ( 1 ) O(1) O(1) 的时间复杂度，这也是上一节课中直接裸露递归的类 IntList 所无法实现的：

java">package CS61B.Lecture4;public class SLList {private static class IntNode {public int val;public IntNode next;public IntNode(int val, IntNode next) {this.val = val;this.next = next;}}private IntNode head;private int size;public SLList(int val) {this.head = new IntNode(val, null);this.size = 1;}// 获取首部节点值public int getFirst() {return this.head.val;}// 在首部添加节点public void addFirst(int val) {this.head = new IntNode(val, this.head);this.size++;}// 删除首部节点并返回其值public int removeFirst() {if (this.head == null) {System.out.println("Already Empty!");return 0;}int val = this.head.val;this.head = this.head.next;this.size--;return val;}// 获取尾部节点值public int getLast() {IntNode p = this.head;while (p.next != null) p = p.next;return p.val;}// 在尾部添加节点public void addLast(int val) {IntNode p = this.head;while (p.next != null) p = p.next;p.next = new IntNode(val, null);this.size++;}// 删除尾部节点并返回其值public int removeLast() {if (this.head == null) {System.out.println("Already Empty!");return 0;}int val;if (this.head.next == null) {val = this.head.val;this.head = null;} else {IntNode p = this.head;while (p.next.next != null) p = p.next;val = p.next.val;p.next = null;}this.size--;return val;}// 获取链表长度public int size() {return this.size;}// 重写输出SLList对象的信息@Overridepublic String toString() {if (this.head == null) return "[]";StringBuilder res = new StringBuilder("SLList: [");IntNode p = this.head;while (p != null) {res.append(p.val);if (p.next != null) res.append(", ");else res.append("]");p = p.next;}return res.toString();}public static void main(String[] args) {SLList L = new SLList(5);L.addFirst(10);System.out.println(L.getFirst());  // 10L.addLast(15);System.out.println(L.getLast());  // 15System.out.println(L.size());  // 3System.out.println(L);  // SLList: [10, 5, 15]System.out.println(L.removeFirst());  // 10System.out.println(L.removeLast());  // 15System.out.println(L.size());  // 1System.out.println(L);  // SLList: [5]}
}

4. 修复addLast()

首先我们写一个无参的构造方法，这样用户能够创建一个空链表：

java">public SLList() {this.head = null;this.size = 0;
}

现在我们尝试创建空链表，并用 addLast() 方法添加节点：

java">SLList L = new SLList();
L.addLast(10);
System.out.println(L);

会发现程序报错了，因为空链表的 this.head 就为 null，在执行 while (p.next != null) 时无法获取 p.next，因此我们可以这样修改 addLast() 方法：

java">// 在尾部添加节点
public void addLast(int val) {if (this.head == null) this.head = new IntNode(val, null);else {IntNode p = this.head;while (p.next != null) p = p.next;p.next = new IntNode(val, null);}this.size++;
}

5. 虚拟头节点

现在观察代码会发现有些方法里做了形如 if (this.head == null) 的特判，当工程代码量变大时如果习惯这么写会导致代码冗余复杂。

我们可以添加一个虚拟头节点，这样就不会存在头节点为空的情况，这种虚拟头节点也称哨兵节点，并且修改 remove 方法使其不返回节点值，因为可以通过 get 方法获取节点值。最后本节课的完整实现代码如下：

java">package CS61B.Lecture4;public class SLList {private static class IntNode {public int val;public IntNode next;public IntNode(int val, IntNode next) {this.val = val;this.next = next;}}private IntNode sentinel;  // 第一个节点在sentinel.next上private int size;public SLList() {this.sentinel = new IntNode(0, null);this.size = 0;}public SLList(int val) {this.sentinel = new IntNode(0, new IntNode(val, null));this.size = 1;}// 获取首部节点值public int getFirst() {IntNode p = this.sentinel;if (p.next != null) p = p.next;return p.val;}// 在首部添加节点public void addFirst(int val) {this.sentinel.next = new IntNode(val, this.sentinel.next);this.size++;}// 删除首部节点public void removeFirst() {if (this.sentinel.next == null) return;this.sentinel.next = this.sentinel.next.next;this.size--;}// 获取尾部节点值public int getLast() {IntNode p = this.sentinel;while (p.next != null) p = p.next;return p.val;}// 在尾部添加节点public void addLast(int val) {IntNode p = this.sentinel;while (p.next != null) p = p.next;p.next = new IntNode(val, null);this.size++;}// 删除尾部节点public void removeLast() {if (this.sentinel.next == null) return;IntNode p = this.sentinel;while (p.next.next != null) p = p.next;p.next = null;this.size--;}// 获取链表长度public int size() {return this.size;}// 重写输出SLList对象的信息@Overridepublic String toString() {StringBuilder res = new StringBuilder("SLList: [");IntNode p = this.sentinel;while (p.next != null) {res.append(p.next.val);p = p.next;if (p.next != null) res.append(", ");}res.append("]");return res.toString();}public static void main(String[] args) {SLList L = new SLList();System.out.println(L.size());  // 0System.out.println(L);  // SLList: []L.addLast(15);System.out.println(L.getLast());  // 15L.addFirst(10);System.out.println(L.getFirst());  // 10System.out.println(L.size());  // 2System.out.println(L);  // SLList: [10, 15]L.removeLast();L.removeFirst();L.removeLast();L.removeFirst();System.out.println(L.size());  // 0System.out.println(L);  // SLList: []}
}

http://www.ppmy.cn/embedded/164959.html

相关文章

小智机器人CMakeLists编译文件解析

小智机器人CMakeLists编译文件解析

编译完成后，成功烧录！ 这段代码是一个CMake脚本，用于配置和构建一个嵌入式项目，特别是针对ESP32系列芯片的项目。CMake是一个跨平台的构建系统，用于管理项目的编译过程。 set(SOURCES "audio_codecs/audio_code…
阅读更多...
基于MFC实现的键盘电子乐器演奏程序

基于MFC实现的键盘电子乐器演奏程序

基于MFC实现的键盘电子乐器演奏程序设计 1.项目简介 需要连接西电微机原理实验室提供的 QTH9054 微机试验箱，使用其蜂鸣器发声，若不连接，程序会直接播放 mp3 文件模拟钢琴声。 请在 release 处下载编译好的 exe 文件运行，如需计…
阅读更多...
go 接口interface func (m Market) getName() string {

go 接口interface func (m Market) getName() string {

跟Java不同点： 1. struct 实现 interface，并没有明显的实现写法，各写各的 2. struct 可以实现部分interface的方法，而不必要全部实现。直接用没问题，用interface进行引用就报错： 示例代码： /…
阅读更多...
在CentOS安装Docker

在CentOS安装Docker

在 CentOS 系统上部署 Docker 可以按照以下步骤进行： 1.系统要求 确保你的 CentOS 系统版本是 CentOS 7 及以上版本。系统内核版本不低于 3.10，可使用以下命令查看内核版本： uname -r2.卸载旧版本（可选） 如果系统中…
阅读更多...
Ollama 模型交互

Ollama 模型交互

Ollama 提供了多种方式与模型进行交互&#xff0c;其中最常见的就是通过命令行进行推理操作。 1. 命令行交互 通过命令行直接与模型进行交互是最简单的方式。 运行模型 使用 ollama run 命令启动模型并进入交互模式&#xff1a; ollama run <model-name> 例如下载 …
阅读更多...
Ubuntu编译ZLMediaKit

Ubuntu编译ZLMediaKit

下载 git clone https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit git submodule update --init安装工具 sudo apt install -y build-essential sudo apt install -y gcc g sudo apt install -y cmakesudo apt install -y build-essential cmake git libssl-dev libsdl1.…
阅读更多...
蓝桥杯——lcd显示

蓝桥杯——lcd显示

一&#xff1a;复制文件 从官方参考文件中复制相关文件&#xff0c;Src中的lcd.c&#xff0c;Inc中的lcd.h&#xff0c;fonts.h复制到自己创建的文件中 二&#xff1a;lcd初始化 在lcd.h中找到四个初始化函数&#xff0c;将其写到main文件中 三&#xff1a;写lcd显示函数 在…
阅读更多...
go～为什么会有json.Number这种类型存在

go～为什么会有json.Number这种类型存在

解决 JSON 数值类型的不确定性 在 JSON 格式里&#xff0c;数值类型没有明确区分整数和浮点数&#xff0c;一个数值可能是整数&#xff08;如 123&#xff09;&#xff0c;也可能是浮点数&#xff08;如 123.45&#xff09;。而在 Go 语言中&#xff0c;整数&#xff08;如 in…
阅读更多...
最新文章

Copyright @ 2022~2023