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

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

在上一节课中编写的 IntList 类是裸露递归的形式，在 Java 中一样平常不会这么定义，因为如许用户大概必要非常了解引用，而且可以大概递归地思考，才能利用这个类。
因此我们必要实现一个更容易利用的单链表（Singly Linked List），首先我们定义节点类 IntNode：

1. package CS61B.Lecture4;
3. public class IntNode {
4.     public int val;
5.     public IntNode next;
7.     public IntNode(int val, IntNode next) {
8.         this.val = val;
9.         this.next = next;
10.     }
11. }

复制代码

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

1. package CS61B.Lecture4;
3. public class SLList {
4.     private IntNode head;
6.     public SLList(int val) {
7.         this.head = new IntNode(val, null);
8.     }
10.     public static void main(String[] args) {
11.         SLList L = new SLList(5);
12.     }
13. }

复制代码

之前用户利用单链表必要如许定义：IntList L = new IntList(5, null);，他必要有递归考虑的思想，必须指定所指向的下一个链表的空值。
由于 IntNode 类只有在 SLList 类中利用才有意义，且用户一样平常不会单独去利用 IntNode 类，因此可以将其作为嵌套类放入 SLList 中，而且可以利用 private 关键字控制其权限：

1. package CS61B.Lecture4;
3. public class SLList {
4.     private static class IntNode {
5.         public int val;
6.         public IntNode next;
8.         public IntNode(int val, IntNode next) {
9.             this.val = val;
10.             this.next = next;
11.         }
12.     }
14.     private IntNode head;
16.     public SLList(int val) {
17.         this.head = new IntNode(val, null);
18.     }
20.     public static void main(String[] args) {
21.         SLList L = new SLList(5);
22.     }
23. }

复制代码

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

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

1. package CS61B.Lecture4;
3. public class SLList {
4.     private static class IntNode {
5.         public int val;
6.         public IntNode next;
8.         public IntNode(int val, IntNode next) {
9.             this.val = val;
10.             this.next = next;
11.         }
12.     }
14.     private IntNode head;
16.     public SLList(int val) {
17.         this.head = new IntNode(val, null);
18.     }
20.     // 获取首部节点值
21.     public int getFirst() {
22.         return this.head.val;
23.     }
25.     // 在首部添加节点
26.     public void addFirst(int val) {
27.         this.head = new IntNode(val, this.head);
28.     }
30.     // 删除首部节点并返回其值
31.     public int removeFirst() {
32.         if (this.head == null) {
33.             System.out.println("Already Empty!");
34.             return 0;
35.         }
37.         int val = this.head.val;
38.         this.head = this.head.next;
39.         return val;
40.     }
42.     // 获取尾部节点值
43.     public int getLast() {
44.         IntNode p = this.head;
46.         while (p.next != null) p = p.next;
47.         return p.val;
48.     }
50.     // 在尾部添加节点
51.     public void addLast(int val) {
52.         IntNode p = this.head;
54.         while (p.next != null) p = p.next;
55.         p.next = new IntNode(val, null);
56.     }
58.     // 删除尾部节点并返回其值
59.     public int removeLast() {
60.         if (this.head == null) {
61.             System.out.println("Already Empty!");
62.             return 0;
63.         }
65.         int val;
67.         if (this.head.next == null) {
68.             val = this.head.val;
69.             this.head = null;
70.         } else {
71.             IntNode p = this.head;
72.             while (p.next.next != null) p = p.next;
73.             val = p.next.val;
74.             p.next = null;
75.         }
77.         return val;
78.     }
80.     // 获取链表长度
81.     public int size() {
82.         return this.size(this.head);  // 无法在该方法中直接实现递归，需要一个额外的辅助方法
83.     }
85.     // size()递归辅助方法
86.     private int size(IntNode p) {
87.         if (p.next == null) return 1;
88.         return 1 + size(p.next);
89.     }
91.     // 重写输出SLList对象的信息
92.     @Override
93.     public String toString() {
94.         if (this.head == null) return "[]";
96.         StringBuilder res = new StringBuilder("SLList: [");
97.         IntNode p = this.head;
99.         while (p != null) {
100.             res.append(p.val);
101.             if (p.next != null) res.append(", ");
102.             else res.append("]");
103.             p = p.next;
104.         }
106.         return res.toString();
107.     }
109.     public static void main(String[] args) {
110.         SLList L = new SLList(5);
112.         L.addFirst(10);
113.         System.out.println(L.getFirst());  // 10
115.         L.addLast(15);
116.         System.out.println(L.getLast());  // 15
118.         System.out.println(L.size());  // 3
119.         System.out.println(L);  // SLList: [10, 5, 15]
121.         System.out.println(L.removeFirst());  // 10
122.         System.out.println(L.removeLast());  // 15
123.         System.out.println(L.size());  // 1
124.         System.out.println(L);  // SLList: [5]
125.     }
126. }

