Collections

Part:   1   2  3  4 

This note is based on J2SDK 1.4.1_01.

Types of Collections

If you are looking for a utility class to organize a group of objects in your application, you will have a hard time to decide which one to use, because J2SDK offers so many of them: AbstractCollection, AbstractList, AbstractMap, AbstractSequentialList, AbstractSet, ArrayList, Collection, Dictionary, HashMap, HashSet, HashTable, IdentityHashMap, LinkedHashMap, LinkedHashSet, LinkedList, List, Map, Set, SortedMap, SortedSet, Stack, TreeMap, TreeSet, Vector, WeakHashMap.

To help you out, let me introduce you some basic concepts about data collections.

Collection: A group of data elements, or objects, organized together. Depending on how the elements can be stored and retrieved, collections are divided into 3 types: set, list, and map.

Set: Data elements are stored and retrieved without position numbers and keys.

The operation of storing an element into a set collection is simple. We can just put the element anywhere in the collection.

However the operation of retrieving an element out of a set collection is very difficult, since there is no clue on where that element is stored in the collection, no position number and no key. The only thing you have is the element, so you have to go through all elements in the collection, and compare each one of them with the given element. If the given element matches a particular element in the collection, you declare that you have found the element in the collection. There is no need to turn that element, because the user of the set collection already has the element. So the only use of the searching process is to identify if the given element is in the collection or not.

List: Data elements are stored and retrieved by position numbers. List is also called sequence.

The operation of storing an element into a list collection is simple but tricky. If you are asked to store an element into a collection with a specific position number, and there is already an existing element at that position, what are you going to do? The answer depends on additional rules about the list collection. If the list collection requires you to replace the existing element with given element, then replace it. If the list collection requires you to move the element at the requested position and all the subsequent elements forward by one position, and put the given element at the requested position, then you will have a lot of work to do.

The operation of retrieving an element out of a list collection is much easier than the set collection. With the given position number, just go to that position and return the element at that position.

Map: Date elements are stored and retrieved by keys. Map is also called dictionary.

The operation of storing an element into a map collection also simple and tricky. If you are asked to store an element into a collection with a key associated with it, and there is already an existing element with that same key, what you going to do? The answer depends on additional rules about the map collection. If duplicate keys are not allowed in the map collection, you should replace the existing element with given element.

The operation of retrieving an element out of a map collection is relatively easy. With the given key, you should through all the keys in the collection, and compare each one of them with the given key. If there is a match, return the element associate with the matching key. Comparing with the set collection, we are matching keys instead of the data elements to locate an element. Usually, the keys are designed to be easier to match. Most commonly used keys are numbers and strings.

In addition to operations of storing and retrieving elements, we should also be able to remove an element, search for a specific element, and iterate through all elements in a collections. So there are 5 major operations for any collections:

• Storing an element into the collection.
• Retrieving an element out of the collection.
• Removing an element from the collection.
• Searching for an element in the collection.
• Iterating through all the elements in the collection.

(Continued on next part...)

Part:   1   2  3  4