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

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

1. 重构单链表SLList

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

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

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：

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 关键字控制其权限：

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. 实现操作链表的方法

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

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)$ 的时间复杂度，这也是上一节课中直接裸露递归的类 IntList 所无法实现的：

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()

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

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

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

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

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

// 在尾部添加节点
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 方法获取节点值。最后本节课的完整实现代码如下：

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: []}
}