Comprehensive Overview of the Java Collection Framework: Interfaces, Implementations, and Usage

1. Collection Framework Diagram

Simplified diagram:

Explanation: The following points describe the diagram:

1. All collection classes reside in the java.util package. The Java collection hierarchy is derived from two root interfaces: Collection and Map. Both are the roots of the collection framework, each having several sub‑interfaces or implementing classes.

2. Collection interfaces: six interfaces (shown as short dashed lines) representing different collection types, forming the foundation of the framework.

3. Abstract classes: five abstract classes (long dashed lines) provide partial implementations of the collection interfaces and can be extended to create custom collections.

4. Concrete classes: eight concrete classes (solid lines) are actual implementations of the interfaces.

5. The Collection interface allows duplicate elements.

6. The Set interface extends Collection and does not allow duplicate elements.

7. The List interface extends Collection, allows duplicates, and maintains insertion order.

8. The Map interface represents key‑value pairs and is unrelated to Collection.

Three major collection categories:

List – ordered collection, elements can be accessed by index.

Set – unordered collection, no duplicate elements.

Map – key‑value mapping, keys are unique.

2. Overall Analysis

The core of the framework is the Collection and Map interfaces.

Collection: a highly abstract interface that defines basic operations. It has two major sub‑interfaces, List and Set.

List: an ordered queue where each element has an index (starting at 0). Implementations include LinkedList, ArrayList, Vector, and Stack.

Set: a collection that does not allow duplicate elements. Implementations include HashSet (backed by HashMap) and TreeSet (backed by TreeMap).

Map: a mapping interface of key‑value pairs. It does not inherit from Collection. Keys must be unique; values may repeat.

3. Collection Interface

The Collection interface is the root of all collection classes. It defines many methods for element manipulation. Note that Map is **not** a sub‑interface of Collection.

Commonly used methods include add(), addAll(), contains(), and toArray(). It also provides iterator() to obtain an Iterator for traversal.

1. List Interface

List represents an ordered collection where each element has a positional index and duplicates are allowed.

List extends Collection. Implementations are ArrayList, LinkedList, Vector, and Stack.

(1) ArrayList

ArrayList is a dynamic array. It expands its capacity automatically; specifying an initial capacity can reduce resizing overhead.

Key operations such as size, isEmpty, get, set, iterator, and listIterator run in constant time. add runs in amortized constant time.

ArrayList excels at random access and is non‑synchronized.

(2) LinkedList

LinkedList implements List as a doubly‑linked list. It provides additional methods get, remove, and insert at the head or tail.

Random access is inefficient because traversal is required. Insertions and deletions are cheap when performed near the ends.

LinkedList is also non‑synchronized; you can obtain a synchronized version via Collections.synchronizedList(new LinkedList<>()):

List list = Collections.synchronizedList(new LinkedList(...));

(3) Vector

Vector is similar to ArrayList but is synchronized, making it thread‑safe.

(4) Stack

Stack extends Vector to provide a LIFO stack with methods push, pop, peek, empty, and search.

2. Set Interface

Set is a collection that does not allow duplicate elements. It may contain at most one null element.

Implementations include HashSet, LinkedHashSet, and TreeSet. Elements must be distinct according to equals() and, for hash‑based sets, also have matching hashCode().

HashSet

HashSet is backed by a HashMap. It does not guarantee order, allows one null, and is non‑synchronized. It offers fast lookup based on hash codes.

Common pitfalls: storing null (only one allowed), assuming element positions are fixed (they are determined by hash codes), and mutating objects that affect hashCode() / equals() after insertion.

LinkedHashSet

LinkedHashSet extends HashSet and maintains insertion order using a linked list. Iteration follows the order of insertion.

TreeSet

TreeSet is a sorted set backed by a TreeMap. It stores elements in natural order or a custom order defined by a Comparator. It does not allow null keys.

4. Map Interface

Map stores key‑value pairs. Keys must be unique; values may repeat. It does not extend Collection.

1. HashMap

HashMap uses a hash table for fast key‑based access. It permits one null key and multiple null values. It is not synchronized.

