CS61B 课程笔记（Lecture 04）

1. SLList简介

SLList（单向链表）是一种动态数据结构，允许高效地插入和检索元素。与IntList（静态列表）相比，SLList提供了更灵活的操作接口。

2. SLList的基本结构

IntNode类

表示链表中的一个节点，包含一个整数项和对下一个节点的引用。

public class IntNode {
    public int item;        // 节点存储的整数项
    public IntNode next;    // 指向下一个节点的引用

    // 构造函数
    public IntNode(int i, IntNode n) {
        item = i;          // 设置节点的项
        next = n;         // 设置下一个节点的引用
    }
}

SLList类

维护对第一个节点的引用，并提供方法以进行列表操作。

public class SLList {
    public IntNode first;   // 链表的第一个节点

    // 构造函数，初始化链表
    public SLList(int x) {
        first = new IntNode(x, null); // 创建第一个节点
    }

    /** 向列表前面添加一个项。 */
    public void addFirst(int x) {
        first = new IntNode(x, first); // 创建新节点并更新首节点
    }

    /** 从列表中检索前面的项。 */
    public int getFirst() {
        return first.item; // 返回首节点的项
    }
}

示例用法

SLList L = new SLList(15); // 创建一个包含15的SLList
L.addFirst(10);             // 向链表前面添加10
L.addFirst(5);              // 向链表前面添加5
int x = L.getFirst();       // x将为5

3. SLList与IntList的比较

IntList 是一种更简单的实现，变量可能直接指向列表的不同部分。
SLList 通过提供抽象，作为与数据结构的中介，简化了用户的交互。

4. Java中的访问控制

使用private关键字限制对类成员的访问，有助于隐藏实现细节，并简化用户与类的交互。

限制访问的好处：

减少用户的认知负担。
允许在不影响用户的情况下进行内部更改。
公共成员意味着需要承诺维持其行为。

5. 嵌套类

嵌套类有助于组织代码，当一个类在逻辑上属于另一个类时特别有用。

使用嵌套类的情况：

当嵌套类从属于外部类时。
封装不需要在外部访问的功能。

静态嵌套类

如果嵌套类不访问外部类的任何实例变量或方法，则应声明为static。

public class SLList {
    public static class IntNode {
        public int item;        // 节点存储的整数项
        public IntNode next;    // 指向下一个节点的引用

        public IntNode(int i, IntNode n) {
            item = i;          // 设置节点的项
            next = n;         // 设置下一个节点的引用
        }
    }
}

6. 使用缓存管理大小

维护一个大小变量来缓存列表的大小，使得大小查询的时间复杂度为O(1)。

public class SLList {
    private IntNode first;   // 链表的第一个节点
    private int size;        // 链表的大小

    public SLList(int x) {
        first = new IntNode(x, null); // 创建第一个节点
        size = 1;                     // 初始化大小
    }

    public void addFirst(int x) {
        first = new IntNode(x, first); // 创建新节点并更新首节点
        size += 1;                     // 增加大小
    }

    public int size() {
        return size;                   // 返回当前大小
    }
}

7. 哨兵节点

哨兵节点通过消除特殊情况（例如，空列表处理）来简化链表操作。

哨兵节点的实现

创建一个始终存在的哨兵节点，可以简化许多链表操作，使代码更简单易懂。

public class SLList {
    private IntNode sentinel; // 哨兵节点

    public SLList() {
        sentinel = new IntNode(0, null); // 创建哨兵节点，项可以是任意值
        sentinel.next = sentinel; // 哨兵节点的下一个指向自身
    }

    public void addFirst(int x) {
        IntNode newNode = new IntNode(x, sentinel.next); // 新节点指向当前第一个节点
        sentinel.next = newNode; // 哨兵节点指向新节点
    }

    public int getFirst() {
        if (sentinel.next == sentinel) {
            throw new RuntimeException("List is empty!"); // 检查是否为空
        }
        return sentinel.next.item; // 返回第一个有效节点的项
    }

    public int size() {
        int count = 0;
        IntNode current = sentinel.next; // 从哨兵节点的下一个开始遍历
        while (current != sentinel) { // 直到回到哨兵节点
            count++;
            current = current.next;
        }
        return count; // 返回大小
    }
}