LinkedIntList and loops
Table of contents
Review
In the previous lesson, we introduced the ListNode class, a fundamental building block for LinkedIntList.
Implementer
public class ListNode {
public int data;
public ListNode next;
}
We also saw how to create integer sequences by creating and connecting multiple ListNode instances.
Implementer
ListNode list;
list = new ListNode();
list.data = 42;
list.next = new ListNode();
list.next.data = -3;
list.next.next = new ListNode();
list.next.next.data = 17;
Traversal
Creating new ListNode instances by hand is very tedious. Let’s automate some of the work of creating a sequence of ListNode instances by combining them with loops.
Suppose we have a variable list with many nodes that we want to print out. We could start by trying to write something like:
Implementer
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 code is quite brittle: it only works if the number of print statements is exactly the same as the size of the list.
What happens if the number of print statements is greater than the size of the list?
Eventually, one of the list...next fields will be null, representing the end of the list. Java will throw a NullPointerException when the code attempts to access the data field of that null reference.
Instead, we will need a new approach that traverses the list by looking at each element one at a time.
- Standard traversal for linked lists
- Use a local variable to traverse the list. At each
ListNode, perform some computation (like printing) before moving to the next node.
Implementer
ListNode current = list;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
current is the variable whose value is a reference to the current node. It begins at the front of the list. At the end of each iteration of the loop, current is reassigned to the next node in the list.
The loop ends when we reach null. We need to perform this check since the code inside of the loop requires access to current.data and current.next, which will only work if current is not null.
LinkedIntList class
Like ArrayIntList, the purpose of the LinkedIntList class is to provide a seamless implementation of a list of integers. ArrayIntList achieved this by maintaining an internal elementData array and size field to represent the data contained in the list ADT. We’ll see how we can achieve this result by maintaining ListNode instances instead of an array. The client should ultimately be able to write code that uses the LinkedIntList without knowing any of the implementation, just as we were able to use Java’s LinkedList class without knowing anything about nodes.
The LinkedIntList class maintains a single ListNode field, front.
Implementer
public class LinkedIntList {
private ListNode front;
public LinkedIntList() {
front = null;
}
}
In ArrayIntList, we kept track of the size as a field. Why is size not necessary here?
size is not necessary for LinkedIntList since each element of the sequence will have its own ListNode instance. The list ends when we hit the null pointer at the end of the sequence. As a rule, we’ll make sure that every ListNode in the LinkedIntList represents one element in the list ADT.
How might we implement the print method for LinkedIntList? We can use the standard traversal, but modify it so that current starts from the front of the LinkedIntList.
Implementer
public class LinkedIntList {
private ListNode front;
public LinkedIntList() {
front = null;
}
public void print() {
ListNode current = front;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
For the rest of this lesson, we’ll focus on implementing the add method.