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:

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

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):

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

  Implementations
Hash TableResizable Array Balanced TreeLinked List
Interfaces Set HashSet   TreeSet  
List  ArrayList   LinkedList
Map HashMap   TreeMap  

Some properties of collections:

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.

Exercises

 

 

2001 Mark Ryan and Alan Sexton