.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :author: Molly Domino Iterators ========= Objectives ---------- Upon completion of this module, students will be able to: * Describe the purpose and use of an Iterator * Implement Iterators using the Iterator and Iterable Interfaces * Design and develop algorithms that use Iterators and Iterator methods Suggested Reading ~~~~~~~~~~~~~~~~~ Java Interlude 5 Iterators from `Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry `_ Introduction to Iterators ------------------------- [13:14] Introduction to Iterators ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html .. raw:: html

Video Slides 11.3.2.1-IntroToIterators.pdf Checkpoint 1 ------------ .. avembed:: Exercises/SWDesignAndDataStructs/IteratorsCheckpoint1Summ.html ka :long_name: Checkpoint 1 Programming Using the Iterable Interface ---------------------------------------- [4:36] Programming Using the Iterable Interface ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html .. raw:: html

Video Slides 11.3.3.1-Iterable.pdf Checkpoint 2 ~~~~~~~~~~~~ .. avembed:: Exercises/SWDesignAndDataStructs/IteratorsCheckpoint2Summ.html ka :long_name: Checkpoint 2 Programming Using Iterators --------------------------- [18:02] Programming Using Iterators ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html .. raw:: html

Video Slides 11.3.4.1-ProgrammingWithIterators.pdf Checkpoint 3 ~~~~~~~~~~~~ .. avembed:: Exercises/SWDesignAndDataStructs/IteratorsCheckpoint3Summ.html ka :long_name: Checkpoint 3 Iterator Design Decisions ------------------------- [8:21] Iterator Design Decisions ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. raw:: html .. raw:: html

Video Slides11.3.5.1-IteratorsDesignConsiderations.pdf .. admonition:: Clarification Iterators that are a nested class inside the linked structure (not subclasses) are more efficient than Iterators that are independent classes. Inner Iterator for ex11.3-Iterator ---------------------------------- As discussed throughout this section there are various design approaches for iterators. Below is one example of how an inner Iterator class could be implemented for ex11.3-Iterator. Include a public method to make the iterator object available: .. code-block:: java /** * Iterator method creates Iterator object * * @return new Iterator object */ public Iterator iterator() { return new LListIterator(); } Include an inner Iterator class. This version does not provide remove functionality as it is complicated with a singly linked list to keep track of the previous nodes in order to remove the current node. .. code-block:: java private class LListIterator implements Iterator { private Node next; private boolean newCurr; /** * Creates a new DLListIterator */ public LListIterator() { next = firstNode; newCurr = false; } /** * Checks if there are more elements in the list * * @return true if there are more elements in the list */ @Override public boolean hasNext() { return (next != null); } /** * Gets the next value in the list * * @return the next value * @throws NoSuchElementException * if there are no nodes left in the list */ @Override public T next() { if (next == null) { throw new NoSuchElementException("No nodes left in the list."); } T value = next.data; next = next.getNext(); newCurr = true; return value; } } A version of an inner Iterator class which does provide remove functionality. It is best to only provide remove functionality through either the data structure or the iterator in order to avoid unintended side effects. .. code-block:: java private class LListIterator implements Iterator { private Node prev; private Node curr; private Node next; private boolean newCurr; /** * Creates a new DLListIterator */ public LListIterator() { prev = null; curr = null; next = firstNode; newCurr = false; } /** * Checks if there are more elements in the list * * @return true if there are more elements in the list */ @Override public boolean hasNext() { return (next != null); } /** * Gets the next value in the list * * @return the next value * @throws NoSuchElementException * if there are no nodes left in the list */ @Override public T next() { prev = curr; curr = next; next = next.getNext(); if (curr == null) { throw new NoSuchElementException("No nodes left in the list."); } newCurr = true; return curr.data; } /** * Removes the last object returned with next() from the list * * @throws IllegalStateException * if next has not been called yet * and if the element has already been removed */ @Override public void remove() { if (next == firstNode) { throw new IllegalStateException( "Next has not been called yet."); } else if (!newCurr) { throw new IllegalStateException( "The Element has already been removed."); } else if (curr == firstNode) { firstNode = next; curr = null; } else { prev.setNext(curr.getNext()); curr = prev; //this code that updates prev is not necessary //because next() must be called before another remove() //and that will update prev, saving this O(n) operation //prev = firstNode; //while ((prev != null) && (prev.getNext() != curr)){ // prev = prev.getNext(); //} } numberOfEntries--; newCurr = false; } } Programming Practice: Iterators ------------------------------- .. extrtoolembed:: 'Programming Practice: Iterators' :workout_id: 1924