In Chapter 9 we studied three different collections:
Portfolio: index-based
collection of Investments
GlobalCredit: collection of
unique CreditCards
Student: collection of Strings
representing course names that map
to grades
Collections are used often when writing code. It would be very tedious and error prone if a client had to create their own collection classes. Java provides a set of software components that are used to represent and manipulate collections of any object type. The Java Collection Framework is made up of:
The official tutorial for Java collections is http://download.oracle.com/javase/tutorial/collections/index.html .
The UML diagram for the Collection interface
hierarchy is shown below:
The Collections Framework also includes a hierarchy of interfaces that are
not rooted at Collection; nevertheless, the Map
interface is an important part of the Collections Framework.
Collection Interface
A Collection represents a group of objects where
each object is called an element of the collection. The interface
defines the most general operations that a client can ask
a collection to perform:
public interface Collection<E> extends Iterable<E>
{
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
Recall that GlobalCredit was a collection of credit cards
and Portfolio was a collection of investments. In general,
a collection needs to be able to hold elements of some type E.
How might we create a collection that can hold any type E?
We know that every class has Object at the root of its
inheritance hierarchy, so a possible solution is to create a collection
that holds Object references (because every
class type is substitutable for Object).
There are two significant problems
with the collection of Object approach.
The first problem is that every class is substitutable for
Object. This means that a client can put anything into a
collection that holds Object references. If the client
creates a collection of Strings there is nothing preventing
the client from adding a Fraction to the collection.
The second problem is that such a collection will always return a
reference to an Object whenever the client retrieves an element
from the collection. This means that the client must always try to cast
the type of the retrieved element to do anything remotely useful.
The designer of the Java language solved the problem by creating a mechanism called generics that allows the client to specify the type of element to use. Suppose you wanted to create a collection of strings:
Collection<String> someStrings = new ArrayList<String>();
// add a string
someStrings.add("Hey this works!");
// get a string
String s = ((List<String>) someStrings).get(0);
Here's how you read the notation:
Collection<String> |
Collection of String |
ArrayList<String> |
ArrayList of String |
List<String> |
List of String |
You can only use generics if the class or interface is declared as
a generic interface (ie. don't try this with Fraction or
String).
List Interface
A List is a collection that holds its elements in
numbered sequence. List supports:
Iterator semantics to take
advantage of the list's sequential nature
List Interface
public interface List<E> extends Collection<E>
{
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c ); //optional
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
It would be a good idea to read the List
API
http://download.oracle.com/javase/6/docs/api/java/util/List.html.
To create a list, you need a class that implements
List. Usually, you will want to use
ArrayList; the other choice is
LinkedList.
// an empty list of Integer List<Integer> numbers = new ArrayList<Integer>();
// an empty list of String List<String> words = new ArrayList<String>();
// an empty list of Fraction List<Fraction> fractions = new ArrayList<Fraction>();
// an empty list of lists of Double List<List<Double>> matrix = new ArrayList<List<Double>>();
You use add to add to the end of the list.
List<Integer> numbers = new ArrayList<Integer>(); numbers.add(new Integer(0)); numbers.add(new Integer(10)); numbers.add(20);
Notice how auto-boxing allows you to add an int
even though numbers is a list of
Integer.
You use get to retrieve an element
using an index from a list.
List<Integer> numbers = new ArrayList<Integer>();
numbers.add(new Integer(0));
numbers.add(new Integer(10));
numbers.add(20);
for (int i = 0; i < numbers.size(); i++)
{
output.println(numbers.get(i));
}
output.println("---");
The above code fragment outputs:
0 10 20 ---
You use the overloaded version of add
to add an element into the list at a specified
index; the existing elements get shifted one
index upwards.
List<Integer> numbers = new ArrayList<Integer>();
numbers.add(new Integer(0));
numbers.add(new Integer(10));
numbers.add(20);
for (int i = 0; i < numbers.size(); i++)
{
output.println(numbers.get(i));
}
output.println("---");
numbers.add(1, new Integer(5));
for (int i = 0; i < numbers.size(); i++)
{
output.println(numbers.get(i));
}
The above code fragment outputs:
0 10 20 --- 0 5 10 20
If you flip a fair coin N times how many heads do you expect to see? How often do you expect to see N / 4 heads?
You could solve the problem using statistics (google "binomial distribution"), or you could write a simulation.
L of length N.
L with all zeros
n
1 to element at index (n - 1)
in L