Java Collections

The Java Collections API's provide Java developers with a set of classes and interfaces that makes it easier to handle collections of objects.Rather than having to write your own collection classes, Java provides these ready-to-use collection classes for you.

In order to understand and use the Java Collections API effectively it is useful to have an overview of the interfaces it contains. So, that is what I will provide here.
There are two "groups" of interfaces: Collection's and Map's.
Here is a graphical overview of the Collection interface hierarchy:

And here is a graphical overview of the Map interface hierarchy:

 

In the Collections Framework, the interfaces Map and Collection are distinct with no lineage in the hierarchy. The typical application of map is to provide access to values stored by keys.
When designing software with the Collection Framework, it is useful to remember the following hierarchical relationship of the four basic interfaces of the framework.

The Collection interface is a group of objects, with duplicates allowed.

Set extends Collection but forbids duplicates.

List also extends Collection, allows duplicates and introduces positional indexing.

Map extends neither Set nor Collection

Interface	Implementation				Historical
Set	HashSet		TreeSet
List		ArrayList		LinkedList	Vector Stack
Map	HashMap		Treemap		Hashtable Properties

The historical collection classes are called such because they have been around since 1.0 release of the java class libraries. If you are moving from historical collection to the new framework classes, one of the primary differences is that all operations are synchronized with the new classes. While you can add synchronization to the new classes, you cannot remove from the old.

Iterable :

The Iterable interface (java.lang.Iterable) is one of the root interfaces of the Java collection classes. The Collection interface extends Iterable, so all subtypes of Collection also implement the Iterable interface.

The iterator() method of the Collection interface returns and Iterator. An Iterator is similar to the Enumeration interface, Iterators differ from enumerations in two ways:
1.Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
2. Method names have been improved.  

A class that implements the Iterable can be used with the new for-loop. Here is such an example:

List list = new ArrayList();

for(Object o : list){
    //do something o;    
}

Iteratable usage in java 5 with generics:

ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist

for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    String s = it.next();  // No downcasting required.
    System.out.println(s);
}

 Example pre Java 5, with explicit iterator and downcasting

An iterator might be used as follows :

ArrayList alist = new ArrayList(); // This holds type Object.
// . . . Add Strings to alist

for (Iterator it = alist.iterator(); it.hasNext(); ) {
    String s = (String)it.next();  // Downcasting is required pre Java 5.
    System.out.println(s);
}

Iterator Methods

Iterator defines three methods, one of which is optional.

Result	Method	Description
b =	it.hasNext()	true if there are more elements for the iterator.
obj =	it.next()	Returns the next object. If a generic list is being accessed, the iterator will return something of the list's type. Pre-generic Java iterators always returned type Object, so a downcast was usually required.
	it.remove()	Removes the most recent element that was returned by next. Not all collections support delete. An UnsupportedOperationException will be thrown if the collection does not support remove().

Q: What does this loop do? Note mixing of iterator with index.

ArrayList<String> alist = new ArrayList<String>();
// . . . Add Strings to alist

int i = 0;
for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(alist.get(i++));
}

 

A: It throws an exception when it goes beyond the end.

After hasNext() returns true, the only way to advance the iterator is to call next(). But the element is retrived with get(), so the iterator is never advanced. hasNext() will continue to always be true (ie, there is a first element), and eventually the get() will request something beyond the end of the ArrayList. 

Use either the iterator scheme.

for (Iterator<String> it = alist.iterator(); it.hasNext(); ) {
    System.out.println(it.next());
}

Or the indexing scheme, but don't mix them.

for (int i=0; i < alist.size(); i++) {
    System.out.println(alist.get(i));
}

ListIterator methods

ListIterator is implemented only by the classes that implement the List interface (ArrayList, LinkedList, and Vector). ListIterator provides the following.

Result	Method	Description
Forward iteration
b =	it.hasNext()	true if there is a next element in the collection.
obj =	it.next()	Returns the next object.
Backward iteration
b =	it.hasPrevious()	true if there is a previous element.
obj =	it.previous()	Returns the previous element.
Getting the index of an element
i =	it.nextIndex()	Returns index of element that would be returned by subsequent call to next().
i =	it.previousIndex()	Returns index of element that would be returned by subsequent call to previous().
Optional modification methods. UnsupportedOperationException thrown if unsupported.
	it.add(obj)	Inserts obj in collection before the next element to be returned by next() and after an element that would be returned by previous().
	it.set()	Replaces the most recent element that was returned by next or previous().
	it.remove()	Removes the most recent element that was returned by next() or previous().




Java Generics - Implementing the Iterable Interface

It is possible to use your own collection type classes with the new for-loop. To do so, your class must implement the java.lang.Iterable<E> interface. Here is a very basic example:

public class MyCollection<E> implements Iterable<E>{

    public Iterator<E> iterator() {
        return new MyIterator<E>();
    }
}

And here is the corresponding implementation skeleton of the MyIterator class:

public class MyIterator <T> implements Iterator<T> {

    public boolean hasNext() {
    
        //implement...
    }

    public T next() {
        //implement...;
    }

    public void remove() {
        //implement... if supported.
    }
}

Here is how to use the MyCollection generified, and with the new for-loop:

public static void main(String[] args) {
    MyCollection<String> stringCollection = new MyCollection<String>();

    for(String string : stringCollection){

    }
}

Other Java Collections basics :

http://tutorials.jenkov.com/java-collections/sorting.html