CS61B(5): SLLists, Nested Classes, Sentinel Nodes

Posted on | In , |

This is the lecture note of CS61B - Lecture 5.

Review the IntList we implemented in lecture 4. We call it "naked linked list".

1
2
3
4
5
6
7
8
9
10
11
public class IntList {
    public int first;
    public IntList rest;

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

    // ...
}

While it works, the above “naked” linked lists are hard to use.

Inspired by our experience with the IntList, we'll now build a new class called SLList, which much more closely resembles the list implementations that programmers use in modern languages. We'll do so by iteratively adding a sequence of improvements.

Improvement 1: Rebranding and culling

Firstly, rename the IntList class as IntNode and remove all methods except the constructor.

1
2
3
4
5
6
7
8
9
public class IntNode {
    public int item;
    public IntNode next;

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

Then, create a class called SLList. Let IntNode be its instance variable, and add "addFirst" and "getFirst" methods to it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/** 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);
    }

    /** Adds x to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }

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

    public static void main(String[] args) {
        SLList L = new SLList(15);  // creates a list of one integer, namely 15
        L.addFirst(10);
        L.addFirst(5);

        System.out.println(L.getFirst());  // 5
    }
}

Until now, I bet you have already realized what's the strength of SLList - it is easier to instantiate and use.

Actually, it is the data structure that makes it easier to use.

Improvement 2: The private Keyword

However, the above implementation has some flaws. One of them is the abuse of public. For example, users of this class might to do some unexpected operations, like this:

1
2
3
SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;

We can prevent programmers from making such mistakes with the private keyword. The private keyword restricts access. It prevents code in other classes from using members (or constructors) of a class.

1
2
3
4
5
6
7
8
9
public class SLList {
    private IntNode first;  // public --> private

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

    // ...
}

Improvement 3: Nested Classes

The IntNode class doesn't stand on its own, and is obviously subordinate to SLList. We can make it as a nested class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SLList {
    // nested class
    private static 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);
   } 
   
   // ...
}

Here, we use private and static modifier.

  • private: if other external classes never use the nested class, declare it private
  • static: if the nested class never uses any instance variables or methods of the outer class, declare it static (results in a minor savings of memory)

Improvement 4: Recursive private helper Methods

To motivate our remaining improvements, and to give more functionality to our SLList class, let's add .addLast and .size methods.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/** Adds an item to the end of the list. */
public void addLast(int x) {
    IntNode p = first;

    while (p.next != null) {
        p = p.next;
    }

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

/** Returns the size of list using ... recursion! */
public int size() {
    /* 
    the following code will cause error, since IntNode doesn't has the size method.
    So we need a helper method.

    IntNode p = first;
    if (p == null) {
        return 0;
    }
    return 1 + p.next.size();
    */

    return size(first);
}

// helper method
/** Returns the size of the list starting at IntNode p. */
private static int size(IntNode p) {
    if (p == null) {
        return 0;
    } 
    return 1 + size(p.next);
}

/** Returns the size of list using ... iteration! */
public int iterativeSize() {
    int totalSize = 0;
    IntNode p = first;

    while (p != null) {
        totalSize += 1;
        p = p.next;
    }

    return totalSize;
}

You may notice we have two .size methods. They have the same function name, but one has parmaters while another does not have. We call it Overload.

Improvement 5: Caching

There are some issues of addLast and size methods - both of them are pretty slow.

Can you figure out why?

This is becauses we need to traverse the whole linked-list.

In this lecture, we will focus on modifying size method so that the execution time of it is always fast. In the next lecture, we will get inspiration for quick addLast method.

Our solution is maintaining a special size variable that caches the size of the list. With this improvement, the execution time of size() method is independent of the size of the list.

Caching: putting aside data to speed up retrieval.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class SLList {
    private static class IntNode {
        public int item;
        public IntNode next;
    
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }
    
    private IntNode first;
    // cache
    private int size;

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

    /** Adds x to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
        size += 1;
    }

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

    /** Adds an item to the end of the list. */
    public void addLast(int x) {
        IntNode p = first;

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

        size += 1;
    }

    /** Returns the size of list. */
    public int size() {
        return size;
    }
}

Improvement 6: Sentinel Nodes

Let's add a new constructor so that we can represent empty SLList.

1
2
3
4
5
6
7
// add a new constructor

/** Creates an empty SLList. */
public SLList() {
    size = 0;
    first = null;
}

It Seems pretty good, right?

Well, actually there is a subtle bug, can you find it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// If you create an empty SLList, then using addLast method, the code will crash.

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

    while (p.next != null) {  // Error: first is null and doesn't have .next
        p = p.next;
    }
    p.next = new IntNode(x, null);
}

/**
public static void main(String[] args) {
    SLList8 L = new SLList8();

    L.addLast(20);
    L.addLastIteration(25);

    System.out.println(L.size());
}
*/

Let's do our last improvement of SLList to fix this bug.

Naive Solution

One possible solution is adding a special case for the empty list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void addLast(int x) {
  size += 1;

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

In this case, it's ok. But in some other complex cases, such as tree data structure, it will cause vast amount of complexity, and make the code ugly. 🤮

There is a better way!

Sentinel Solution

We avoid special cases by making all SLLists (even empty) the same!

The following is our final implementation of SLList.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/** An SLList is a list of integers, which hides the terrible
 * truth of the nakedness within.
 */
public class SLList {
    // nested class
    private static class IntNode {
        // attention: inner class should have private members
        private int item;
        private IntNode next;
    
        private IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }
    
    /* The first item (if it exits) is always at sentinel.next ... invariants */
    private IntNode sentinel;  // rename first to be sentinel
    private int size;

    /** Creates an empty SLList. */
    public SLList() {
        size = 0;

        // sentinel node’s item needs to be an integer, 
        // but doesn’t matter what value we pick.
        sentinel = new IntNode(-1, null);
    }

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

    /** Adds x to the front of the list. */
    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }

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

    /** Adds an item to the end of the list. */
    public void addLast(int x) {
        IntNode p = sentinel;

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

        size += 1;
    }

    /** Returns the size of list using ... recursion! */
    public int size() {
        return size;
    }
}

Invariants