cs61b week2--The 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即可,不会触发空指针异常
cs61b week2--The SLList_第1张图片

全部都添加哨兵结点之后的代码为

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变量始终是已添加的项目总数。

你可能感兴趣的