【UCB CS 61B SP24】Lecture 5 - Lists 3: DLLists and Arrays学习笔记

本文内容为构建双向循环链表、使用 Java 的泛型将其优化为通用类型的链表以及数组的基本语法介绍。

1. 双向链表

回顾上一节课写的代码，当执行 addLast() 与 getLast() 方法时需要遍历链表，效率不高，因此可以添加一个指向链表末尾的索引，这样 addLast() 与 getLast() 方法的时间复杂度就为 $O(1)$。

但是我们再考虑一下 removeLast() 方法，如下图所示：

即使我们有了指向链表末尾的指针 last，但是当我们要移除最后一个节点时，需要的不是最后一个节点“50”的信息，而是倒数第二个节点“9”，我们需要将“9”的 next 置为 null，并将 last 指向“9”：

那么我们想要定位到这个节点“9”的唯一方法还是需要从头遍历一遍链表，同理如果你想将 last 指向链表的倒数第二个节点，认为这样就能快速定位，那么就会有新的问题：当节点“50”被删除后，如何更新 last 指向节点“3”？显然又需要从头遍历链表。

有什么办法能快速定位到这个节点呢？我们可以让每个节点不仅指向后一个节点，还能指向前一个节点，这就是双向链表（Doubly Linked List）：

但是此时又会出现棘手的问题，那就是 last 指针在链表为空时会指向哨兵节点，在链表不为空时又会指向最后一个实值节点：

有什么办法能统一起来呢？能想到的第一个方案就是同样给尾部设定一个哨兵节点，就和之前的表头哨兵节点类似：

此外还有更完美的解决方案，那就是构建循环链表，这样只需要一个哨兵节点，无需指向链表末尾的指针，当链表为空时，哨兵的前一个节点和后一个节点都是指向自己，当链表不为空时哨兵的前一个结点为末尾节点，末尾节点的后一个节点为哨兵：

实现代码如下：

