cs61b week2--The SLList java

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

【cs61b week2--The SLList】完整代码：

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：