LinkedIntList

Traversal
LinkedIntList

Traversal

Managing ListNode references by hand is tedious and tricky. In this lesson, we’ll explore how we can implement a data abstraction so that clients can take advantage of the performance benefits of linked nodes without learning how to manipulate linked nodes. Our goal will be to define a linked list, a list data type based on the linked nodes data structure.

Many list operations such as add, remove, and get depend on accessing particular nodes at a given index in the linked list. Suppose a list contains many nodes whose values we want to print out. 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 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.

This problem is more generally known as traversing the list by examining 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.

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 current reaches the null reference at the end of the list.

LinkedIntList

The LinkedIntList class represents a linked list of integers by maintaining a single ListNode field called front. Let’s implement the toString method as an example. Apply the standard traversal starting from the front of the list but instead of printing out each element, append it to the result string.

public class LinkedIntList {
    private ListNode front;

    public LinkedIntList() {
        front = null;
    }

    // post: Returns a text representation of the list
    public String toString() {
        if (front == null) {
            return "[]";
        } else {
            ListNode current = front;
            String result = "[";
            while (current.next != null) {
                result += current.data + ", ";
                current = current.next;
            }
            result += current.data + "]";
            return result;
        }
    }
}

ArrayIntList kept track of the size of the list as a field. Why is size not needed here?

ArrayIntList.size separated the in-use array indices from the not-in-use array indices.

But in a linked list, each linked node is in use. Each element in a linked list is represented by exactly one ListNode instance. The linked list ends when we hit the null reference at the end of the linked nodes.

LinkedIntList class invariant: The i-th item in the list is always stored in the i-th node from the front.

Before any public method call, the class invariant must hold for external correctness.
In the implementation, the class invariant can be temporarily broken so long as it is later restored.
After any public method call, the class invariant must hold for external correctness.

LinkedIntList

Table of contents

Traversal

LinkedIntList