Analysis of Algorithms

Analysis of Algorithms

Iterators and Sequences 2010 Goodrich, Tamassia Iterators and Sequences 1 Iterators An iterator abstracts the process of scanning through a collection of elements It maintains a cursor that sits between elements in the list, or before the first or after the last element Methods of the Iterator ADT: hasNext(): returns true so long as the list is not empty and the cursor is not after the last element next(): returns the next element Extends the concept of position by adding a traversal capability Implementation with an array or singly linked list

2010 Goodrich, Tamassia Iterators and Sequences 2 Iterable Classes An iterator is typically associated with an another data structure, which can implement the Iterable ADT We can augment the Stack, Queue, Vector, List and Sequence ADTs with method: Iterator iterator(): returns an iterator over the elements In Java, classes with this method extend Iterable Two notions of iterator: snapshot: freezes the contents of the data structure at a given time dynamic: follows changes to the data structure In Java: an iterator will fail (and throw an exception) if the underlying collection changes unexpectedly

2010 Goodrich, Tamassia Iterators and Sequences 3 The For-Each Loop Java provides a simple way of looping through the elements of an Iterable class: for (type name: expression) loop_body For example: List values; int sum=0 for (Integer i : values) sum += i; // boxing/unboxing allows this 2010 Goodrich, Tamassia Iterators and Sequences 4 Implementing Iterators Array based

Linked list based array A of the elements index i that keeps track of the cursor doubly-linked list L storing the elements, with sentinels for header and trailer pointer p to node containing the last element returned (or the header if this is a new iterator). We can add methods to our ADTs that return iterable objects, so that we can use the foreach loop on their contents 2010 Goodrich, Tamassia Iterators and Sequences 5 List Iterators in Java Java uses a the ListIterator ADT for node-based lists. This iterator includes the following methods:

add(e): add e at the current cursor position hasNext(): true if there is an element after the cursor hasPrevious: true if there is an element before the cursor previous(): return the element e before the cursor and move cursor to before e next(): return the element e after the cursor and move cursor to after e set(e): replace the element returned by last next or previous operation with e remove(): remove the element returned by the last next or previous method 2010 Goodrich, Tamassia Iterators and Sequences 6 Sequence ADT The Sequence ADT is the union of the Array List and Node List ADTs Elements accessed by List-based

methods: Index, or Position Generic methods: size(), isEmpty() ArrayList-based methods: get(i), set(i, o), add(i, o), remove(i) 2010 Goodrich, Tamassia first(), last(), prev(p), next(p), replace(p, o), addBefore(p, o), addAfter(p, o), addFirst(o), addLast(o), remove(p) Bridge methods: Iterators and Sequences

atIndex(i), indexOf(p) 7 Applications of Sequences The Sequence ADT is a basic, generalpurpose, data structure for storing an ordered collection of elements Direct applications: Generic replacement for stack, queue, vector, or list small database (e.g., address book) Indirect applications: Building block of more complex data structures 2010 Goodrich, Tamassia Iterators and Sequences 8 Linked List Implementation

A doubly linked list provides a reasonable implementation of the Sequence ADT Nodes implement Position and store: element link to the previous node link to the next node Special trailer and header nodes header 2010 Goodrich, Tamassia Position-based methods run in constant time Index-based methods require searching from header or trailer while keeping track of indices; hence, run in linear time nodes/positions trailer elements Iterators and Sequences 9

Array-based Implementation elements We use a circular array storing positions A position object stores: Element Index Indices f and l keep track of first and last positions 2010 Goodrich, Tamassia 0 1 2 3 positions

S f Iterators and Sequences l 10 Comparing Sequence Implementations Operation Array 1 List 1 atIndex, indexOf, get 1 n first, last, prev, next 1 1 set(p,e) 1 1 set(i,e) 1

n add, remove(i) n n addFirst, addLast 1 1 addAfter, addBefore n 1 remove(p) n 1 size, isEmpty 2010 Goodrich, Tamassia Iterators and Sequences 11

Recently Viewed Presentations

  • Helium PBL

    Helium PBL

    Walther's Law. A law stating that lithologies that conformably overlie one another must have accumulated in adjacent depositional environments. Another way of thinking of this is the ability to predict what the rock units will look like if the depositional...
  • Models of Our Universe - SMU Physics

    Models of Our Universe - SMU Physics

    The Big Chill: Aka: The Big Freeze. The universe expands forever and cools off making it too cold to sustain life. The Big Crunch: Expansion slows down, reverses, and collapses. This will either cause a massive black hole singularity or...

    Felt that there should be relationships with community leagues. Interested in intramurals so students could be active and improve sport skills. Emphasized desire to offer healthy, active opportunities. Requested a student survey. Believed that having 1 Varsity and 1 JV...
  • Credit Risk - University of Belgrade

    Credit Risk - University of Belgrade

    Credit Ratings. In the S&P rating system, AAA is the best rating. After that comes AA, A, BBB, BB, B, and CCC. The corresponding Moody's ratings are Aaa, Aa, A, Baa, Ba, B, and Caa. Bonds with ratings of BBB...
  • William Shakespeare -

    William Shakespeare -

    William Shakespeare - The basics. Thought to be born on April 23, 1564 in Stratford-upon-Avon. Died April 23, 1616. Considered to be the best writer inthe English language. Surviving works: 38 plays, 154 sonnets, 2 long narrative poems, and several...
  • Hamilton Wildcats FC -

    Hamilton Wildcats FC -

    Hamilton Wildcats FC History Founded in 2004 Part of Hamilton Girls Soccer Club (formerly HTRGSL) Three original teams - U8, U9, U10 Added teams each year Today: 9 teams from U8-U14 36 players in 2004; 125 players 2008 Wildcats FC...
  • Alcohols - Groby Community College

    Alcohols - Groby Community College

    + HCl. Boardworks AS Chemistry . Alcohols. Teacher notes. Phosphorus(III) chloride can also be used a sa chlorinating agents. Phosphorus(V) chloride is a solid, and the reaction with alcohols can take place at room temperature. Phosphorus(III) chloride is a liquid,...
  • Cognitive Processes PSY 334

    Cognitive Processes PSY 334

    What matters is how material is processed. Orienting tasks: Count whether work has e or g. Rate the pleasantness of words. Half of subjects told they would be asked to remember words later, half not told. No advantage to knowing...