Linked Lists in Java

Notes from Josh Hug's lecture videos.

A linked list is a recursive object that contains a value and the next element in the list, which is another instance of itself.

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

This is really bad, though, and it's a pain for users to use, so we can improve it.

Improving the IntNode

In order to start fixing our IntNode let's build a new class that uses it, SLList.

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

Because we want to hide IntNode from anyone using the SLList class, we have made it private, making it inaccessible to the outside.

It's somewhat better, since there's no more need to, when creating a linked list, specify a null, e.g. new IntNode(6, null).

Let's implement getters and setters for the first item in the list. We'll also nest the IntNode class inside of our SLList. Java supports nested classes!

public class SLList {
    private IntNode first;
    /* We moved our IntNode class to the same file as this one.*/
    private static class IntNode{
        private int item;
        private IntList next;
        public IntList(int item, IntList next){
            this.item = item;
            this.next = next;
        }
    }
    public SLList(int x) {
        first = new IntNode(x, null)
    }
    /* Add a number to the front of the list*/
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
    
    /*Get the first item in the list.*/
    public int getFirst() {
        return first.item;
    }
}

Since there's no need for anything outside of SLList to manipulate an IntNode, we are free to make it private. Since it never uses anything outside of its own class, we can also make it static.

Now there's no more need for users, when constructing lists, to nest a bunch of new IntNode() calls, and they can just use the addFirst method if they want to extend the list.

This is Better	This is Cringe
SLList L = new SLList(3);	IntNode L = new IntNode(9, new IntNode(6, new IntNode(3, null)))
L.addFirst(6);
L.addFirst(9);

Improving the SLList

Now that we've got our basic SLList structure down, we can improve it further by adding more methods for the user.

public class SLList {
    private IntNode first;
    /* Keep track of the size of the list so we don't have to compute it each
    time we want it*/
    private int size = 1;
    private static class IntNode{
        public int item;
        public IntList next;
        public IntList(int item, IntList next){
            this.item = item;
            this.next = next;
        }
    }
    public SLList(int x) {
        first = new IntNode(x, null);
    }
    public void addFirst(int x) {
        first = new IntNode(x, first);
        /*Increment the size of the list by one*/
        size += 1;
    }
    public int getFirst() {
        return first.item;
    }
    /* Adds an item to the end of the list, rather than the beginning.*/
    public void addLast(int x) {
        IntNode temp = first;
        while (temp.next != null) {
            temp = temp.next
        }
        temp.rest = new IntNode(x, null);
        /*Increment the size of the list by one*/
        size += 1;
    }
    /* Instead of recursively computing the size each time we want it, we
    just have a getter for the variable. */
    public int size() {
        return size;
    }
}

The Empty List

Let's add another constructor so that we can account for having an empty SLList.

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

This works fine for everything but `addLast`, because in that method, we try to access the .next of first, which is not going to work because it is null. Let's see how we can fix that.

We can fix the above with a special case, but special cases are cringe. It's better for everything to work in one consistent way.

Sentinel Node

Instead of using a special case, we can represent the empty list using a sentinel node, a special node that is always there.

public class SLList {
    /* The first item of this list is at sentinel.next*/
    private IntNode sentinel;
    private int size = 1;
    private static class IntNode{
        public int item;
        public IntList next;
        public IntList(int item, IntList next){
            this.item = item;
            this.next = next;
        }
    }
    public SLList(int x) {
        sentinel = new IntNode(69, null);
        sentinel.next = new IntNode(x, null)
    }
    /*Our new constructor for an empty list — 69 is a dummy and will never
    be accessed.*/
    public SLList() {
        size = 0;
        sentinel = new IntNode(69, null);
    }
    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }
    public int getFirst() {
        return sentinel.next.item;
    }
    public void addLast(int x) {
        /* Temp will never be null! Thus our problem is solved */
        IntNode temp = sentinel;
        while (temp.next != null) {
            temp = temp.next
        }
        temp.next = new IntNode(x, null);
        size += 1;
    }
    public int size() {
        return size;
    }
}

Because we rewrote our code in this way, we have the following invariants in mind!

• The first item in the linked list will always be at sentinel.next.

• In the addLast method, temp will never be null.

We don't have to write special cases for null anymore.