LinkedList Implementation: iteration

Iteration.

To consider the task of implementing iteration, we start with a snippet of client code that prints all of the items in a collection of strings, one per line:

Stack collection = new Stack();
...
for (String s : collection)
   StdOut.println(s);
...

This foreach statement is shorthand for the following while statement:

Iterator i = collection.iterator();
while (i.hasNext()) { 
   String s = i.next();
   StdOut.println(s);
}

To implement iteration in a collection:

  • Include the following import statement so that our code can refer to Java’s java.util.Iterator interface:
    import java.util.Iterator;
  • Add the following to the class declaration, a promise to provide an iterator() method, as specified in the java.lang.Iterable interface:

implements Iterable
  • Implement a method iterator() that returns an object from a class that implements the Iterator interface:
    public Iterator iterator() {
    return new ListIterator();
}
  • Implement a nested class that implements the Iterator interface by including the methods hasNext(), next(), and remove(). We always use an empty method for the optional remove() method because interleaving iteration with operations that modify the data structure is best avoided.
    • The nested class ListIterator in Bag.java illustrates how to implement a class that implements the Iterator interface when the underlying data structure is a linked list.
    • The nested class ArrayIterator in ResizingArrayBag.java does the same when the underlying data structure is an array.

Assignments:

Implement the ADT Set, Set_YI.java with the methods below. The Set ADT uses a LinkedList structure. ‌ In mathematics, a Set is a well-defined collection of distinct objects, considered as an object in its own right. In this implementation of Set, the Set ADT behaves like a LinkedList but it doesn’t allow duplicates. Create a Node class.

    1. add(E e)
      Ensures that this collection contains the specified element.
    2. addAll(collection<?> c)
      Adds all of the elements in the specified collection to this set if they’re not already present. The alternate version is to add all elements from Set_YI.
    3. void clear()
      Removes all of the elements from this set (optional operation).
    4. boolean contains(Object o)
      Returns true if this set contains the specified element.
    5. boolean containsAll(collection<?> c)
      Returns true if this set contains all of the elements of the specified collection.
    6. boolean equals(Object o)
      Compares the specified object with this set for equality. The alternate version is to compare objects of Set_YI.
    7. boolean isEmpty()
      Returns true if this set contains no elements.
    8. Iterator<E> iterator()
      Returns an iterator over the elements in this set.
    9. boolean remove(Object o)
      Removes the specified element from this set if it is present (optional operation).
    10. boolean removeAll(collection<?> c) Removes from this set all of its elements that are contained in the specified collection (optional operation). The ? could be whatever you choose.
    11. int size()
      Returns the number of elements in this set (its cardinality).