week2 2.2 notes

cs61b ucberkeley JoshHug

2.2 Lectures include SLLists, Nested Classes, Sentinel Nodes

Adding addLast(int x) and size() methods to SLList.java

implement the addLast method iteratively, though you could also do it recursively. The idea is fairly straightforward, we create a pointer variable p and have it iterate through the list to the end.

/** Adds an item to the end of the list. */
public void addLast(int x) {
    IntNode p = first;
    /* Advance p to the end of the list. */
    while (p.next != null) {
        p = p.next;
    }
    p.next = new IntNode(x, null);
}

a recursive implementation of size is especially encouraged.

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

Try to get to be familiar with recursive and iterative inplementation.

Having a size method that is very slow for large lists is unacceptable, since we can do better.It is possible to rewrite size so that it takes the same amount of time, no matter how large the list.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 {
    private IntNode first;
    private int size;
    public SLList(int x) {
      first = new IntNode(x, null);
    }
    public void addFirst(int x){
      first = new IntNode(x,first);
      size += 1;
    }
    public int getFirst(){
        return first.item;
    }
    public void addLast(int x){
        size += 1;
        IntNode p = first;
        while(p.next != null){
            p = p.next;
        }
        p.next = new IntNode(x, null);
    }
    public int size(){
      return size;
    }
}

Sentinel Nodes

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.
One solution to fix addLast is to create a special case for the empty list, as shown below:

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

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.

For example, the empty list created by SList L = new SList() would be as shown below:

And an SLList with the items 5, 10, and 15 would look like:

In the figures above, the lavender ?? value indicates that we don't care what value is there. Since Java does not allow us to fill in an integer with question marks, we just pick some abitrary value like -518273 or 63 or anything else.
Since an SSList without a sentinel has no special cases, we can simply delete the special case from our addLast method, yielding:

public void addLast(int x) {
    size += 1;
    IntNode p = sentinel;
    while (p.next != null) {
        p = p.next;
    }
    p.next = new IntNode(x, null);
}