【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对象的信息
    @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)$ 的时间复杂度，这也是上一节课中直接裸露递归的类 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: []
    }
}