Java Collections

Java.util

Collections can store only objects in Java. Primitive types can not be added to a collection, so it is necessary to use the wrapper classes such as Integer and Double instead of primitives.

There are three elements that make up collections.

·        Interfaces  define the methods that each type of collection must implement

·        Implementations  actual classes such as Hashtable and Vector

·        Algorithms  methods that store, retrieve, and manipulate elements in a collection

There are four properties that collections may or may not possess, as shown in Table. These are the properties you must know to differentiate collection types.

Property	Description
Sorted	Ascending order, sorted naturally using the equals() object method. An example is a Membership list.
Ordered/Unordered	Collection keeps an order determined by where the object is placed in the collection. For example, a deck of cards is ordered.
Allows duplicates	Duplicate objects can be added to the collection. An example is a collection of hockey cards.
Uses keys	A key object is used to reference the stored object. For example, names of people are stored by social insurance number.

Collection Interfaces and Classes

The interfaces in the collections framework are the foundation of collections. By using these interfaces, collections can be passed into other methods regardless of the details of a particular collection.

There are six interfaces that make up the core collections framework. Some of these interfaces extend other interfaces to form a hierarchy

                             

Notice Map and SortedMap do not extend the Collection interface. Map and SortedMap are still known as collections, even though in strict Java terms they are not Collection types.

Each of the interfaces also has an abstract class that has some of the methods already programmed. For example, the Collection interface has a class called AbstractCollection, and the Set interface has a class called AbstractSet.

We will now examine the interfaces individually.

Iterator methods

A simple explanation of an iterator is an object that contains methods that allow a programmer to iterate through the data one element at a time.Iterator enables you to cycle through a collection, obtaining or removing elements.

List al = new ArrayList();
      // add elements to the array list
      al.add("A");
      al.add("B");
      al.add("C");

// Use iterator to display contents of al
Iterator itr = al.iterator();

while(itr.hasNext()) {
         Object element = itr.next();
}

Iterator iterator()

The iterator() method returns an Iterator object from the collection. The methods in the Iterator interface are as follows:

boolean hasNext()

This returns true if the iteration has more elements.

Object next()

The preceding returns the next element in the iteration.

void remove()

This removes from the underlying collection the last element returned by the iterator.

ListIterator extends Iterator to allow bidirectional traversal of a list, and the modification of elements.

ListIterator litr = al.listIterator();
while(litr.hasNext()) {
   Object element = litr.next();
   litr.set(element + "+");

}

while(litr.hasPrevious()) {
   Object element = litr.previous();
}  

Set

A Set is unique because it does not allow duplicate objects to enter the collection of elements. The Set interface contains all of the methods of the Collection interface  and does not add any new methods. The difference is the add() and addAll() methods check for duplication of objects using the equals() method on each object.

The only functional class in the Java API that directly implements the Set interface is HashSet, as you can see in the Figure. Let’s look at the HashSet class in use.

import java.util.*;
class SetTest {
     public static void main (String [] args) {

            Set<String> hs = new HashSet<String>();
          hs.add("Hockey Game");
          hs.add("Poker");
          hs.add("Solitaire");
          hs.add("Hockey Game");
          System.out.println(hs);
     }
}

Sorted Set

The SortedSet interface is similar to the Set interface, except that the elements in the set are stored in ascending order. Once again, the elements are nonduplicating. The SortedSet interface includes all of the methods of Set because it extends Set, but also adds a few more to take advantage of the fact that it is sorted.

The TreeSet class is the only class to implement this interface directly. Let’s examine the TreeSet class in some code.

import java.util.*;
class SortedSetTest {
     public static void main (String [] args) {
          SortedSet set = new TreeSet();
          set.add("Hockey Game");
          set.add("Chess");
          set.add("Checkers");
          set.add("Blackjack");
          System.out.println(set);
          SortedSet end = set.tailSet("Checkers");
          System.out.println(end);
     }
}

List

A List is ordered. This allows a List to maintain an order as objects are added and removed from the collection. This is not the same as sorted! Sorted objects form a hierarchy based on how the objects compare to each other, such as alphabetical sorting.



