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

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

In IntelliJ, create class CNodeIterator implementing Iterator<T>, add your proposed fields, and write a constructor. Leverage IntelliJ’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 6” 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 along with your code 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

• Discussion is not a race. Focus on the current activity being facilitated by your TA and engage your whole group to propose and explain ideas.
• Elect a recorder to maintain the “master” copy of your work (others are still encouraged to jot down ideas on scratch paper). Rotate this position each week.
• It is a violation of academic integrity to credit someone for work if they were not present when the work was done, and the whole group is accountable. Your CMS group must only include classmates who attended section with you on that day. Remember that our participation policies accommodate occasional absences without penalty.
• It is your individual responsibility to ensure that you are grouped on CMS and that your group’s work is submitted before the deadline. Log into CMS the day after section to ensure that everything is in order, and contact your groupmates if not. It would be prudent for multiple members to photograph the group’s work.
• Only one group member (typically the recorder) needs to upload a submission. But their submission must not be uploaded until after all group members have confirmed their membership in CMS (contact your TA if you have trouble grouping in CMS).

Challenge problem

If your entire group finishes early and are looking for more practice with this material, try completing this additional task. To be clear, we are not expecting anyone to submit work on challenge problems to CMSX, nor will your TA have time to discuss them in section. But you are welcome to discuss them on Ed or to bring questions and ideas to office hours.

Read about nested classes in Java, then reimplement CNodeIterator as an inner class within CNode. Your iterator class should have one fewer (explicit) field than before.