CS61B: Lecture 5

Lecture

• We notice that adding to the back of an SLList is much slower than adding to the front.
  • We must traverse through the entire list.
• We must change our data structure so that adding to the end of the list is also fast.
  • One idea is to “cache” the last node, so that we point at the last item in the list.
  • But a better idea is to use a sentinel for the end too. Our last reference could point to either a real node or a sentinel node.
• For the sentinel node, we could add sentinels to both ends of the list, or we can have the sentinel loop back to itself.

Make Our class Generic.

• Specify the generic type only once at the very top of the file.
• In java files, specify the desired type during declaration, and use the empty diamond operator <> during instantiation.
• When instantiating your data structure, we use the reference type rather than the primitive type.

public class SLList<T> {
    private class Node {
        public T item;
        public Node next;
    
        public Node(T i, Node n) {
            item = i;
            next = n;
        }
    }

    private Node sentinel;
    private int size;

    public SLList(T x) {
        sentinel = new Node(null, null);
        sentinel.next = new Node(x, null);
        size = 1;
    }

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

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

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

    public T get(int i) {
        Node dummy = sentinel; 
        while (i > -1 && dummy.next != null) {
            dummy = dummy.next;
            i--;
        }
        return dummy.item;
    }

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

    public int size() {
        return size;
    }
}

SLList<String> L = new SLList<>("love");
L.addFirst("I");
L.addLast("Michelle");
for (int i = 0; i < 3; i++) {
    System.out.println(L.get(i));
}

I
love
Michelle

Arrays

• To store information, we need memory boxes, which are created when declaring variables or instantiating objects.
• Refernce types are allocated 64 bits, while primitives like int (32 bits) vary.
  • When we instantiate an objct, memory voxes are allocated for every attribute stored by that object.
• Arrays are a special kind of object that have a numbered sequence of memory boxes.
  • To get an ith item of an array A[i], use A[i]
  • They do not have named memory boxes like classes.
  • Arrays have a fixed size.
• Arrays have a sequence of N meory boxes where N=length, such that all boxes must hold the same type and thus have the same number of bits.
  • The boxes are numbered based on 0-index.
• Only one reference is created when an array is created, if we reassign all variables containing that reference then we never get the array back.
• Arrays also do not have methods like classes.
  • “It is just a sequence of boxes”

Creating arrays

• Arrays are almost always instantiated with new.
• Three main valid notations:

int[] x = new int[3]; // Every box gets default value of 0
int[] y = new int[]{1,2,3,4,5}; // Implies length is 5
int[] z = {9, 10, 11, 12, 13};
System.out.println(Arrays.toString(z));

[9, 10, 11, 12, 13]

• Two ways to copy arrays;
  • Iterate over items using a loop.
  • Using arraycopy, which takes 5 parameters:
    • Source array,
    • Source start
    • Destination array
    • Destination start
    • How many to copy.

Java 2D arrays

• There are no 2D arrays in Java, only arrays of array references.
• Arrays and Classes are both used to organize memory boxes.
  • Array boxes are accessed using [] notation.
  • Class boxes are accessed using dot notation.
  • Array boces must be of the same type.
  • Class boxes may be of different types.
  • Both have a fixed number of boxes.