CS61B 学习笔记

$\textcolor{cyan}{不妨就跳过基础的Java语法知识吧}$

2.列表

Java 永远复制变量中保存的内容；基本类型变量保存数据本身，对象变量保存对象的引用。

例如调用函数max(a,b)，a 和 b 在此之前定义时已经有内存存储了，故在调用时只是把参数的比特复制进函数作用域中，即按值传递。

数组实例化

int[] x;
Dog[] Dogs;

两条声明都会创建一个64位的内存盒。

2.1 IntList

public class IntList{
    public int first;
    public IntList rest;

    public IntList(int f, IntList r){
        first = f;
        rest = r;
    }
}

此内容在 cs61a 中有所记载 —> 神秘连接

上面的代码过于丑陋，因此我们考虑添加 size 方法。使调用 L.size() 时能得到 L 中元素数量。

size 实现方法

public int size(){
    if (rest == null){
        return 1;
    }
    return 1 + this.rest.size();
}

iterativesize 实现方法

public int iterativesize(){
    IntList p = this;
    int totalsize = 0;
    while (p != null){
        totalSize += 1;
        p = p.rest;
    }
    return totalSize;
}

简单分析一下

• size
  • 时间复杂度：$\Theta (N)$
  • 空间复杂度（容易 stackoverflow）：$\Theta (N)$
• iterativesize
  • 时间复杂度：$\Theta (N)$
  • 空间复杂度：$\Theta (1)$

2.2 SLList

在 2.1 中，我们构建了 IntList 类。从技术上说，它可以完成列表应做的所有事情；但在实际使用中，IntList 相当“别扭”，会导致代码难以月的和维护

根本问题在于，IntList 是一种我称为裸递归的数据结构。为了正确使用 IntList，程序员即便只完成简单的列表操作，也必须理解并运用递归。这限制了它对初学者的适用性；而且根据 IntList 类提供了哪些辅助方法，还可能引入一整类棘手的新错误。(懒得写直接复制了)

吸取 IntList 的经验后，我们讲构建一个新类 SLList。

改进 1：重命名

原 IntList 类：

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }
...

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

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

改进 2：添加一层类

public class SLList {
    public IntNode first;

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

添加两个简单的方法：addFIRST 和 getFirst

public class SLList {
    public IntNode first;

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

    /** Adds an item to the front of the list */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
}

/** Retrieves the front item from the list */
public int getFirst() {
    return first.item;
}

优化后的等价比较

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

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

两种数据结构的对比图

我们发现，IntList 可能让变量指向 IntList 的中间位置，这并不是一件好事，因为我们仅仅想要加个头节点。

正如奥维德所说，凡人直视神明便会死去。

因此我们采用 SLList 作为中介，这种方式安全且更为简便。

练习1 给 IntList 写一个 addFirst 方法

错误写法

public void addFirst(int x) {
    this = new IntList(x, this);
}

这是由于 `this` 是 `final` 引用，代表当前对象的地址，不能改变他的值(这和c++是一样的)。

丑陋写法
```java
public void addFirst(int x) {
    this.rest = new IntList(this.first, this.rest);
    this.first = x;
}