Collection OverviewJ8 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 Java 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>
- When we use the term Collections using an uppercase C and ending with an s, we are referring to the
java.util.Collectionsclass that contains a lot ofstaticutility methods we can use with our collections.
We go into great detail about the angled brackets <E> notation in the section on generics, 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 Hierarchy | Map Hierarchy | Utilities Hierarchy | ||
|---|---|---|---|---|
| Lists | Queues | Sets | Maps | Utilities |
ArrayList | PriorityQueue | HashSet | HashMap | Arrays |
Vector | LinkedHashSet | Hashtable | Collections | |
LinkedList | TreeSet | LinkedHashMap | ||
TreeMap | ||||
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 Diagram 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 Interfaces & Classes 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 Ordering Top
The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:
| Collection Type | Ordering | |||
|---|---|---|---|---|
| Lists | Queues | Sets | Ordered | Sorted |
ArrayList<E> | By the index | No | ||
Vector<E> | By the index | No | ||
LinkedList<E> | By the index | No | ||
PriorityQueue<E> | Sorted | PIPO | ||
HashSet<E> | No | No | ||
LinkedHashSet<E> | By insertion order | No | ||
TreeSet<E> | Sorted | Natural/bespoke order | ||
Map Hierarchy Diagram 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 Interfaces & Classes 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 Ordering Top
The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:
| Collection Type | Ordering | |
|---|---|---|
| Map | Ordered | Sorted |
HashMap<K,V> | No | No |
LinkedHashMap<K,V> | By insertion order or last access order | No |
Hashtable<K,V> | No | No |
TreeMap<K,V> | Sorted | By natural order or bespoke order |
Utilities Hierarchy Diagram 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 Classes 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.Arrays | Utility class for manipulating arrays. |
java.util.Collections | Utility class for manipulating collections. |
Java Documentation 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 first of three lessons on the different collection types within the Collection hierarchy we look at Set collection type.