Working with collections

What are collections?

A collection (sometimes called a container) is an object that groups multiple elements into a single unit. Collections are used to store, retrieve and manipulate data, and to transmit data from one method to another. Collections typically represent data items that form a natural group, like an order (a collection of order lines), a mail folder (a collection of messages), or a telephone directory (a collection of name/phone-number pairs).

Example: ArrayList

ArrayLists are like growable arrays. In an ordinary array, if you run out of space (i.e. you want to insert more elements than the array can hold), you're stuck. With an ArrayList, however, more sace is automatically allocated.

ArrayList coins = new ArrayList();
coins.add(new Coin(0.1, "dime"));
coins.add(new Coin(0.25, "quarter"));
. . .

To get objects out of the ArrayList, use the get method, which takes an integer position argument.

Coin myCoin = (Coin)coins.get(4);

Like arrays, the positions start at 0, and go to coins.size()-1.

There is also an add(object, position) method which adds the object at the stated position. It shifts elements with higher positions (adds one to their position) to make room. It throws an exception if position is greater than the current size.

Points to note:

We don't need to set the size at the construction time. We can, if we want to, for added efficiency.
ArrayLists store Objects. These have to be cast back to the correct type. To store integers or doubles, use the wrapper classes Integer and Double. An ArrayList can store any object - so you could add non-Coin objects to coins. However, the code above which attempts to cast any element of coins back to a Coin would then result in an error.
Other methods include remove(i) (which removes and shifts down), set(i) (which replaces the object at position i). See ArrayList for more details.

ArrayLists suffer from some of the same problems as arrays, however:

insertion at a particular point may be very inefficient, if a lot of shifting is involved. Removal is similarly inefficient. Storing objects as a linked list does not suffer from this drawback.
arrays are ordered, yet the collection we are storing may not have a natural ordering. Arrays also allow duplications, which may be undesirable for some purposes. Storing items in a hash table does not suffer from these disadvantages.

Fortunately, the collections API implements these other ways of storing items too.

The Collections API

Benefits of using the Collections API (this list taken from Sun's Collections Framework Overview):

Reduces programming effort by providing useful data structures and algorithms so you don't have to write them yourself.
Increases performance by providing high-performance implementations of useful data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be easily tuned by switching implementations.
Provides interoperability between unrelated APIs by establishing a common language to pass collections back and forth.
Reduces the effort required to learn APIs by eliminating the need to learn multiple ad hoc collection APIs.
Reduces the effort required to design and implement APIs by eliminating the need to produce ad hoc collections APIs.
Fosters software reuse by providing a standard interface for collections and algorithms to manipulate them.

Collections in Java

Collections in Java are organised around the following interfaces:

A set is a collection without duplicates. A list is a collection which may have duplicates. A map is an assignment of values to keys. Maps are not collections, but are related to them.

Important methods of the Collection interface:

`boolean`	`add(Object o)` Ensures that this collection contains the specified element (optional operation).
`boolean`	`remove(Object o)` Removes a single instance of the specified element from this collection, if it is present (optional operation).
`int`	`size()` Returns the number of elements in this collection.
`boolean`	`contains(Object o)` Returns `true` if this collection contains the specified element.
`boolean`	`equals(Object o)` Compares the specified object with this collection for equality.
`Iterator`	`iterator()` Returns an iterator over the elements in this collection.

Typical usage of collections:

Interface myCol = new ImplClass();
myCol.add(...);
myCol.add(...);
myCol.remove(...);

Iterator it = myCol.iterator();
while (it.hasNext())
{
   Item i = (Item) it.next();
   // do something with i
   // possible: it.remove();
}

Some standard implementations in the API

		Hash Table	Resizable Array	Balanced Tree	Linked List
		Implementations
Interfaces	Set	`HashSet`		`TreeSet`
	List		`ArrayList`		`LinkedList`
	Map	`HashMap`		`TreeMap`

Some properties of collections:

automatically grown to size;
only contain objects, not primitive datatypes.
have many convenient methods, such as iterator(). The method get(int i) (not present in all collections) returns the ith element.

LinkedList is an implementation of the List interface. Look at LinkedListTest.java.

Just changing the implementation class (e.g. whether ArrayList or LinkedList) can have a big effect on the efficiency of the program.

Sorted collections

Sorted collection implementations need to know how objects should be ordered. A class which implements the Comparable interface must have a compareTo method, which tells how objects of the class are ordered:

int compareTo (Object arg)

returns a negative, zero or positive integer according to whether the calling object is less, equal or greater than arg other in the natural ordering. Look at the Item class in TreeSetTest.java.

TreeSet is an implementation of the SortedSet interface, which keeps items in an ordered tree.

The comparator interface

Sometimes we want to sort in a different order to the natural ordering. To do that, we define a compare method as the only method in a class which implements the Comparator interface. We provide an object of that class in the constructor of the ordered collection.

TreeSet is an implementation of the Set interface. Look at TreeSetTest.java.