CS61B Notes：5. Lists II SLLists

概述

链表是一种由节点（Node）组成的线性数据结构，节点之间通过指针连接，而不是像数组一样连续存储在内存中。

SLList（Singly Linked List，单向链表）中的每个节点只保存指向下一个节点的引用，因此只能从前向后遍历。

Pasted image 20260311115951

SLList 的实现

考虑以下代码：

public class IntNode {  
    public int item;  
    public IntNode next;  
  
    public IntNode(int i, IntNode n) {  
       item = i;  
       next = n;  
    }  
}

public class SLList {  
    public IntNode first;  
  
    public SLList(int x) {  
       first = new IntNode(x, null);  
    }  
  
	/** 在前面添加 x **/
    public void addFirst(int x) {  
       first = new IntNode(x, first);  
    }  
  
	/** 获取第一项 **/  
    public int getFirst() {  
       return first.item;  
    }  
  
    public static void main(String[] args) {  
       SLList L = new SLList(15);  
       L.addFirst(10);  
       L.addFirst(5);  
       int x = L.getFirst();  
       System.out.println("The first element is: " + x);  
    }  
}

执行完毕后，示意图如下：

如上图所示，L 指向一个 SLList 实例，该实例内部有一个成员变量 first，first 包含一个 IntNode 实例。该 IntNode 实例中包含两个成员变量：item 和 next。

L.addFirst(10) 调用 public void addFirst(int x) 方法，形成链式结构，如下图所示：

由于 L 是引用类型变量，它始终指向同一个 SLList 实例。

因此该代码不是改变了 L 本身，而是改变了 L 所指向对象内部的成员变量状态。具体而言，是通过 addrFirst 方法改变了 SLList 实例内部的成员变量 first 的内容。

访问控制

Pasted image 20260307185140

private 意味着外部类无权直接访问，用户无法直接访问，所以调用 L.first 就会报错。

我们应该通过 private 关键字来阻止用户直接修改类属性的内容，让用户通过开发者提供的公共方法进行修改，这更加安全。

同时，将某些变量设置为 private 可以避免很多错误。

嵌套类

可以把上述两个部分合并到一起，即 java 允许一个类中嵌套另一个类。

public class SLList {
       public class IntNode {
            public int item;
            public IntNode next;
            public IntNode(int i, IntNode n) {
                item = i;
                next = n;
            }
       }

       private IntNode first; 

       public SLList(int x) {
           first = new IntNode(x, null);
       } 
...

嵌套类的访问规则：

普通嵌套类可以直接访问外部类实例成员。
如果嵌套类 IntNode 不需要使用 SLList 的任何实例方法或变量，你可以将其声明为 static。

缓存

如果想直接计算某个列表的大小，我们需要一步一步迭代或者递归，这样占用了太多时间。

取而代之的是直接维护一个 size 变量，每当列表有改变，就同时对 size 变量做修改。

哨兵节点

当列表为空的时候，直接对该列表调用一些指令可能会出错，因此我们需要一个哨兵节点为我们“挡下”这部分操作

空列表：