复制代码

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

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

1. package CS61B.Lecture4;
3. public class SLList {
4.     private static class IntNode {
5.         public int val;
6.         public IntNode next;
8.         public IntNode(int val, IntNode next) {
9.             this.val = val;
10.             this.next = next;
11.         }
12.     }
14.     private IntNode head;
15.     private int size;
17.     public SLList(int val) {
18.         this.head = new IntNode(val, null);
19.         this.size = 1;
20.     }
22.     // 获取首部节点值
23.     public int getFirst() {
24.         return this.head.val;
25.     }
27.     // 在首部添加节点
28.     public void addFirst(int val) {
29.         this.head = new IntNode(val, this.head);
30.         this.size++;
31.     }
33.     // 删除首部节点并返回其值
34.     public int removeFirst() {
35.         if (this.head == null) {
36.             System.out.println("Already Empty!");
37.             return 0;
38.         }
40.         int val = this.head.val;
41.         this.head = this.head.next;
42.         this.size--;
43.         return val;
44.     }
46.     // 获取尾部节点值
47.     public int getLast() {
48.         IntNode p = this.head;
50.         while (p.next != null) p = p.next;
51.         return p.val;
52.     }
54.     // 在尾部添加节点
55.     public void addLast(int val) {
56.         IntNode p = this.head;
58.         while (p.next != null) p = p.next;
59.         p.next = new IntNode(val, null);
60.         this.size++;
61.     }
63.     // 删除尾部节点并返回其值
64.     public int removeLast() {
65.         if (this.head == null) {
66.             System.out.println("Already Empty!");
67.             return 0;
68.         }
70.         int val;
72.         if (this.head.next == null) {
73.             val = this.head.val;
74.             this.head = null;
75.         } else {
76.             IntNode p = this.head;
77.             while (p.next.next != null) p = p.next;
78.             val = p.next.val;
79.             p.next = null;
80.         }
82.         this.size--;
83.         return val;
84.     }
86.     // 获取链表长度
87.     public int size() {
88.         return this.size;
89.     }
91.     // 重写输出SLList对象的信息
92.     @Override
93.     public String toString() {
94.         if (this.head == null) return "[]";
96.         StringBuilder res = new StringBuilder("SLList: [");
97.         IntNode p = this.head;
99.         while (p != null) {
100.             res.append(p.val);
101.             if (p.next != null) res.append(", ");
102.             else res.append("]");
103.             p = p.next;
104.         }
106.         return res.toString();
107.     }
109.     public static void main(String[] args) {
110.         SLList L = new SLList(5);
112.         L.addFirst(10);
113.         System.out.println(L.getFirst());  // 10
115.         L.addLast(15);
116.         System.out.println(L.getLast());  // 15
118.         System.out.println(L.size());  // 3
119.         System.out.println(L);  // SLList: [10, 5, 15]
121.         System.out.println(L.removeFirst());  // 10
122.         System.out.println(L.removeLast());  // 15
123.         System.out.println(L.size());  // 1
124.         System.out.println(L);  // SLList: [5]
125.     }
126. }

复制代码

4. 修复addLast()

