Collection OverviewS2C Home « Collection Overview

In our first lesson on collections we look at the collection interfaces and classes using various diagrams and explain the terminology used when dealing with collections. So what is a collection? You can think of a collection as a generic type that allows us to store and iterate over data. We have already used one such collection when we looked at the Array object in the Objects & Classes section.

In this section we look at several more collections that allow us more flexibility and structure than the indexing mechanism of a basic array. The major caveat being that you can only store reference variables in collections, whereas you can store primitives and reference variables in basic arrays. With the advent of autoboxing in Java5 this is easily solved using one of the primitive wrapper classes to wrap our primitives in prior to adding them to a collection. The collection interfaces and classes we will cover in this section all reside in the java.util package and are commonly known as The Collections Framework.

Before we start our studies of the The Collections Framework we should clarify our use of the word 'collection' as used in general Java terminology and on this site:

  • When we use the term collection(s) using a lowercase c, this applies to any of the collection types we can store and iterate over. These being:
    • Lists
    • Maps
    • Queues
    • Sets
  • When we use the term Collection using an uppercase C, we are referring to the java.util.Collection<E> interface from which:
    • List<E>
    • Queue<E>
    • Set<E>
    extend.
  • When we use the term Collections using an uppercase C and ending with an s, we are referring to the java.util.Collections class that contains a lot of static utility methods we can use with our collections.

We will talk about the angled brackets <E> notation when we talk about Generics in the next lesson; for now think of it as a parameterized type of Element within the collection.

The table below lists the concrete implementation classes of the various collection types and utilities that are covered on the site. Click a link to go to detailed information about a particuar class:

Collection Types/Utilities & Concrete Implementation Classes
Collection Hierarchy Map Hierarchy Utilities Hierarchy
ListsQueuesSetsMapsUtilities
ArrayListPriorityQueueHashSetHashMapArrays
VectorLinkedHashSetHashtableCollections
LinkedListTreeSetLinkedHashMap
TreeSet

The table above shows we have two utility classes for use with collections as well as four collection types, these being lists, maps, queues and sets. Each collection type can be further divided by whether it is ordered and unsorted, or both sorted and ordered or finally both unsorted and unordered. Ordered collections allow us to iterate over our collections in a specific pre-determined way. Sorted collections are ordered according to the sort order and as such the ordering is defined by the sorting rules. This is the reason we can't have sorted unordered collections, as the sort order implicitly defines the ordering; but we can have ordered collections that are unsorted.

The sort order is derived from properties within the objects being sorted and can be based on natural ordering such as alphabetically or numerically or in a bespoke order as defined by the programmer. We will expand on the last paragraph when we look at the sorted collection types the terminology applies to as we work through the section.

There is quite a lot of information to assimilate when using collections so lets look at some hierarchy diagrams to clarify the points made so far and give an overview of what's to come:

Collection Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Collection hierarchy and covers the interfaces and classes we will study in this section. The diagram has several interfaces missing and also the java.util.EnumSet<E> and java.util.Stack<E> concrete implemetations which are not covered on the site, but should help in visualisation:

collection hierarchy

Collection Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Collection<E>The root interface in the Collection hierarchy which the List<E>, Queue<E> and Set<E> interfaces extend. There is no direct implementation of the Collection<E> interface within the JDK.
List<E>Interface for ordered collections of elements.
Queue<E>Interface for holding elements prior to processing.
Set<E>Interface for unique collections of elements.
ArrayList<E>Random access, resizable-array implementation of the List<E> interface that implements all optional list operations and permits all elements, including null.
Vector<E>Synchronized random access resizable-array implementation of the List<E> interface.
LinkedList<E>Sequential access linked implementation of the List<E> interface that implements all optional list operations, and permits all elements, including null. The class also implements the Queue<E> interface, providing first-in-first-out queue operations.
PriorityQueue<E>Unbounded priority queue implementation of the Queue<E> interface based on a priority heap that does not permit null elements.
HashSet<E>Implementation of the Set<E> interface using a HashMap instance.
LinkedHashSet<E>Hash table and linked list implementation of the Set<E> interface that implements all optional set operations and permits all elements, including null.
SortedSet<E>Interface for unique collections of sorted elements.
TreeSet<E>Implementation of the Set<E> interface using a TreeMap instance.

Collection Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:

Collection Type Ordering
ListsQueuesSetsOrderedSorted
ArrayList<E>By the indexNo
Vector<E>By the indexNo
LinkedList<E>By the indexNo
PriorityQueue<E>SortedPIPO
HashSet<E>NoNo
LinkedHashSet<E>By insertion orderNo
TreeSet<E>SortedNatural/bespoke order

Map Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Map hierarchy and covers the interfaces and classes we will study in this section. The diagram has several interfaces missing and also the java.util.WeakHashMap<K,V> and java.util.IdentityHashMap<K,V> concrete implemetations which are not covered on the site, but should help in visualisation:

map hierarchy

Map Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Map<K,V>The root interface in the map hierarchy which the SortedMap<K,V> interface extends.
HashMap<K,V>Hash table based implementation of the Map<K,V> interface that implements all optional map operations and permits all elements, including null and the null key.
LinkedHashMap<K,V>Hash table and linked list implementation of the Map<K,V> interface with predictable ordering and permits all elements, including null elements.
Hashtable<K,V>Hash table implementation of the Map<K,V> interface that doesn't allow null elements or null keys.
SortedMap<K,V>Interface for sorted map elements.
TreeMap<K,V>Random access tree based implementation of the SortedMap<K,V> interface.

Map Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:

Collection Type Ordering
MapOrderedSorted
HashMap<K,V>NoNo
LinkedHashMap<K,V>By insertion order or last access orderNo
Hashtable<K,V>NoNo
TreeMap<K,V>SortedBy natural order or bespoke order

Utilities Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the utilities hierarchy and covers the java.util.Arrays and java.util.Collections classes which we will study in this section. These classes are genral utility classes and give us some useful static methods to use with arrays and collections.

utilities hierarchy

Utilities Classesgo to top of page Top

The table below gives a description of the classes within the above diagram. Click a link to go to detailed information about a particuar class:

Class Description
java.util.ArraysUtility class for manipulating arrays.
java.util.CollectionsUtility class for manipulating collections.

Java Documentationgo to top of page Top

As mentioned in the other sections Java comes with very rich documentation. The following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. We haven't taken a formal look at the Collection<E> interface as there is no direct implementation and we will discuss the other interfaces that extend it in more detail in the relevant lessons. For now take a look at the documentation for the Collection<E> interface which you can find by scrolling down the upper left pane and clicking on java.util, then go to the lower left pane and click on Collection under the Interfaces Heading. You will go back to this documentation time and time again so if you haven't done so already I suggest adding this link to your browser's favourites toolbar for fast access.

Lesson 1 Complete

In this lesson we looked at an overview of the Collection Framework.


What's Next?

In the next lesson we unravel the terminology behind generics and look at some of the the strange syntax we get with it.

go to home page Homepage go to top of page Top