Review

In class on Friday, we started the task of implementing Java’s LinkedList from scratch. Friday’s class was all about the fundamental building block for the LinkedList called a IntListNode. As a reminder, the IntListNode is defined as

public class IntListNode {
    public int data;
    public IntListNode next;
}

Which we link together by manually by writing code like

public class ListClient {
    public static void main(String[] args) {
        IntListNode list;
        list = new IntListNode();
        list.data = 42;

        list.next = new IntListNode();
        list.next.data = -3;

        list.next.next = new IntListNode();
        list.next.next.data = 17;
    }
}

Which produces a list like the one we saw in class

Constructors

The code is a bit more complicated than necessary because we don’t provide a constructor that just sets the node up with the data desired. To fix this, we can provide a constructor:

public IntListNode(int data) {
    this.data = data;
}

Which then lets us simplify the client code to

public class ListClient {
    public static void main(String[] args) {
        IntListNode list;
        list = new IntListNode(42);

        list.next = new IntListNode(-3);

        list.next.next = new IntListNode(17);
    }
}

We can even simplify this further by providing a constructor that also sets .next for us since we know what we want the .next to be right away. Here is the finalized version of the class and the client method that uses a constructor that takes both an int and IntListNode.

public class IntListNode {
    public int data;
    public IntListNode next;

    public IntListNode() {
        this(0, null);
    }

    public IntListNode(int data) {
        this(data, null);
    }

    public IntListNode(int data, IntListNode next) {
        this.data = data;
        this.next = next;
    }
}

public class ListClient {
    public static void main(String[] args) {
        IntListNode list = new IntListNode(42, new IntListNode(-3, new IntListNode(17)));
    }
}

This just simplifies all the work of having to manually set the .data and .next fields since they are handled by the constructors.

Making IntListNode Code More General

In both classes, students asked is there a better way of handling these nodes without having to write out .next.next.next.... This will be the focus on Wednesday’s class, but we will introduce the concept for the first time here before starting class reviewing this idea.

Consider we had a variable list with many nodes that we wanted to print out each value. We could start by trying to write something like:

System.out.print(list.data + " ");
System.out.print(list.next.data + " ");
System.out.print(list.next.next.data + " ");
System.out.print(list.next.next.next.data + " ");
...

This will never work because we might not know how long this list is beforehand so we won’t know how many print statements to write. Additionally, we might run into a NullPointerException if the list was shorter and went too far down the list with too many .nexts.

Instead, we will need a new approach that somehow traverses the list by looking at each element in turn. (This will be quite similar to how we traverse arrays, but with a few key differences since we don’t have indexes or a defined size for our LinkedIntList.)

Key Idea: Use a local variable that moves through the list. It will keep track of the current node, do some computation (like printing), before moving to the next node.

We will quickly just show the final version code now, and then we will note why it is written this way below. It is okay if this doesn’t make sense now, we just want to expose you to this code pattern before we walk through it on Wednesday.

IntListNode current = list;
while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
}

What is this doing?

current is a variable that stores a reference to the current node we are looking at. It starts out at the front of the list, and on each iteration of the loop gets updated to point to the next node in the list.
We want to stop the loop once we have reached null. It’s okay for current to become null, but we must never say .data or .next on current if it is null.
- One way of thinking about this: inside the loop we say current.data and current.next so we have to make sure current is not null (hence the loop condition).

Here is a gif showing how the variables change throughout the program:

Example exuction of program