Home ListNode manipulation

In CSE 143, we spend a fair amount of time learning how to implement and manipulate a singly linked list – a kind of linked lists where each node references only the subsequent node. This is in contrast to doubly linked lists, where each node references both the previous and next nodes in the list.

Since we use singly linked lists, note that it is not possible to go "backwards" when looking at a certain node.

public void test() {
    ListNode target = this.head;
    while (target != null) {
        if (matchesCondition(target)) {
            // How can we get the previous node here?
        }
        target = target.next;
    }
}

There are a number of ways to get around this issue, some ugly, and some clean. One relatively clean approach is to look for the previous node while looping forward:

public void test() {
    ListNode previous = this.head;
    while (previous != null && previous.next != null) {
        if (matchesCondition(previous.next)) {
            // We can easily access both the target node and the previous node here.
            ListNode target = previous.next;
        }
        previous = previous.next;
    }
}

In this class, we want to make sure you understand how to work with references and how to manipulate ListNodes.

So, to prevent you from working around the problem by solving something easier, you may not modify the data field of any ListNode or ListNode-like object.

Likewise, you should construct new ListNode objects to the minimum – that is, do new ListNode(n) only when you must literally add a new item to your list.

However, you may construct as many ListNode references as you want &dnash; as many variables that refer to ListNode objects as you want. Some exam problems will restrict the number of references you may use, but there is no such restriction for homework assignments.

To clarify the difference between creating a new ListNode vs a reference to a ListNode, consider the following:

// Creates a reference named 'a',
// and a new ListNode containing 1
ListNode a = new ListNode(1);

// Creates a reference named 'b',
// and a new ListNode containing 2
ListNode b = new ListNode(2);

// Creates a reference named 'c'
// that refers to nothing
ListNode c = null

// Creates a reference named 'd'
// that refers to the same ListNode
// that 'a' refers to
ListNode d = a;

In this example, we've created four references (the variables 'a', 'b', 'c', and 'd') and two new ListNode objects.

Sometimes, you will need a "placeholder" reference or some sort of "default" value when searching for a ListNode. For example, suppose we want to save a reference to the ListNode containing the number 42 and do something with that ListNode while printing out all ListNodes in the list. Naively, we might try doing this:

ListNode target;
ListNode current = this.front;
while (current != null) {
    if (current.data == 42) {
        target = current;
    }
    System.out.println(current.data);
    current = current.next
}
// do something with target

However, this code won't compile! The first line will fail to compile because we didn't assign a value to that variable.

Naively, we might try assigning some sort of "default" value like so:

ListNode target = new ListNode(0);  // default?
ListNode current = this.front;
while (current != null) {
    if (current.data == 42) {
        target = current;
    }
    System.out.println(current.data);
    current = current.next
}
// do something with target

However, this is also bad because we've ended up creating an unnecessary ListNode. Instead, you should use null as the "default" value:

ListNode target = null;  // default
ListNode current = this.front;
while (current != null) {
    if (current.data == 42) {
        target = current;
    }
    System.out.println(current.data);
    current = current.next
}
// do something with target

You will occasionally encounter instructor-provided code that marks some field or variable as final. One common example of this is ListNodes:

public class ListNode {
    public final int data;
    public ListNode next;

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

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

When a field is marked as final, Java will produce an error during compilation-time if you try and write code that changes that field.

You should not try and circumvent this by removing the final keyword. When we mark something as final or otherwise prevent you from modifying something, it is because we feel you would learn more from working under that restriction then you would have otherwise.

For example, the reason we mark the data field in ListNode objects is because one of the major reasons why we cover ListNode problems is to give you practice in working with and manipulating references. Allowing you to just change the data field would end up side-stepping the lesson we want to teach.