CS计算机代考程序代写 data structure Java COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 8-3 : OOD10 Iterable and Iterator
Giulia Alberini, Fall 2020

WHAT ARE WE GOING TO DO IN THIS VIDEO?
 Java interfaces Iterable and Iterator

ITERABLE and ITERATOR

REMEMBER THE FOR-EACH LOOP?
int[] numbers = {1,2,3,4,5};
for(int element: numbers) {
System.out.println(element); }
The for-each loop (also called enhanced for loop) can make your code more readable and can be convenient to use. It is not helpful when you need to refer to the index of an element. For certain data structures is the only loop we can use…

ITERABLE AND ITERATOR
 The use of a for-each loop is made possible by the use of two interfaces: Iterator and Iterable.
 For beginners, the two interfaces are often confusing. Even though they are similar, they refer to two different things:
 Objects of type Iterable are representations of a series of elements that can be iterated over. (e.g. a specific ArrayList)
 Objects of type Iterator allows you to iterate through objects that represent a collection (a series of elements).

JAVA ITERABLE INTERFACE
public interface Iterable { public Iterator iterator();
}
 A class that implements Iterable needs to implement the iterator() method. The iterator() method returns an object of type Iterator that can then be used to iterate through the elements of this instance.
 A class that implements Iterator needs to implement the methods hasNext() and next().
public interface Iterator { boolean hasNext();
T next(); // returns current,
// and advances to next
void remove(); // optional, ignore it
}

OBSERVATION
public interface Iterable { public Iterator iterator();
}
 The iterator() method returns an iterator to the start of the collection. Using hasNext() and next() you can move forward in the collection. If you want to traverse the collection again, you’ll need a new Iterator.
public interface Iterator { boolean hasNext();
T next(); // returns current,
// and advances to next
void remove(); // optional, ignore it
}

ITERABLE AND FOR-EACH LOOP
 Implementing the Iterable interface allows an object to make use of the for-each loop. It does that by internally calling the iterator() method on the object!

HOW TO IMPLEMENT THE INTERFACES
 As always when implementing interfaces, a class that implements an interface must implement every method from such interface.
 Generally, when we write a class that implements the interface Iterable we also write a class that implements the interface Iterator. Often, such class is defined as an inner class of the first class.
 Why? To implement Iterable, we need to implement the method iterator(). Such method need to return an object of type Iterator that can iterate through the elements of a specific object of the outer class. We need a class that can create such object.

EXAMPLE
public class MyCollection implements Iterable { public MyIterator iterator() {
return new MyIterator(this);
}
}
 In general, if the class MyIterator is used only by the class MyCollection, good practice is to make that class a private inner class of MyCollection.
public class MyIterator implements Iterator { public MyIterator(MyCollection c) {
: }
}

SLinkedList
iterator() returns an object of type Iterator that points to the head of the provided list.
next() returns the element of the list that the Iterator is currently referencing, and then moves to the next node.
public class SLinkedList implements Iterable {
private SNode head;
public SLLIterator iterator() {
return new SLLIterator(this); }
private class SLLIterator implements Iterator { SNode cur;
SLLIterator(SLinkedList list) {
cur = list.head; }
public boolean hasNext() {
return (cur != null);
}
public E next() {
SNode tmp = cur;
cur = cur.next;
return tmp.element;
} }
}

THE BIG PICTURE
interface
Iterable
iterator()
extends
extends
interface
Iterator
next() hasNext()
interface
Iterable iterator()
interface
Collection
interface
List
implements
implements
implements
class
SLLIterator
SNode next() Boolean hasNext()
class
SLinkedList
: SLLIterator iterator()
class
LinkedList

EXAMPLE
 Suppose we have a SLinkedList of Shapes:
SLinkedList list = …
iter
 Then by calling iterator() we create an object of type Iterator that points to the head of the list.
Iterator iter = list.iterator();
list
head
size
4
null

SLinkedList list = … ;
Shape s;
s
list
head
size
null
4

SLinkedList list = … ;
Shape s;
Iterator iter1 = list.iterator(); Iterator iter2 = list.iterator();
s
list
iter1 iter2
head
size
null
4

SLinkedList list = … ;
Shape s;
Iterator iter1 = list.iterator(); Iterator iter2 = list.iterator();
s = iter1.next();
iter1
iter2
s
head
size
list
The iterators iterate over nodes, not Shapes. The next()
method returns a Shape.
null
4

SLinkedList list = … ;
Shape s;
Iterator iter1 = list.iterator(); Iterator iter2 = list.iterator();
s = iter1.next();
s = iter1.next(); iter1
iter2
s
head
size
list
null
4

SLinkedList list = … ;
Shape s;
Iterator iter1 = list.iterator(); Iterator iter2 = list.iterator();
s = iter1.next();
s = iter1.next(); iter1 s = iter2.next();
iter2
s
head
size
list
null
4

SLinkedList list = … ;
Shape s;
Iterator iter1 = list.iterator(); Iterator iter2 = list.iterator();
s = iter1.next();
s = iter1.next(); iter1 s = iter2.next();
s = iter2.next();
iter2
s
head
size
list
null
4

ITERATING THROUGH ELEMENTS IN A LINKED LIST
 What is the time complexity of the following two snippet of code? (suppose the size of the list is N)
for (k = 0; k < list.size(); k ++) System.out.println(list.get( k )); for (E element : list) System.out.println(e); In the next videos: Induction and Recursion

Related Posts