Discussion 9 handout

Objectives

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:

Enhanced for-loop
for (T x : xs) {
    // LOOP BODY
}
Transformed while-loop
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:

Iterable
/** 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();
}
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

Download CNode.java and add it to a new project in IDEA.

In IDEA, create class CNodeIterator implementing Iterator<T>, add your proposed fields, and write a constructor. Leverage IDEA’s hints to create stubs for hasNext() and next().

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.

Part 5: Iterable

Modify CNode.java so that it implements Iterable<T>, returning a new CNodeIterator that will yield that node’s value first.

Test your implementation by uncommenting the main() method in CNode.java.

Submission

  1. Open the assignment page for “Discussion activity 9” in CMSX
  2. [Recorder] Find the “Group Management” section and invite each group member
  3. [Others] Refresh the page and accept your invitation
  4. [Recorder] Take a picture of your work and save as either a JPEG or a PDF file named “discussion_responses”. After all invitations have been accepted, upload your picture as your group’s submission.
    • Recommended scanning apps: Microsoft Office Lens, Adobe Scan, Genius Scan, Evernote Scannable

Ensure that your group is formed and your work submitted before the Friday evening deadline.

Tips and reminders