Java Collections Framework

last updated 2/23/04

Java Class Library

import java.util.*;

In this package you will find a number of common data structures already implemented for you.

The framework includes

interfaces
abstract classes
concrete classes (no abstract methods)
protocols

Similar properties of collections

a collections' size can grow dynamically
defined to hold Objects
uses references rather than copies (shallow copying)
provides two constructors, one to be empty, other to be a copy of the contents of another collection (not necessarily of the same structure)

Differing properties of the various collections

logical structure of the elements
underlying implementation
efficiency of the operations
set of supported operations
duplicate entries may or may not be permitted
support of "keys"
whether or not elements are "sorted"

Legacy Classes

Vector -- A dynamically sized array but has been supplanted by the ArrayList

BitSet -- An array of bits (boolean values)

Stack -- extends Vector and contains the operations as we've defined them, but the implementation may be less efficient because of the way Vector operations are implemented.

Java 2 Collections Framework Interfaces

Collection Interface

no unique keys
boolean add(Object) -- add the object to the collection; return true if this was a new value in the collection
boolean addAll(Collection) -- all the objects of the parameter; return true if any new value was added to the the collection
boolean contains(Object) -- returns true if the collection contains the object
boolean isEmpty() -- returns true if the collection has no elements

Map Interface

unique keys
the List interface we've discussed is more closely related to the this structure
we will discuss this interface's operations when we discuss hashing later in the course

Iterator Interface

iterators are "instantiated and used once through" (no reset)
next() gets next item
hasNext() checks if there is a next item

The Collection Interface

The Collection is a standard structure interface that is defined in Java. These are the method names you should use on defining the standard operations on collections, whether you are implementing the interface or not.

import java.util.*; //Collection and Iterator found here

method	description
boolean add(Object element)	object is added to the collection
boolean addAll(Collection c)	the collection c is added to the current collection
void clear()	removes all elements from the collection
boolean contains(Object element)	returns true if element is in the collection
boolean containsAll(Collection c)	returns true if c is a subset of the collection
boolean equals(Object o)	returns true if the object o equals the collection (in some way defined within the implementation)
boolean isEmpty()	returns true if the this collection contains no elements
Iterator iterator()	returns an iterator over the elements of the collection
boolean remove(Object element)	remove one instance of this element in the collection
boolean removeAll(Collection c)	remove all elements in the collection that are also in collection c
boolean retainAll(Collection c)	retain all elements that are found in collection c; remove all others
int size()	returns the number of elements in the collection
Object[] toArray()	return an array containing all of the elements of the collection.

Introduction to iterators

The persistent pattern of sequentially processing a collection is clear. That is, we start at the beginning of the collection (whatever the beginning may be) and step through each item with the option of removing it, or inserting a new item before or after (if it's an ordered collection).

An iterator is an object associated with a collection that simplifies (abstracts) the access of the elements in the collection.

Iterators are implemented as an interface. That is, as in any interface, it defines some basic methods that must be implemented or is implemented for you.

The iterator tracks what elements of the collection has been processed, which is the current element and if there is a next element.

Iterators are typically "use once". If you need to start over, you instantiate a new iterator.

Public Methods

These methods need to be implemented for the iterator interface.

boolean hasNext() // returns true if the iterator has more elements

Object next() // return the item next in the sequence; 
              // update current pointer; return null if there is no next

void remove() // removes the last item returned from the collection

Example implementation of an iterator

TestIterator.java as a user of the iterator

Example Use of the Iterator

Tiny cllctn = new Tiny();
Iterator iter = cllctn.iterator();

  ...   //simple walk through the collection
  while(iter.hasNext()){
    Object obj = iter.next();
    processElement(obj);
  }

       //rewalk the collection
  iter = cllctn.iterator(); // reset iterator
  if(iter.hasNext()){...

       //can have multiple iterators on same collection
  Iterator iter2 = cllctn.iterator();

  iter.remove(); // may cause problems with iter2

AbstractCollection Class

This defines 15 fundamental operations that when you extend it to define a new class, you will more likely provide the basic operations necessary to use the collection. This is called "completeness".