Collections and Data Structures


The Collections Framework

Reading Assignment:
Java Tutorial's Collections Framework Trail - read the Intro: http://java.sun.com/docs/books/tutorial/collections/intro/index.html
And read the Interfaces Lesson: http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html

A collection = an object that organizes data inside your classes

 How you structure data in you program greatly impacts your program's performance.

Collections Framework - a hierarchy of interfaces and classes that provides different ways of organizing your data



Collection Interfaces

4 primary interfaces: Collection, Set, List, Map

These correspond loosely to the 4 major types of collections: bags, sets, lists, maps

 Fundamental Interface in Framework: the Collection interface


The Collection interface: first consider the 2 most fundamental methods in java.util.Collection
 The add() method adds an object to the collection.
  -- Returns true if adding the object actually changed the collection, false otherwise

Ex: If you add an element to a set and the object is already in the set, then the set doesn't change since sets do not contain duplicates.

The iterator() method returns an object that implements the Iterator interface (more on this in a minute). An iterator object lets you visit the elements in your collection one by one.




Iterator Interface Interlude

***********************************************************
The Iterator interface - consider 3 fundamental methods first:
 Visit the next element in the collection by calling the next() method.
  -- If you are at the end of the collection, next() throws a NoSuchElementException.
  -- Call hasNext() before calling next().

hasNext() returns true if the iterator object has more elements to visit.

Ex: Look at all elements in previously defined collection c

Iterator it = c.iterator();
while(it.hasNext())
{
   Object obj = it.next();
   // whatever you want to do with obj
}

remove() removes the element that was returned by the last call to next().

Advancing an Iterator - think of the iterator pointing between elements. When next() is called, the iterator moves past the next element and returns a reference to it.

Ex: Remove the 1st element in previously defined collection c

Iterator it = c.iterator();
it.next();  // returns 1st element
it.remove();  // removes 1st element

If next() is not called before the call to remove(): IllegalStateException is thrown.

Ex: Remove 2 adjacent elements in collection c

it.next();
it.remove();
it.next();
it.remove();

************************************************


We will use Iterators frequently!


Exercise: Write a method addAll() that adds all objects from one collection to another. The boolean return value should be true if the collection is changed by the operation, and false otherwise.
public static boolean addAll(Collection to, Collection from)
{
      Iterator it = from.iterator();
      boolean changed = false;
      while(it.hasNext())
      {
         if(to.add(it.next()))
            changed = true;
      }
      return changed;
 }


The abstract class AbstractCollection implements the Collection interface. It leaves the fundamental methods (like add() and iterator()) abstract, but implements some other routine methods (like a version of addAll()) in terms of them.

public abstract class AbstractCollection implements Collection
{
    public abstract boolean add(Object obj);

    public boolean addAll(Collection from)
    {
        // fill in the code as an exercise

    }
}

Some concrete Collection classes extend AbstractCollection instead of implementing the Collection interface - this is simpler, since some methods are provided in AbstractCollection.




Methods of java.util.Collection

Iterator iterator()
      -- Returns an interator that can be used to visit the elements of the collection

int size()
    -- returns the number of elements in the collection

boolean isEmpty()
    -- returns true if the collection contains no elements

boolean contains (Object obj)
    -- returns true if this collection contains obj

boolean containsAll (Collection other)
    -- returns true if this collection contains all elements in other

boolean add (Object element)
    -- adds element to the collection, and returns true if this collection is changed as a result of this call

boolean addAll (Collection other)
    -- adds all elements of other to this collection, and returns true if this collection is changed as a result of this call

boolean remove (Object obj)
     -- removes an object equal to obj from this collection, and returns true if a matching object was removed

boolean removeAll (Collection other)
    -- removes all elements from this collection that are also contained in other, and returns true if this collection was changed as a result of this call

void clear()
    -- removes all elements from this collection

boolean retainAll(Collection other)
    -- removes all elements from this collection that are not contained in other, and returns true if collection is changed as a result of call

Object[] toArray()
    -- returns an array of the objects in the collection

Note: All Collection implementation classes have a constructor that takes a Collection argument, and initializes the new Collection to contain all elements in the Collection that is passed in.

Example: Assume coll is a Collection of some sort. Create a new ArrayList (this is a class that inherits from the List interface) that contains all elements of coll.

List myList = new ArrayList(coll);   // now myList contains all elements in coll



Methods in java.util.Iterator

boolean hasNext()
   -- returns true if there is another element to visit

Object next()
   -- returns the next object in this collection. Throws a NoSuchElementException if the end of this collection has been reached.

void remove()
   -- removes the last visited object - a call to remove() must follow an element visit. If this collection has been modified since the last element visit, remove() throws an IllegalStateException.