Robert Sedgewick and Kevin Wayne • Copyright © 2006 • http://www.Princeton.EDU/~cos2262.7 Lists and Iterators2Sequences and UrnsSequence. Ordered collection of items.Key operations. Insert an item, iterate over the items.Design challenge. Support iteration by client, without revealing theinternal representation of the collection.was the best ofIt timesnextRobert Sedgewick and Kevin Wayne • Copyright © 2006 • http://www.Princeton.EDU/~cos226Iteration in Java4Iterator InterfaceAPI for java.util.Iterator.! hasNext() Are there more items in the list?! next() Return the next item in the list.! remove() Delete the last item returned by next().public interface Iterator<Item> { boolean hasNext(); Item next(); void remove(); // optional}was the best ofIt timesnext5public static void main(String[] args) { Sequence<String> list = new Sequence<String>(); list.add("This"); list.add("is"); list.add("a"); list.add("test."); Iterator<String> i = list.iterator(); while (i.hasNext()) { String s = i.next(); System.out.println(s); }}Iterator ClientAPI for java.util.Iterator.! hasNext() Are there more items in the list?! next() Return the next item in the list.! remove() Delete the last item returned by next().6Iterable InterfaceAPI for java.lang.Iterable.! iterator() Return an iterator.Ex. Sequence, java.util.ArrayList, HashSet.public interface Iterable<Item> { Iterator<Item> iterator();}7Enhanced For LoopEnhanced for loop. Syntactic sugar for iterating over a collection.Remark. Can also use enhanced for loop with arrays.public static void main(String[] args) { Sequence<String> list = new Sequence<String>(); list.add("This"); list.add("is"); list.add("a"); list.add("test."); for (String s : list) System.out.println(s);}implements Iterable !can iterate using enhanced for loopRobert Sedgewick and Kevin Wayne • Copyright © 2006 • http://www.Princeton.EDU/~cos226Sequence ADT: Two Implementations9Sequence: Linked List Implementationimport java.util.Iterator;import java.util.NoSuchElementException;public class Sequence<Item> implements Iterable<Item> { private Node first, last; private class Node { Item item; Node mext; } public void add(Item item) { Node x = new Node(); x.item = item; if (first == null) first = x; else last.next = x; last = x; } public Iterator<Item> iterator() { return new SeqIterator(); }next slidesame as queue10Sequence: Linked List Implementation (cont)private class SeqIterator implements Iterator<Item> { Node current = first; public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; }}was the best ofIt timescurrent11Sequence: Array Implementationimport java.util.Iterator;import java.util.NoSuchElementException;public class Sequence<Item> implements Iterable<Item> { private Item[] a = (Item[]) new Object[8]; private int N = 0; public void add(Item item) { if (N >= a.length) resize(); a[N++] = item; } public Iterator<Item> iterator() { return new SeqIterator(); } private class SeqIterator // see next slide}as usual, with array doubling12Sequence: Array Implementation (cont)private class SeqIterator implements Iterator<Item> { int i = 0; public boolean hasNext() { return i < N; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return a[i++]; }}It was the best of times0 1 2 3 4 5 6 7i NRobert Sedgewick and Kevin Wayne • Copyright © 2006 • http://www.Princeton.EDU/~cos226Applications14Load BalancingLoad balancing. N users want to choose among N identical file shares.The goal is to balance users across file shares. Assume it's too hard tocoordinate (or query) all resources to see how empty they are.Random assignment. Assign each user to a resource at random.% java LoadBalance 100:1:2: user73: user1 user2 user84: user0 user95:6: user3 user67:8: user49: user5max load = 315Server.javapublic class Server { private Sequence<String> list = new Sequence<String>(); private int load; public void add(String user) { list.add(user); load++; } public String toString() { String s = ""; for (String user : list) s += user + " "; return s; }}16Load Balancingpublic class LoadBalance { public static void main(String[] args) { int N = Integer.parseInt(args[0]); Server[] servers = new Server[N]; for (int i = 0; i < N; i++) servers[i] = new Server(); // assign N users to N servers at random for (int j = 0; j < N; j++) { String user = "user" + j; int i = (int) (Math.random() * N); servers[i].add(user); } // print results for (int i = 0; i < N; i++) System.out.println(i + ": " + servers[i]); }}17Load BalancingLoad balancing. N users want to choose among N identical file shares.The goal is to balance users across file shares. Assume it's too hard tocoordinate (or query) all resources to see how empty they are.Coordinated assignment. Assign user i to server i.Result. Max load = 1.Random assignment. Assign each user to a resource at random.Theory. Max load " log N / log log N.Best of two. For each user, choose two resources at random and assignuser to least busy one.Theory. Max load " log log N.18Java List Libraries: ArrayList and LinkedListAPI for java.util.ArrayList.! add() Add item to end of list.! iterator() Return an iterator to the list.! size(), remove(), set(), clear(), indexOf(), toArray(), ….import java.util.ArrayList;public class Test { public static void main(String[] args) { ArrayList<String> list = new ArrayList<String>(); list.add("This"); list.add("is"); list.add("a"); list.add("test."); for (String s : list) System.out.println(s); }}Robert Sedgewick and Kevin Wayne • Copyright © 2006 • http://www.Princeton.EDU/~cos226Tree Iterators20Binary Tree IteratorBinary tree. Create an iterator for a binary tree.(and avoid using extra space)public class BinaryTree<Item> { private Node root; private class Node { Item item; Node l, r; } public Iterator<Item> iterator() { return new Preorder(); }} goal: implement thisBEMPTH WVY21Preorder TraversalPreorder traversal. Visit a node before its two children.Q. How to implement an iterator for preorder traversal?BEMPTH
View Full Document