public class IntList {
public int first;
public IntList rest;
public IntList(int first, IntList rest) {
this.first = first;
this.rest = rest;
}能用，但不够好。提供更好的封装，隐藏掉具体的实现细节更符合 Java 的哲学。
封装
- 提供 Node
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
this.item = i;
this.next = n;
}
}- 封装 Node 到 List，此时即可封装掉 next 的指针，只通过构造器来完成全新数组的构建
public class SLList {
public IntNode first; // 可视作 链表头指针
public SLList(int x) {
this.first = new IntNode(x, null);
}
}public static void main(String[] args) {
SLList slList = new SLList(5);
}- Improvement: Using private to control the access.
When you create a public member (i.e. method or variable), be careful, because you’re effectively committing to supporting that member’s behavior exactly as it is now, forever.
Having a nested class has no meaningful effect on code performance, and is simply a tool for keeping code organized. For more on nested classes, see Oracle’s official documentation.
If the nested class has no need to use any of the instance methods or variables of SLList, you may declare the nested class static, as follows. Declaring a nested class as static means that methods inside the static class can not access any of the members of the enclosing class. In this case, it means that no method in IntNode would be able to access first, addFirst, or getFirst. This saves a bit of memory, because each IntNode no longer needs to keep track of how to access its enclosing SLList. Put another way, if you examine the code above, you’ll see that the IntNode class never uses the first variable of SLList, nor any of SLList’s methods. As a result, we can use the static keyword, which means the IntNode class doesn’t get a reference to its boss, saving us a small amount of memory.
A simple rule of thumb is that if you don’t use any instance members of the outer class, make the nested class static. 1
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
this.item = i;
this.next = n;
}
}
private IntNode first;
public SLList(int x) {
this.first = new IntNode(x, null);
}
}插入
头插法
new node & next 指向原链表头，再将 new object 的地址 return 给 first（链表头指针）即可。
/* add to 1st place */
public void addFirst(int x) {
this.first = new IntNode(x, first);
}尾插法
just do while loop.
public void addLast(int x) {
IntNode end = this.first;
while (end.next != null) {
end = end.next;
}
end.next = new IntNode(x, null);
}size()
想要做递归实现则需要引入 helper method 建立起 IntNode & SLList 之间的联系。SLList 本身是没有递归定义的，所以试图只使用 size() 去完成递归描述非常不简洁，所以使用接收 IntNode 作 middleman 的 helper function 解决。
private static int size(IntNode p){
if (p.next == null){
return 1;
}
return 1 + size(p.next);
}
public int size(){
return size(this.first);
}static V.S. non-static
注意到 size() 的 helper 设置成了 private static，经过 ai 交流 后得到：
依赖实例，则为实例方法 (non-static)，反之则为静态方法 (static)。如果一个方法需要读取或修改对象的某个特定状态（即实例变量），那么它必须是一个实例方法 (non-static)。
如果一个方法的功能不依赖于任何对象的特定状态，它的逻辑是自给自足的（所有需要的输入都通过参数传来），那么它应该是一个静态方法 (static)。
caching
与 递归/loop 计算 size 大小相比，更优方案是 SLList 本身维护一个 int size。当涉及增删操作时 update size，size() 则 return this.size。
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
this.item = i;
this.next = n;
}
}
private IntNode first;
private int size;
public SLList(int x) {
this.first = new IntNode(x, null);
this.size = 1;
}
/* add to 1st place */
public void addFirst(int x) {
this.first = new IntNode(x, first);
this.size += 1;
}
public void addLast(int x) {
IntNode end = this.first;
while (end.next != null) {
end = end.next;
}
end.next = new IntNode(x, null);
this.size += 1;
}
public int size(){
return this.size;
}
}Sentinel Node
上方的实现存在一个功能缺失，即需要引入空列表。SLList 应当可以表示一个空列表。
引入空列表的方式显而易见，提供一个空参构造器，set first = null。
但在后续测试中发现：在允许 SLList instance = null 的时候，addLast() 方法会存在 bug。当 instance = null, addLast() 在访问 end.next 时实际访问的是 null.next，出现 NullPointerException。
解决方式有二，显然法二更美：
-
使用卫语句，if p == null, return? throw Exception? 该方法事实上可以解决问题，但是引入了 special case。引入 special case 始终是下下策，我们需要一个更 general 的方法去处理这些 special case，否则在后续的代码累积中可能积攒下海量屎山。
-
使用 sentinel node（哨兵节点）来解决：
- SLList 的第一个节点永远是一个 sentinel node（IntNode），通过提供一个统一的模式（即，无论何时 SLList 都永远有 node 存在）来保证对 node 操作的统一。这是更 general 的解法。
- 对 SLList，笔者考虑使用 sentinel 的 item 空间来存储 size，来减少 SLList 下的 size variable，但事实上必要性不大，纯属个人审美。
修改后观察代码发现引入 sentinel node 提高了 function 编写的难度，例如 addFirst 不再是简单的插到队首，而是 sentinel node 和真正值（sentinel.next）之间，看上去不太值得。但事实上，sentinel node 消除了 special case & 边界情况的存在，长久的降低了代码设计时思考的难度，规避了意想不到的潜在 bug，如上文提到的 addLast() 的空指针问题。josh 说值得，我觉得也是。
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
this.item = i;
this.next = n;
}
}
// use sentinel's item to save size
private IntNode sentinel;
public SLList() {
this.sentinel = new IntNode(0, null);
}
public SLList(int x) {
this();
this.sentinel.item += 1;
this.sentinel.next = new IntNode(x, null);
}
/* add to 1st place */
public void addFirst(int x) {
this.sentinel.item += 1;
this.sentinel.next = new IntNode(x, this.sentinel.next);
}
public int getFirst() {
return this.sentinel.next.item;
}
public void addLast(int x) {
this.sentinel.item += 1;
IntNode p = this.sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
public int getLast() {
IntNode p = this.sentinel.next;
while (p.next != null) {
p = p.next;
}
return p.item;
}
public int size() {
return this.sentinel.item;
}
}