package CS61B.Lecture5;public class DLList {private static class IntNode {public int val;public IntNode next;public IntNode prev;public IntNode(int val, IntNode next, IntNode prev) {this.val = val;this.next = next;this.prev = prev;}}private IntNode sentinel = new IntNode(0, null, null);private int size;public DLList() {this.sentinel.next = this.sentinel.prev = sentinel;this.size = 0;}public DLList(int val) {IntNode p = new IntNode(val, this.sentinel, this.sentinel);this.sentinel.next = this.sentinel.prev = p;this.size = 1;}public int size() {return this.size;}public int getFirst() {return this.sentinel.next.val;}public void addFirst(int val) {IntNode p = new IntNode(val, this.sentinel.next, this.sentinel);this.sentinel.next.prev = p;this.sentinel.next = p;this.size++;}public void removeFirst() {if (this.size == 0) return;this.sentinel.next.next.prev = this.sentinel;this.sentinel.next = this.sentinel.next.next;this.size--;}public int getLast() {return this.sentinel.prev.val;}public void addLast(int val) {IntNode p = new IntNode(val, this.sentinel, this.sentinel.prev);this.sentinel.prev.next = p;this.sentinel.prev = p;this.size++;}public void removeLast() {if (this.size == 0) return;this.sentinel.prev.prev.next = this.sentinel;this.sentinel.prev = this.sentinel.prev.prev;this.size--;}@Overridepublic String toString() {StringBuilder res = new StringBuilder("DLList: [");IntNode p = this.sentinel;while (p.next != this.sentinel) {res.append(p.next.val);p = p.next;if (p.next != this.sentinel) res.append(", ");}res.append("]");return res.toString();}public static void main(String[] args) {DLList L = new DLList();L.addFirst(5);L.addFirst(10);System.out.println(L.getFirst());  // 10System.out.println(L);  // DLList: [10, 5]L.removeFirst();System.out.println(L);  // DLList: [5]System.out.println(L.size());  // 1L.addLast(20);System.out.println(L.getLast());  // 20System.out.println(L);  // DLList: [5, 20]L.removeFirst();L.removeLast();System.out.println(L);  // DLList: []}
}

2. 通用类型双向链表

现在我们的链表只能存放整数，如果想存放其他数据类型例如字符串，那么需要拷贝一份代码将其中的 int 修改为 String，显然这样很冗余。

如果想实现一个通用类型的数据结构，就需要引入 Java 的泛型概念，我们可以将 DLList 定义为泛型类，这样能够编写出类型安全的、可重用的代码，同时避免类型转换的繁琐操作和潜在的运行时错误。

通过在 <> 中添加类型参数用来表示泛型，类型参数通常使用单个大写字母表示，常见的命名约定如下：

• T：Type（类型）
• E：Element（元素）
• K：Key（键）
• V：Value（值）
• N：Number（数字）

需要注意：

• 泛型类型参数必须是引用类型，不能是基本数据类型（如 int、double 等）。如果需要使用基本数据类型，可以使用其对应的包装类（如 Integer、Double）。
• 泛型类型参数不能是 final 修饰的类，因为它们不能被继承。

package CS61B.Lecture5;public class DLList<T> {private class IntNode {public T val;public IntNode next;public IntNode prev;public IntNode(T val, IntNode next, IntNode prev) {this.val = val;this.next = next;this.prev = prev;}}private IntNode sentinel = new IntNode(null, null, null);private int size;public DLList() {this.sentinel.next = this.sentinel.prev = sentinel;this.size = 0;}public DLList(T val) {IntNode p = new IntNode(val, this.sentinel, this.sentinel);this.sentinel.next = this.sentinel.prev = p;this.size = 1;}public int size() {return this.size;}public T getFirst() {return this.sentinel.next.val;}public void addFirst(T val) {IntNode p = new IntNode(val, this.sentinel.next, this.sentinel);this.sentinel.next.prev = p;this.sentinel.next = p;this.size++;}public void removeFirst() {if (this.size == 0) return;this.sentinel.next.next.prev = this.sentinel;this.sentinel.next = this.sentinel.next.next;this.size--;}public T getLast() {return this.sentinel.prev.val;}public void addLast(T val) {IntNode p = new IntNode(val, this.sentinel, this.sentinel.prev);this.sentinel.prev.next = p;this.sentinel.prev = p;this.size++;}public void removeLast() {if (this.size == 0) return;this.sentinel.prev.prev.next = this.sentinel;this.sentinel.prev = this.sentinel.prev.prev;this.size--;}@Overridepublic String toString() {StringBuilder res = new StringBuilder("DLList: [");IntNode p = this.sentinel;while (p.next != this.sentinel) {res.append(p.next.val);p = p.next;if (p.next != this.sentinel) res.append(", ");}res.append("]");return res.toString();}public static void main(String[] args) {DLList<String> L = new DLList<>();  // new DLList<String>()中的String可以省略，Java会自动判断L.addFirst("World");L.addFirst("Hello");System.out.println(L.getFirst());  // HelloSystem.out.println(L);  // DLList: [Hello, World]L.removeFirst();System.out.println(L);  // DLList: [World]System.out.println(L.size());  // 1L.addLast("Algorithm");System.out.println(L.getLast());  // AlgorithmSystem.out.println(L);  // DLList: [World, Algorithm]L.removeFirst();L.removeLast();System.out.println(L);  // DLList: []}
}

注意 IntNode 类需要改为非静态的，泛型类型变量不能直接在静态方法或静态上下文中使用，因为泛型类型变量是与类的实例相关联的，而静态上下文与类的实例无关。

3. 数组

数组的大小在创建时必须指定，并且一旦创建，其大小不能改变。如果需要更大的数组，必须创建一个新的数组并复制数据。但数组通过索引直接访问元素，时间复杂度为 $O(1)$，适合频繁读取的场景。

3.1 数组基本语法

建议每次创建数组时都使用关键字 new，因为数组也是一个 Object，在声明了数组中的变量后也可以省略 new 关键字：

package CS61B.Lecture5;import java.util.Arrays;public class ArraySyntax {public static void main(String[] args) {int[] a = new int[3];int[] b = new int[]{1, 2, 3};int[] c = {1, 2, 3};Arrays.stream(a).forEach(x -> System.out.print(x + " "));  // 0 0 0System.out.println();Arrays.stream(b).forEach(x -> System.out.print(x + " "));  // 1 2 3System.out.println();Arrays.stream(c).forEach(x -> System.out.print(x + " "));  // 1 2 3}
}

现在再来看下面这段代码：

package CS61B.Lecture5;public class ArrayBasics {public static void main(String[] args) {int[] a = null;int[] b, c;b = new int[]{1, 2, 3, 4, 5};c = b;b = new int[]{-1, 2, 5, 4, 99};c = new int[3];a = new int[0];int b_length = b.length;String[] s = new String[6];s[4] = "ketchup";s[b[3] - b[1]] = "muffins";int[] x = {9, 10, 11};System.arraycopy(x, 0, b, 3, 2);}
}

首先声明了一个名为 a 的数组引用，但是并没有调用 new 关键字，此时 Java 并没有创建空间，只是创建了用于存放数组引用的整数空间。同样 b 和 c 只是声明了一个整数数组的引用，未存放实际的数组。

之后通过初始化了一个长度为5的数组，new 关键字使得 Java 在内存中挖掘5个连续的位置用来存放这个数组的内容，并将其地址返回给变量 b。当执行 c = b 时是将数组的引用赋值给 c，因此实际上这时候 b 和 c 指向了同一个数组，如下图所示：

接下来执行的 b = new int[]{-1, 2, 5, 4, 99}; 语句使用 new 关键字重新创建了一个数组，这时候新数组返回了一个新的内存地址，此时 b 和 c 便指向了不同数组：

再看下一步的 c = new int[3]; 改变了 c 使其指向一个新的长度为3的数组：

此时最早创建的数组 {1, 2, 3, 4, 5} 消失了，因为已经没有任何引用能找到这个数组的地址了，垃圾收集器会将其清理掉永远无法再访问这个数组。

再看下一行创建了一个长度为0的数组，虽然这样几乎没什么意义，但是只是想说明一下可以这么做：

b.length 能够获取 b 所指向的数组的长度，但是从之前的图上我们没看到任何其他变量能够记录数组的长度，因此事实证明数组有一个隐秘的实例变量记录长度，通过 Java Visualizer 无法查看这个值在哪。

String 是引用数据类型，因此如果创建了数组并不能将字符串的值直接存放在数组的那个位置上，而是在其他某个位置创建一个字符串对象后再将其引用存放在数组的某个位置上。

最后一行的 System.arraycopy() 方法是将 x 数组从0开始索引取2个值（也就是 [9, 10]）复制到 b 数组从3开始索引的对应位置上：

3.2 二维数组

我们创建一个4行的二维数组：

package CS61B.Lecture5;public class Array2D {public static void main(String[] args) {int[][] a = new int[4][];a[0] = new int[]{1};a[1] = new int[]{1, 1};a[2] = new int[]{1, 2, 1};a[3] = new int[]{1, 3, 3, 1};}
}

此时我们实际上是在内存中创建了5个数组，a 指向了一个长度为4的数组，这个数组中的每个位置又存放了一个指向某个一维数组的引用，如下图所示：