2.2.单链表

发表于 2024-05-31 更新于 2024-06-02 分类于 CS61B DataStructure ， 2.List 阅读次数：本文字数： 1.6k 阅读时长 ≈ 6 分钟

\(2.2\)单链表

在前一章中，我们搭建了整型链表\(IntList\)，但在实际应用中，\(IntList\)较难使用，并且会导致代码难以理解与维护。

这些问题的来源是：\(IntList\)是一个裸裸递归结构：\(IntList\)在函数内部直接调用自身的递归，而没有其他辅助操作或条件检查。

下面我们对\(IntList\)进行一系列优化，来搭建新的类\(SLList\)。

1.重构

public class IntNode {
    public int item;
    public IntNode next;

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

为了避免\(IntList\)的复杂使用，我们创建一个单独的\(SLList\)类给用户使用：

public class SLList {
    public IntNode first;

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

\(SLList\)的实现隐藏了\(IntList\)的一些细节，使得定义链表变得更简洁：

1 2	IntList L1 = new IntList(5, null); SLList L2 = new SLList(5);

2.`addFirst`，`getFirst`

public void addFirst(int x) {
    first = new IntNode(x, first);
}

public int getFirst() {
    return first.item;
}

这样优化后的链表很方便使用：

SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
int x = L.getFirst();

//compared with IntList//
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
int x = L.first;

可以看到，\(SLList\)类扮演了链表使用者和裸递归数据结构间中介人的角色。

3.`public`和`private`

先前定义的\(SLList\)有一个问题：用户的一些操作会导致链表的异常。例如：

1
2
3

SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;

这会导致链表的无限延长，而这是我们不希望看到的。我们可以采用下面的方法来杜绝这件事：

1
2
3

public class SLList {
    private IntNode first;
...

private变量和方法只能被同一个.java文件内的代码访问，其他文件访问它时，会返回first has private access in SLList的错误。

在软件工程中，private关键字表明一段代码应该被用户忽略、也不需要被用户理解。public关键字则声明了一个方法是可用的、并且永远不会出错(不管用户做出什么更改)。因此，要谨慎使用public关键字。

As an analogy, a car has certain public features, e.g. the accelerator and brake pedals. Under the hood, there are private details about how these operate. In a gas powered car, the accelerator pedal might control some sort of fuel injection system, and in a battery powered car, it may adjust the amount of battery power being delivered to the motor. While the private details may vary from car to car, we expect the same behavior from all accelerator pedals. Changing these would cause great consternation from users, and quite possibly terrible accidents.

4.嵌套类

目前为止我们定义了两个类：\(IntNode\)和\(SLList\)，但是\(IntNode\)实际上只是辅助\(SLList\)的。

对此，\(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);
       } 
...

创建一个嵌套类与分开定义两个类的效果是一样的，只是前者能让代码看起来更为整齐。

如果嵌套类不需要使用\(SLList\)中的任何实例方法或者变量，我们可以用static来声明它。static关键字说明静态类(\(static\;class\))中的方法不能访问任何在封闭类中的成员。在这个例子中，这意味着\(IntNode\)不能够访问first，addFirst或者getFirst。

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

       private IntNode first;
...

这样的做法可以节约一些内存，因为之后\(IntNode\)就不需要再追踪它怎么访问它所处的\(SLList\)了，从而\(IntNode\)不会调用\(SLList\)。

if you don't use any instance members of the outer class, make the nested class static.

5.`addLast`、`size`

/** Adds an item to the end of the list. */
public void addLast(int x) {
    IntNode p = first;

    /* Advance p to the end of the list. */
    while (p.next != null) {
        p = p.next;
    }
    p.next = new IntNode(x, null);
}

/** Returns the size of the list starting at IntNode p. */
private static int size(IntNode p) {
    if (p.next == null) {
        return 1;
    }

    return 1 + size(p.next);
}

这个\(size\)函数也是\(O(n)\)复杂度的。为了减少时间消耗，我们可以像创建\(SLList\)一样创建一个“中介人”，来实现用户对\(Size\)的访问：

/** Returns the size of the list starting at IntNode p. */
private static int size(IntNode p) {
    if (p.next == null) {
        return 1;
    }

    return 1 + size(p.next);
}

public int size() {
    return size(first);
}

这里出现了两个方法，名称都叫\(size\)。这是允许的，因为它们有不同的参数。我们把这种方法名字相同、参数不同的方法称作重载(\(overloaded\))。

6.缓存\(cashing\)

除了用上面的方法计算\(size\)，我们还可以在\(SLList\)类中添加一个\(size\)变量：

public class SLList {
    ... /* IntNode declaration omitted. */
    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;
    }
    ...
}

这种通过保存关键信息来加速检索的方法被称为缓存(\(cashing\))。

7.空链表

我们\(SLList\)的框架可以轻松地初始化链表：

public SLList() {
    first = null;
    size = 0;
}

8.哨兵节点(\(sentinel\))

我们可以按照上一章的方法实现addLast方法：

public void addLast(int x) {
    size += 1;
    IntNode p = first;
    while (p.next != null) {
        p = p.next;
    }

    p.next = new IntNode(x, null);
}

但是，当传入的链表是空链表时，由于first == null，while(p.next != null),p.next这些方法都会导致null pointer exceptation的错误。

我们可以单独讨论first == null的情况，但这样会让程序变得复杂。因此我们设法将所有的链表都统一成一种情况。

我们可以在链表的开头创建一个节点，叫作哨兵节点(\(sentinel\;node\))，不管链表是否为空，这个节点都存在。

在将所有情况统一后，我们就可以更好地实现addLast：

public void addLast(int x) {
    size += 1;
    IntNode p = sentinel;
    while(p.next != null) {
        p = p.next;
    }
    
    p.next = new IntNode(x, null);
}

9.不变量\(invarient\)

不变量，就是数据结构中必须要遵守的事实(\(fact\;that\;is\;guaranteed\;to\;be\;true\))。

一个\(SLList\)至少要遵循以下不变量：

sentinel总是指向哨兵节点。
链表最前面的元素(如果存在的话)永远是sentinel.next.item。
size变量永远代指被加入链表的元素的数量。