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.
|
|
|
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.
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.