2. LinkedHashMap

LinkedHashMap extends HashMap and preserves insertion order (or access order if configured). It is slightly slower than HashMap due to the linked list.

3. TreeMap

TreeMap is a sorted map implemented with a red‑black tree. Keys must implement Comparable (or a custom Comparator must be supplied). It does not allow null keys and is non‑synchronized.

5. Iterator and ListIterator Details

1. Iterator

Definition: public interface Iterator<E> {} Provides methods hasNext(), next(), and remove(). Example:

public class IteratorExample {
    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        Iterator<String> it = a.iterator();
        while (it.hasNext()) {
            String t = it.next();
            if ("bbb".equals(t)) {
                it.remove();
            }
        }
        System.out.println("After iterate : " + a);
    }
}

Output:

Before iterate : [aaa, bbb, ccc] After iterate : [aaa, ccc]

Notes:

Iterator moves only forward. remove() is the only safe way to modify the collection during iteration.

2. ListIterator

ListIterator extends Iterator and adds bidirectional traversal, index access, and element modification.

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

Example:

public class ListIteratorExample {
    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        ListIterator<String> it = a.listIterator();
        while (it.hasNext()) {
            System.out.println(it.next() + ", " + it.previousIndex() + ", " + it.nextIndex());
        }
        while (it.hasPrevious()) {
            System.out.print(it.previous() + " ");
        }
        System.out.println();
        it = a.listIterator(1);
        while (it.hasNext()) {
            String t = it.next();
            if ("ccc".equals(t)) {
                it.set("nnn");
            } else {
                it.add("kkk");
            }
        }
        System.out.println("After iterate : " + a);
    }
}

Output:

Before iterate : [aaa, bbb, ccc]
aaa, 0, 1
bbb, 1, 2
ccc, 2, 3
ccc bbb aaa 
bbb
ccc
After iterate : [aaa, bbb, kkk, nnn]

Key differences between Iterator and ListIterator:

ListIterator supports add(), set(), and bidirectional traversal.

Iterator only provides forward traversal and removal.

ListIterator can report current index via nextIndex() and previousIndex().

6. Differences Among Implementations

1. ArrayList vs. LinkedList

ArrayList uses a dynamic array; LinkedList uses a doubly‑linked list.

Random access ( get, set) is faster in ArrayList.

Insertions and deletions are cheaper in LinkedList for bulk operations.

2. Hashtable vs. HashMap

Both implement Map, Cloneable, and Serializable.

Hashtable is synchronized and does not allow null keys or values; HashMap is unsynchronized and permits one null key and multiple null values.

Hashtable extends Dictionary; HashMap extends AbstractMap.

3. HashMap, Hashtable, LinkedHashMap, TreeMap Comparison

HashMap is the most commonly used map; it offers fast access but iteration order is unpredictable. Hashtable provides thread safety at the cost of performance. LinkedHashMap maintains insertion order (or access order) and is useful when order matters. TreeMap keeps keys sorted (natural or custom) and does not allow null keys.

4. HashSet, LinkedHashSet, TreeSet Comparison

HashSet: unordered, allows one null, non‑synchronized.

LinkedHashSet: maintains insertion order, slightly slower on insertion than HashSet.

TreeSet: sorted set, does not allow null, non‑synchronized.

7. Collection vs. Collections

java.util.Collection is the root interface for all collection types (e.g., List, Set).

java.util.Collections is a utility class that provides static methods for sorting, searching, synchronizing, and otherwise operating on collections.

Example of using Collections.sort() on a List:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestCollections {
    public static void main(String[] args) {
        List list = new ArrayList();
        double[] array = {112, 111, 23, 456, 231};
        for (int i = 0; i < array.length; i++) {
            list.add(new Double(array[i]));
        }
        Collections.sort(list);
        for (int i = 0; i < array.length; i++) {
            System.out.println(list.get(i));
        }
        // Output: 23.0 111.0 112.0 231.0 456.0
    }
}

END

Scan the QR code above for more Java resources.