Discussion 6 handout

Group members (names & NetIDs)

Objectives

• Process circular linked lists
• Implement the Iterator design pattern

Warmup: Circular linked list processing

Recall how we designed a generic class to represent linked-list nodes:

/** A node in a linked list. */
Node<T> {
    /** The value at this location in the list. */
    T value;

    /** The node after this one in the list; may be null. */
    Node<T> next;
}

Given a starting (“head”) node, you can process all elements in a linear linked list by advancing a “current node” variable to its next field until it is null. But in a circular linked list, the next field is never null; instead, the last node points back to the head node (we are assuming that the head node is on the circular portion—no “loops with tails”).

Write a loop to call a function process(String v) for every String value in a circular linked list whose head node (a Node<String>) is pointed to by a variable head.

Reference: Iteration using Iterators

If the type of the variable (or expression) xs implements Iterable<T>, then Java’s enhanced for-loop serves as “syntactic sugar,” transforming itself into a while-loop as follows:

for (T x : xs) {
    // LOOP BODY
}

Iterator<T> it = xs.iterator();
while (it.hasNext()) {
    T x = it.next();
    // LOOP BODY
}

Two interfaces play a role in telling the compiler when this is possible:

/** Implementing this interface allows an object to
 *  be the target of the enhanced for statement. */
interface Iterable<T> {
    /** Returns an iterator over elements. */
    Iterator<T> iterator();
}

package java.util;

/** An iterator over a collection. */
interface Iterator<T> {
    /** Returns true if the iteration has more elements. */
    boolean hasNext();

    /** Returns the next element in the iteration.
     *  Effects: advances this iterator to the next element. */
    T next();
}

Task: Iterator for circular linked list

Our goal is to be able to write the following as a solution to the warmup exercise (wouldn’t this have made things easier for you in the client role?):

// `head` is a CNode<String>
for (String v : head) {
    process(v);
}

It should work for both linear and circular linked lists (we’ve renamed the node class to CNode to emphasize this possibility).

Part 1: Iterator design

We will need an implementation of Iterator<T>; let’s write a new class CNodeIterator<T> to serve that role. In order to perform its duties (yielding the next element and knowing when it’s done), it will need to store some state. Identify (and write specifications for) some fields that will help CNodeIterator do its job.

Part 2: Iterator definition

Please download dis06-release.zip, extract it to a known location on your computer, and open it as a project in IDEA.

Add your proposed fields to CNodeIterator and write a constructor.

Part 3: Iterator hasNext

Implement the hasNext() method (look at the loop guard from your warmup solution for inspiration). Trace execution on a circular list of size 1 to check your logic.

Part 4: Iterator next

Implement the next() method. Don’t forget about the throws clause.