Lists

We can construct a very basic linked list of integers:

public class IntList {
    int first;
    IntList rest;

    public IntList(int first, IntList rest) {
        this.first = first;
        this.rest = rest;
    }

    /** Return the number of ints in this list. */
    public int size() {
        if (rest == null) {
            return 1;
        }
        return rest.size() + 1;
    }

    /** Returns the int at index i. */
    public int get(int i) {
        if (i == 0) {
            return this.first;
        }
        return rest.get(i - 1);
    }

    /** Return a new list with the same ints, but incremented by 1. */
    public IntList incrementRecursiveNonDestructive() {
        IntList newRest = null;
        if (rest != null) {
            newRest = rest.incrementRecursiveNonDestructive();
        }
        return new IntList(first + 1, newRest);
    }

    public static void main() {
        IntList myList = new IntList(67, null);
        myList.rest = new IntList(6, null);
        myList.rest = new IntList(7, null);
    }
}

The implementation of an IntList is simple, but it takes a lot of effort to go through and index elements. Additionally, when we are creating new elements in our list, we have to know the implementation of the list itself: the linked list structure.

An SLList is similar to an IntList, but we abstract away the linked list structure by wrapping our list class around a system of nodes:

public class IntNode {
    int item;
    IntNode next;

    public IntNode(int item, IntNode next) {
        this.item = item;
        this.next = next;
    }
}

Then we can create methods that use these nodes:

public class SLList {
    IntNode first;
    int size;

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

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

    /** Adds x to the end of this list. */
    public void addLast(int x) {
        size += 1;
        // special case: null pointer when list is empty
        if (first == null) {
            first = new IntNode(x, null);
            return;
        }
        IntNode current = first;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new IntNode(x, null);
    }

    public static int get(IntNode node, int i) {
        if (i == 0) {
            return node.item;
        }
        return get(node.next, i - 1);
    }

    /** Return the int at index i in the list. */
    public int get(int i) {
        get(first, i);
    }
}

Notice that we have a special case that we have to remember when we implement addLast: it fails if the list is empty, so we need to first check if it is null or not.

In order to remove this special case, we can add a sentinel node that is always there, regardless of whether the list is empty or not. This means that first will never be null:

IntNode sentinel;

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

public SLList(int first) {
    this.sentinel = new IntNode(0, null);
    sentinel.next = new IntNode(first, null);
    size = 1;
}

And we would have to change all the other methods to take into account this sentinel node.