CS61B: Lecture 4

Lecture

Beauracracy

• Although the IntList is a functional list, we can improve it by hiding some of the abstraction object.
  • We will make it so that someone with no recursion would know how to make it. We want to hide away the recursive structure.
  • In other words, SLList will add an abstraction barrier that will handle all the base logic for manipulating the list, without the enduser knowing how the list works. This simplifies thinking about the list as an object.
• We now make a singular node from our IntList. This represents a single element in our old list.

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

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

• Now we can make our SLList that utilizes the IntNode objects and classes to make a list.

public class SLList {
    public IntNode first;

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

• The advantage of this is that now the SLList is easier to instantiate with a value. We do not need to specify a next value.
• If we want to make an addFirst method, we can simply mimic what we did before for an IntList, and add that to our class. We can also create a getFirst method to grab the first element with similar logic.

public void addFirst(int x) {
    first = new IntNode(x, first);
} 

public int getFirst() {
    return first.item;
}

Access Control

• However, with our current implementation, we also run the risk that the user may try to bypass the protections that we have set up in the abstraction barrier. They might try to tamper with the internal components of SLList itself.
  • We can prevent this by making attributes that we want to hide (such as first) private.
  • This enforces an abstraction barrier in Java.
  • Now users cannot use the first attribute in SLList to create an unintended list, such as an infinite cycle.

public class SLList {
    private IntNode first;
    ...
}

• This makes sure that the compiler would not compile any details beyond the abstraction barrier we set up.
  • Private hides implementation details from class users. It also means there is less for users to understand, and also makes it safer for us to change private methods.
• We may also nest classes within each other, and make the entirety of the IntNode class a private class. This adds futher baby proofing.
  • we may also use the static keyword for the IntNode class to protect it from accessing any instance attributes of SLList.
  • The static keyword then saves a little overhead memory, as now IntNode does not need to contain a reference to any other SLList instance.

    public class SLList {
      private static class IntNode {
      public int item;
      public IntNode next;
    
      public IntNode(int i, IntNode n) {
          item = i;
          next = n;
      }
      }
      ...
    }
    

More features

• We now want to migrate over the other features we had for IntList. We may keep a similar implementation for these features.
• addLast(int x)

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

• size()
  • For this we use a design pattern. To create a recursive algorithm in a structre that is not recursive itself, we make a private recursive helper function that calculates the size for us. ```java private int size(IntNode p) { if (p == null) { return 0; } return 1 + size(p.next); }

public int size() { return size(first); }

- However, we may make this quicker.
## Caching
- We may cache the overall size of the list at it's creation or when any methods are called.
- This turns the size function from a linear time operation to a constant time operation.
    - This comes at smaller costs though, we allocate more memory to store the size, and also slightly more time to perform other operations as we manipulate size itself.
- We can do this because SSList acts as a middle man for the user to interact with the list made of IntNodes. So this middle man can store metadata for us such as size.

## Representing the Empty List
- To allow the creation of an empty list, we write a constructor for instantiating an empty list.


```java
public SLList() {
    first = null;
    size = 0;
}

• However, this introduces a new bug. If we try to run addLast() then we get a NullPointerException because we try to access the next node of null which doesn’t exist.
  • An easy fix is to add an edge case.

public void addLast(int x) {
    if (first == null) {
        addFirst(x);
    }
    IntNode dummy = first;
    while (dummy.next != null) {
        dummy = dummy.next
    }
    dummy.next = new IntNode(x);
    size+=1;
}

Sentinel Node

• Although adding a special case works, adding them introduces a special case, which an introduce a lot of complexity.
  • A linear structure like a linked list may have no special cases, but a tree strucutre may have many many many special cases.
• Our fundamental problem right now is that the empty list has a null first, so first.next does not exist.
• To avoid this case we want to make all lists equal, including empty lists.
  • Thus, we want to create a special node that is always there.
• Every SLList will have this special sentinel node, so sentinel.next is always accessible.
• The sentinel node is an invariant, which is something that is always guaranteed to be true during code generation.

public class SLList {
    private static class IntNode {
        public int item;
        public IntNode next;

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

    // The sentinel node is the dummy node at the front of the list,
    // and the real node is the node that comes after the sentinel node
    private IntNode sentinel;
    private int size;

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

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

    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size+=1;
    }

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

    public int getFirst() {
        return sentinel.next.item;
    }

    public int size() {
        return size;
    }
}