CS61B 2018 Lecture 4 SLLists, Nested Classes, Sentinel Nodes

[poanc]

Summary

• From IntList to SLList
  • Improvement 1: Rebranding
  • Improvement 2: Bureaucracy
  • addFirst and getFirst
  • Improvement 3: Access Control (Public vs. Private)
  • Improvement 4: Nested Classes
  • addLast() and size()
  • Improvement 5: Caching
  • Improvement 6: The Empty List
  • Improvement 6b: Sentinel Nodes
  • Invariants

From IntList to SLList

Improvement 1: Rebranding

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

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

Improvement 2: Bureaucracy

/** An SLList is a list of integers, which hides the terrible truth of the nakedness within */
public class SLList {
    public IntNode first;

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

    public static main (String[] args){
        SLList L = new SLList(10);
    }
}

這樣一來，就可以不用輸入null作為argument
可以和之前宣告IntList的方式比較，不用多一個null，使可讀性增加

IntList L1 = new IntList(5, null);
SLList L2  = new SLList(5);

addFirst and 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);
    }

    /** Return the first item in the list */
    public int getFirst(){
        return first.item;
    }
}

Improvement 3: Access Control (Public vs. Private)

然而，我們想要限制使用者取用一些變數

我們可以使用private，讓使用者只能在當下的class，才能使用private variable or method

Improvement 4: Nested Classes

像是IntNode和SLList是有相關聯的(IntNode屬於SLList的子集)，我們可以把 class IntNode 放在SLList之下，好處就是看起來比較有結構性。
(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.)

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

PS: if external class won't be able to use the IntNode class, then set the IntNode class to private

static nested class

如果IntNode class不會用到SLList class的properties and methods(outter class stuff or detail)，可以設成static，這個static class就不會向外去找資源，節省記憶體空間。
(This saves a bit of memory, because each IntNode no longer needs to keep track of how to access its enclosing SLList.)

addLast() and size()

addLast()

1. my solution 1 addLast()：why is wrong？

    public void addLast(int x){
        IntNode ptr = first; 
        if(ptr == null){
            ptr = new IntNode(x, null);
        }else{
            ptr = ptr.next;
            while(ptr.next != null){
                ptr = ptr.next;
            }
            ptr = new IntNode(x, null);
        }
    }

Ans：仔細看while loop的條件多跨了一個node，所以會少迭代到一個node。此外，ptr = new IntNode(x, null)會和原本的IntNode失去關聯。

2. my solution 2 addLast()：why is wrong？

    public void addLast(int x){
        IntNode ptr = first; 
        while(ptr != null){
            ptr = ptr.next; 
        }
        ptr = new IntNode(x, null);
    }

Ans：跑完while loop的ptr，是一個variable，存著指向null的reference，已經沒有操作到IntNode

3. Correct solution：

    public void addLast(int x){
        IntNode ptr = first; 
        while(ptr.next != null){
            ptr = ptr.next; 
        }
        ptr.next = new IntNode(x, null);
    }

size()

因為SLList有middle man，使用recursion會有一些限制。下面的方法是java 常用的pattern，Josh稱private的那個method為God method，還蠻貼切的xd

The recursive call for size in IntList was straightforward: return 1 + this.rest.size(). For a SLList, this approach does not make sense. A SLList has no rest variable. Instead, we'll use a common pattern that is used with middleman classes like SLList -- we'll create a private helper method that interacts with the underlying naked recursive data structure.

    private static int size(IntNode ptr){
        if(ptr.next == null){
            return 1;
        }
        return 1 + size(ptr.next);
    }
    public int size(){
        return size(first);
        
    }

Here, we have two methods, both named size. This is allowed in Java, since they have different parameters. We say that two methods with the same name but different signatures are overloaded. For more on overloaded methods, see Java's official documentation.

Improvement 5: Caching

然而，當我們的SLList很長的時候，要計算size大小，會花很多時間。有沒有更快的作法？
我們可以利用 caching 才儲存，

(To do so, we can simply add a size variable to the SLList class that tracks the current size, yielding the code below. This practice of saving important data to speed up retrieval is sometimes known as caching.)

public class SLList {
    ... /* IntNode declaration omitted. */
    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;
    }
    ...
}

這樣的作法，雖然會讓addFirst()和addLast變慢，但是這樣的tradeoff是值得的。
(This modification makes our size method incredibly fast, no matter how large the list. Of course, it will also slow down our addFirst and addLast methods, and also increase the memory of usage of our class, but only by a trivial amount. In this case, the tradeoff is clearly in favor of creating a cache for size.)

在java，SLList是很常用的pattern，用object來管理variable和method，可以更有organization。

Improvement 6: The Empty List

Unfortunately, this causes our addLast method to crash if we insert into an empty list. Since first is null, the attempt to access p.next in while (p.next != null) below causes a null pointer exception.

/** Original addLast method */
    public void addLast(int x){
        size += 1;
        IntNode ptr = first; 
        while(ptr.next != null){
            ptr = ptr.next; 
        }
        ptr.next = new IntNode(x, null);
        
    }

/** Fixed addLast method */
    public void addLast(int x){
        size += 1;
        if(first == null){
            first = new IntNode(x, null);
            return;
        }
        
        IntNode ptr = first; 
        while(ptr.next != null){
            ptr = ptr.next; 
        }
        ptr.next = new IntNode(x, null);
        
    }

Improvement 6b: Sentinel Nodes

像是empty SLList這種special case是會很常有的，但是我們需要讓code有一致性，即使是empty SLList，也要有“相同“的結果。
Like the code above, this solution works, but special case code like that shown above should be avoided when necessary. Human beings only have so much working memory, and thus we want to keep complexity under control wherever possible. For a simple data structure like the SLList, the number of special cases is small. More complicated data structures like trees can get much, much uglier.

A cleaner, though less obvious solution, is to make it so that all SLLists are the "same", even if they are empty. We can do this by creating a special node that is always there, which we will call a sentinel node. The sentinel node will hold a value, which we won't care about.

public class SLList {
    ... /* IntNode declaration omitted. */
    public IntNode sentinel;
    private int size;

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

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

Invariants

An invariant is a fact about a data structure that is guaranteed to be true (assuming there are no bugs in your code).
A SLList with a sentinel node has at least the following invariants:

• The sentinel reference always points to a sentinel node.
• The front item (if it exists), is always at sentinel.next.item.
  • The size variable is always the total number of items that have been added.

Summary

Methods	Non-Obvious Improvements
addFirst(int x)	1 Rebranding: IntList → IntNode
getFirst	2 Bureaucracy: SLList
size	3 Access Control: public → private
addLast(int x)	4 Nested Class: Bringing IntNode into SLList
	5 Caching: Saving size as an int.
	6 Generalizing: Adding a sentinel node to allow representation of the empty list.