$24
Iterators & BitList
Objectives
• Understand the principle of iterators.
• Explain in your own words the concept of iterators.
• Solve problems using an iterator.
Iterators are a type of data structure that allows us to traverse a collection of elements in order to interact with those elements. An iterator allows us to access an element of a collection, and then access the next element until the collection is empty.
In Java, the interface Iterator has the methods: hasNext(), next() and remove().
• hasNext() : Returns true if the iterator has a next element
• next() : Returns the next element or throws NoSuchElementException if no next element exists
• remove() : Removes the last element from the collection returned by the iterator, thus it has to be called after at least one call of the method next().
To illustrate the use of an iterator, we will use the class java.util.LinkedList. LinkedList is a linked list that implements the interface iterable, which specifies the method iterator(). The method iterator() returns an object implementing the interface Iterator.
Once we have that iterator, we can go through all the elements in the list al. To do so, we use a while loop with the condition that hasNext() returns true. We can then print every element of the list.
import java.util.*;
public class IteratorDemo{
public static void main(String args[]) {
// Create an array list
LinkedList<String> al = new LinkedList<String>();
// add elements to the array list
al.add("dog");
al.add("bird");
al.add("fish");
al.add("cat");
al.add("monkey");
al.add("lizard");
// Use iterator to display contents of al
System.out.print("Contents of al: ");
Iterator<String> itr = al.iterator();
while(itr.hasNext()) {
String element = itr.next();
System.out.print(element + " ");
}
}
}
Note that with a basic operator, we cannot modify the elements of the list. However, many implementations of the interface Iterator have additional methods that allow us to modify the elements, and much more. For example, the class ListIterator that implements Iterator has additional methods such as add, hasPrevious, previous, set and many others.
Practice
Modify the code above to print only the elements of the list al that precedes the String “cat” in the list (print all elements until you encounter “cat”).
Hint: modify the condition of the while loop.
For each loop
The for each loop acts as an iterator, and it allows us to directly act on the elements of the collection (without using methods such as set()).
The syntax for the for each loop is as follows:
for(type elem:collection){
//more code
}
Where :
• type : The type of the elements of the collection
• elem : The name of the variable representing each element in the loop
• collection : The name of the variable of the collection that we what to iterate through.
By default this loop will go through each element of the collection. However if we want to stop the loop after a certain condition we can use the command break that will immediately exit the loop.
Here is a solution of the exercise 1 above using the for each loop.
import java.util.*;
public class IteratorDemo{
public static void main(String args[]) {
// Create an array list
LinkedList<String> al = new LinkedList<String>();
// add elements to the array list
al.add("dog");
al.add("bird");
al.add("fish");
al.add("cat");
al.add("monkey");
al.add("lizard");
System.out.println("\nSolving using augmented for loop: ");
for(String element:al){
if(element.equals("cat")){
break;
}
System.out.print(element + " ");
}
}
}
Exercise
For this laboratory, you will use a linked list to save a number of bits (zeros and ones). Unlike other implementations seen before, the values in the nodes are integers (int).
The class BitList has an inner class. This is a second private class definition in the same folder as the public class BitList. This inner class is BitListIterator.
BitListIterator implements the interface Iterator forcing it to implement the three methods: hasNext, next, and remove.
Take the time to understand each method and their implementations.
BitList
Because most operations on bits work from right to left, your implementation must store the bits in the “right-to-left” order — i.e. with the rightmost bit in the first node of the list.
For example, the bits “11010” must be stored in a list such that the bit 0 is the first, followed by 1, followed by 0, followed by, 1, followed by 1:
• -> 0 -> 1 -> 0 -> 1 -> 1
Complete the implementation of the class BitList
The linked list makes use of the private instance variable first of type Node that represents the first element in the list.
public BitList( String s )
This constructor has to create a list representing the chain of 0s and 1s given as parameter.
The given string, s, must be a string of 0s and 1s, otherwise the constructor must throw an exception of type IllegalArgumentException.
This constructor initializes the new BitList instance to represent the value in the string. Each character in the string represents one bit of the list, with the rightmost character in the string being the low order bit.
For example, given the string “1010111” the constructor should initialize the new BitList to include this list of bits:
• -> 1 -> 1 -> 1 -> 0 -> 1 -> 0 -> 1
If given the empty string, the constructor should create an empty list — null is a not a valid argument.
The constructor must not remove the leading zeroes. For example, given “0001” the constructor must create a list of size 4:
• -> 1 -> 0 -> 0 -> 0
Files:
• Iterator.java
• BitList.java
