关于java:cs61b-week2The-SLList

1. 赤裸的递归写链表

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

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

构想一下以下面的形式写一个链表结点，那么每次在 public static void main() 中调用，时
应用
IntList L1 = new IntList(5, null);
当咱们要在以后结点前插入一个新的结点时，

IntList L = new IntList(5, L);
IntList L = new IntList(15, L);
IntList L = new IntList(50, L);

每次都须要这样写，IntList()的参数，第一个是数据项，第二个是结点的指针指向，应用以上语句，以后新结点的指针每次都指向上一个结点，从而实现头插。然而以可读性来说，对于 Java 老手十分不敌对。

2. 改良的链表写法

实质上是把一些反复的操作封装在类外面，从而在 main()中调用时更加清晰简洁
首先对结点类进行封装，与上文赤裸的封装形式别无他样

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

    public IntNode(int f,IntList r){
        item = f;
        next = r;
    }
}

之后构建一个 SLList class 在外面封装一些办法，比方 构造函数：

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

则咱们的传参缩小为只有一个 x，也就是省去了每次都须要本人加 null，
在以后结点前增加新的结点：

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

类比上文中在 main()外面增加新结点的办法，每次都是
IntList L = new IntList(data,L)
咱们把每次新结点的 rest 指针指向上一个结点的操作封装在类内，省去每次调用都要写一遍的操作
返回以后结点的数据：

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

残缺代码：

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;}
}

精彩的是，当咱们在 main()外面调用时，不再显得横七竖八，更加便于了解，比方 构建链表头结点与新增结点操作：

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

一眼就能看进去是增加了 10，5 这两个结点。

3.Private 申明

假如某人有一个愚昧的做法，这样写

public class SLLTroubleMaker {public static void main(String[] args) {SLList L = new SLList(15);
        L.addFirst(10);
        L.first.next.next = L.first.next;
    }
}

当你应用
L.first.next.next = L.first.next;
这会导致结点指向本身，从而造成有限循环，为了防止外人调用 first 成员，咱们能够将其设为公有的，即
private IntNode first;
公有变量往往是须要用户理解的，就比方对一辆汽车而言，其发动机引擎如何将汽油焚烧等等不须要咱们晓得，咱们只须要操作 public 的方向盘等等，
当你申明 public 时，示意全世界都有永恒拜访它的权限

4. 嵌套类

因为 java 主类的名字必须与.java 的文件名雷同，否则无奈编译，以前咱们总是把两个 class 写在两个.java 文件中，而后调用它们，比方上文中的链表创立，咱们先在一个.java 文件中写下 public class IntNode, 再在另一个.java 文件中 public class SLList 中调用
显然这是比拟麻烦的，因而咱们能够把 class IntNode 写进 class SLList 中，作为嵌套类

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);
       } 
...

分割上文咱们所说的 private, 咱们能够把 class IntNode 设置为private，禁止拜访其外部成员
private class IntNode
static
当嵌套类齐全不须要应用外部类的任何办法和成员时，能够加上 static, 申明为static 意味着动态类中的办法不能拜访关闭类的任何成员。在这种状况下，这意味着 IntNode 将无法访问 first，addFirst()或 getFirst()。
private static class IntNode
应用 static 的前提是确保嵌套类齐全不须要拜访内部元素，加上 static 能够节俭内存空间

5.addLast()与 size()

接下来须要增加两个办法，作用别离是在链表开端增加一个新的结点和计算链表的总长度，
因为每次默认的新增结点都是头插，每次新增结点都是插入到以后结点之前，因而 first 总是头结点，要做到在链表开端增加一个新的结点，须要先遍历链表直到达到最初一个结点，再作增加操作

public void addLast(int x) {
    IntNode p = first;

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

因为咱们的主类是 SLList，并没有 next 指针，所以须要应用 IntNode 外面的 next，增加辅助办法

private static int size(IntNode p) {if (p.next == null) {return 1;}

    return 1 + size(p.next);
}

这是递归的办法求长度，十分相似于求二叉树的深度，返回 1 + 残余链表的长度，1 即以后结点长度，如 josh hug 所说，这是神的语言，咱们将其转换为凡人的语言

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

Java 容许两个函数同名，只有两个函数的参数定义不同即可，这叫做 函数重载

6. 改良 size()的办法 –caching

咱们的递归求解 size()，当数据量足够宏大时，工夫复杂度是O(n), 当计算 100 长度的链表须要两秒时，计算 100000 长度的链表可能须要 2000 秒，对于此，咱们须要进行改良，也就是新增一个size 变量，记录以后链表的长度

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;}
    ...
}

那么初始时只有一个头结点，size=1, 尔后每次进行减少操作，size+ 1 即可，这样的工夫复杂度将 是 O(1) 级别。

7. 空链表与哨兵结点

假如咱们想创立一个空的链表

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

那么当咱们在调用之前的 addLast()办法时，其中的

p=first;
while(p.next!=null)

这里 p =first=null, 咱们调用 p.next 相当于调用 null.next，显然会触发 NullPointerException, 简略的解决办法是在 addLast() 加一个特判条件

    if (first == null) {first = new IntNode(x, null);
        return;
    }

然而当咱们之后面对更为简单的数据结构，诸如树，图之时，这种特判会十分麻烦，因而为了对立，咱们设定一个哨兵结点，也就是相当于头结点，其数据域不放任何值（也能够轻易赋值，don’t care），而后真正的数据项从头结点的下一项开始寄存，这样空链表的判断条件则是 head.next=null 即可，不会触发空指针异样

全副都增加哨兵结点之后的代码为

public class SLList{

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

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

    public IntNode sentinel;
    private int size;

    public SLList(){sentinel = new IntNode(??,null);
        size = 0;
    }

    public SLList(int x){sentinel = new IntNode(??,null);
        sentinel.next = new IntNode(x,null);
        size = 1;
    }

    public void addFirst(int x){sentinel.next = new IntNode(x,sentinel.next);
        size++;
    }

    public int getFirst(){return sentinel.next.item;}

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

8.Invariants

带有哨兵结点的 SLList 至多具备以下 invariants：

• sentinel 援用总是指向哨兵结点。
• 第一个真正的结点（如果存在）始终位于 sentinel.next.item。
• SSList 的 size 变量始终是已增加的我的项目总数。