Note: An ordered collection maintains the order of the elements based on the sequence you put stuff into/remove them from the collection. A sorted collection keeps the elements sorted based on a sort criteria.
 

A List can also contain duplicate entries of objects. The List interface adds several methods, all of which deal with the List collection being ordered. The added methods contain an index or index numbers that are used to specify a certain ordered object in the List.

There are three functional classes that implement the List interface.

·         LinkedListobjects are queued at the beginning of the list and removed from the end. Often used when buffering operations.

·         Vectora growable array of objects.

·         ArrayListThis class is roughly equivalent to Vector, except that it is unsynchronized.

	LinkedList	ArrayList
get(int index)	O(n) (with n/4 steps on average)	O(1) <--- main benefit of ArrayL
add(E element)	O(1)	O(1) amortized, but O(n) worst-case
add(int index, E element)	O(n) (with n/4 steps on average), but O(1) when index = 0	O(n) (with n/2 steps on average)
remove(int index)	O(n) (with n/4 steps on average)	O(n) (with n/2 steps on average)
Iterator.remove()	O(1). <--- main benefit of LinkedList<E>	O(n) (with n/2 steps on average)
ListIterator.add(E element)	O(1) This is one of the main benefits of LinkedList<E>	O(n) (with n/2 steps on average)

 

 

Map

The Map interface does not extend the Collection interface (see figure), so in strict terms it is not a Collection type. In general terms, however, it is part of the collections architecture.

A Map stores objects that are identified by unique keys. A map may not store duplicate keys. It can, however, store duplicate objects. Objects are stored in Map collections in no particular order.

There are two common collections that directly implement the Map interface, as we saw in Figure:

·        Hashtable

·        HashMap

The HashMap class is roughly equivalent to Hashtable, except that it is not synchronized for threads and it permits null values to be stored.

import java.util.*;
class HashMapTest {
     public static void main (String [] args) {
          Map hm = new HashMap();
          hm.put("Game1","Tic Tac Toe");
          hm.put(null, "Chess");
          hm.put("Game3", "Checkers");
          hm.put("Game3", "Hockey Game");
          hm.put("Game4", "Chess");
          System.out.println(hm);
          String title = (String)hm.get("Game3");
          System.out.println(title);
     }
}

Sorted map

SortedMap is similar to Map, except the objects are stored in ascending order according to their keys. Like Map, there can be no duplicate keys and the objects themselves may be duplicated. One very important difference with SortedMap objects is that the key may not be a null value. SortedMap objects are, of course, sorted and it would be impossible to try to sort with a null value as a comparator.

TreeMap is the only core API class to implement this interface directly, so let’s examine this in some code.

import java.util.*;
class TreeMapTest {
     public static void main (String [] args) {
          Map titles = new TreeMap();
          titles.put(new Integer(2),"Tic Tac Toe");
          titles.put(new Integer(3), "Checkers");
          titles.put(new Integer(1), "Hockey Game");
          titles.put(new Integer(4), "Chess");
          System.out.println(titles);
     }
}

	Sorted	Ordered	Uses Keys	No Duplicates
Set				X
SortedSet	X			X
List		X
Map			X
SortedMap	X		X

Now that you have a better idea of collections, here are some possible attributes for a collection, followed by the correct collection interface.

Non-duplicating, unordered collection	Set
Duplicating, ordered collection	List
Duplicating, ordered collection with keys	Map
Non-duplicating, sorted collection	SortedSet
Duplicating collection sorted by keys	SortedMap

·         Set can store only unique objects, not duplicates.

·         A List keeps the objects indexed in a definite order.

·        A Map stores objects according to keys.

·        SortedSet stores objects in ascending order without duplicates.

·        SortedMap stores objects in ascending order using keys.

·        SortedSet can’t contain objects that are null.

·        SortedMap can’t contain keys that are null.

·        HashSet implements the Set interface.

·        TreeSet implements the SortedSet interface.

·        LinkedList, Vector, and ArrayList implement List.

·        HashMap and Hashtable implement the Map interface.

·        TreeMap implements the SortedMap interface.