.. 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 `_ .. _IteratorIntro: Introduction to Iterators [13:14] --------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.3.2.1-IntroToIterators.pdf .. raw:: html Checkpoint 1 ------------ .. avembed:: Exercises/MengBridgeCourse/IteratorsCheckpoint1Summ.html ka :long_name: Checkpoint 1 .. _IteratorInterface: Programming Using the Iterable Interface [4:36] ----------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.3.3.1-Iterable.pdf .. raw:: html Checkpoint 2 ------------ .. avembed:: Exercises/MengBridgeCourse/IteratorsCheckpoint2Summ.html ka :long_name: Checkpoint 2 .. _IteratorProg: Programming Using Iterators [18:02] ----------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.3.4.1-ProgrammingWithIterators.pdf .. raw:: html Checkpoint 3 ------------ .. avembed:: Exercises/MengBridgeCourse/IteratorsCheckpoint3Summ.html ka :long_name: Checkpoint 3 .. _IteratorDesign: Iterator Design Decisions [8:21] -------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.3.5.1-IteratorsDesignConsiderations.pdf .. raw:: html .. admonition:: Clarification Iterators that are a nested class inside the linked structure (not subclasses) are more efficient than Iterators that are independent classes. .. _IteratorInner: 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