【UCBCS61BSP24】Lecture4-Lists2: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对象的信息 @Override public 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()); // 10 L.addLast(15); System.out.println(L.getLast()); // 15 System.out.println(L.size()); // 3 System.out.println(L); // SLList: [10, 5, 15] System.out.println(L.removeFirst()); // 10 System.out.println(L.removeLast()); // 15 System.out.println(L.size()); // 1 System.out.println(L); // SLList: [5] } }

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

3. 优化效率

我们现在关注 size() 方法，发现每次用户需要查看链表长度时都需要遍历一次链表，因此我们可以用一个变量实时记录链表的长度，也就是用空间换时间，这样每次查询只需要 O ( 1 ) O(1) 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对象的信息 @Override public 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()); // 10 L.addLast(15); System.out.println(L.getLast()); // 15 System.out.println(L.size()); // 3 System.out.println(L); // SLList: [10, 5, 15] System.out.println(L.removeFirst()); // 10 System.out.println(L.removeLast()); // 15 System.out.println(L.size()); // 1 System.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对象的信息 @Override public 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()); // 0 System.out.println(L); // SLList: [] L.addLast(15); System.out.println(L.getLast()); // 15 L.addFirst(10); System.out.println(L.getFirst()); // 10 System.out.println(L.size()); // 2 System.out.println(L); // SLList: [10, 15] L.removeLast(); L.removeFirst(); L.removeLast(); L.removeFirst(); System.out.println(L.size()); // 0 System.out.println(L); // SLList: [] } }