首先我们写一个无参的构造方法，如许用户可以大概创建一个空链表：

1. public SLList() {
2.     this.head = null;
3.     this.size = 0;
4. }

复制代码

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

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

复制代码

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

1. // 在尾部添加节点
2. public void addLast(int val) {
3.     if (this.head == null) this.head = new IntNode(val, null);
4.     else {
5.         IntNode p = this.head;
7.         while (p.next != null) p = p.next;
8.         p.next = new IntNode(val, null);
9.     }
10.     this.size++;
11. }

复制代码

5. 虚拟头节点

现在观察代码会发现有些方法里做了形如 if (this.head == null) 的特判，当工程代码量变大时如果风俗这么写会导致代码冗余复杂。
我们可以添加一个虚拟头节点，如许就不会存在头节点为空的情况，这种虚拟头节点也称哨兵节点，而且修改 remove 方法使其不返回节点值，因为可以通过 get 方法获取节点值。末了本节课的完整实当代码如下：

1. package CS61B.Lecture4;
3. public class SLList {
4.     private static class IntNode {
5.         public int val;
6.         public IntNode next;
8.         public IntNode(int val, IntNode next) {
9.             this.val = val;
10.             this.next = next;
11.         }
12.     }
14.     private IntNode sentinel;  // 第一个节点在sentinel.next上
15.     private int size;
17.     public SLList() {
18.         this.sentinel = new IntNode(0, null);
19.         this.size = 0;
20.     }
22.     public SLList(int val) {
23.         this.sentinel = new IntNode(0, new IntNode(val, null));
24.         this.size = 1;
25.     }
27.     // 获取首部节点值
28.     public int getFirst() {
29.         IntNode p = this.sentinel;
30.         if (p.next != null) p = p.next;
31.         return p.val;
32.     }
34.     // 在首部添加节点
35.     public void addFirst(int val) {
36.         this.sentinel.next = new IntNode(val, this.sentinel.next);
37.         this.size++;
38.     }
40.     // 删除首部节点
41.     public void removeFirst() {
42.         if (this.sentinel.next == null) return;
43.         this.sentinel.next = this.sentinel.next.next;
44.         this.size--;
45.     }
47.     // 获取尾部节点值
48.     public int getLast() {
49.         IntNode p = this.sentinel;
50.         while (p.next != null) p = p.next;
51.         return p.val;
52.     }
54.     // 在尾部添加节点
55.     public void addLast(int val) {
56.         IntNode p = this.sentinel;
57.         while (p.next != null) p = p.next;
58.         p.next = new IntNode(val, null);
59.         this.size++;
60.     }
62.     // 删除尾部节点
63.     public void removeLast() {
64.         if (this.sentinel.next == null) return;
65.         IntNode p = this.sentinel;
66.         while (p.next.next != null) p = p.next;
67.         p.next = null;
68.         this.size--;
69.     }
71.     // 获取链表长度
72.     public int size() {
73.         return this.size;
74.     }
76.     // 重写输出SLList对象的信息
77.     @Override
78.     public String toString() {
79.         StringBuilder res = new StringBuilder("SLList: [");
80.         IntNode p = this.sentinel;
82.         while (p.next != null) {
83.             res.append(p.next.val);
84.             p = p.next;
85.             if (p.next != null) res.append(", ");
86.         }
88.         res.append("]");
89.         return res.toString();
90.     }
92.     public static void main(String[] args) {
93.         SLList L = new SLList();
94.         System.out.println(L.size());  // 0
95.         System.out.println(L);  // SLList: []
97.         L.addLast(15);
98.         System.out.println(L.getLast());  // 15
100.         L.addFirst(10);
101.         System.out.println(L.getFirst());  // 10
103.         System.out.println(L.size());  // 2
104.         System.out.println(L);  // SLList: [10, 15]
106.         L.removeLast();
107.         L.removeFirst();
108.         L.removeLast();
109.         L.removeFirst();
110.         System.out.println(L.size());  // 0
111.         System.out.println(L);  // SLList: []
112.     }
113. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。