Java Collections Hierarchy

Java Collections Hierarchy

The Java Collections Framework is not a flat list of unrelated classes. It is a carefully designed hierarchy of interfaces and implementations where every concrete class — ArrayList, HashMap, TreeSet, ArrayDeque — fills a specific slot defined by the interface it implements. Once you understand the hierarchy, you stop memorising individual classes and start reasoning about which one fits a given problem.

This article maps every interface and implementation, shows you what each level of the hierarchy guarantees, and gives you working examples for each branch.

What Is the Collections Hierarchy?

The Collections hierarchy is the inheritance and implementation structure that organises all collection types in java.util and java.util.concurrent. Every collection either extends an interface or implements one — and those interfaces form a tree rooted at java.lang.Iterable.

The full hierarchy has two independent branches: the Collection branch for single-element containers, and the Map branch for key-value associations. Map does not extend Collection — the two branches are siblings, not parent and child.

COLLECTION BRANCH
=================

java.lang.Iterable<E>                        ← supports for-each loop
    └── java.util.Collection<E>              ← root of all single-element collections
            │
            ├── java.util.List<E>            ← ordered, allows duplicates, index access
            │       ├── ArrayList            (resizable array — default choice)
            │       ├── LinkedList           (doubly-linked nodes)
            │       ├── Vector               (legacy, synchronised)
            │       └── Stack                (legacy LIFO — extends Vector)
            │
            ├── java.util.Set<E>             ← unique elements, no duplicates
            │       ├── HashSet              (hash table, no order)
            │       ├── LinkedHashSet        (hash table + insertion order)
            │       └── SortedSet<E>
            │               └── NavigableSet<E>
            │                       └── TreeSet  (Red-Black tree, sorted order)
            │
            └── java.util.Queue<E>           ← ordered for processing, typically FIFO
                    ├── PriorityQueue        (min-heap, priority order)
                    └── java.util.Deque<E>   ← double-ended queue, both-end access
                            ├── ArrayDeque   (resizable array, modern default)
                            └── LinkedList   (also implements List and Deque)


MAP BRANCH (separate hierarchy — does NOT extend Collection)
============================================================

java.util.Map<K,V>                           ← key-value pairs, unique keys
        ├── HashMap                          (hash table, no key order)
        ├── LinkedHashMap                    (hash table + insertion order)
        ├── Hashtable                        (legacy, synchronised)
        └── SortedMap<K,V>
                └── NavigableMap<K,V>
                        └── TreeMap          (Red-Black tree, sorted keys)

The interfaces define contracts — what operations a collection supports. The concrete classes define implementation — how those operations work internally and what performance they provide.

The Interface Layers — What Each One Adds

Layer 1 — Iterable

java.lang.Iterable<E> is the root. It lives in java.lang so it is automatically imported. It declares one method: iterator(). Any class that implements Iterable can be used in a Java enhanced for-each loop. Every Collection extends Iterable, so every collection works with for-each automatically.

Output:
=== for-each loop (via Iterable) ===
  Java
  Python
  Go
=== explicit iterator (what for-each becomes) ===
  Java
  Python
  Go

Layer 2 — Collection

java.util.Collection<E> extends Iterable and adds the core group-management methods that every collection supports: add(), remove(), contains(), size(), isEmpty(), clear(), addAll(), removeAll(), retainAll(), and toArray().

Declaring a method parameter as Collection<T> makes it accept any List, Set, or Queue — the widest useful type for read and basic modification.

Output:
=== ArrayList passed as Collection ===
  Size     : 3
  Empty?   : false
  Has Java?: true
  Contents : [Java, Spring, Java]
=== HashSet passed as Collection ===
  Size     : 2
  Empty?   : false
  Has Java?: true
  Contents : [Spring, Java]

=== addAll and removeAll ===
  After removeAll(B,D): [A, C, E]
  After retainAll(A,C): [A, C]

Layer 3a — List

List<E> extends Collection and adds the contract for ordered, indexed access. It introduces get(int index), set(int index, E element), add(int index, E element), remove(int index), indexOf(Object o), subList(int from, int to), and listIterator(). The ordering guarantee and duplicate permission are what distinguish List from Set.

Output:
=== List-specific operations ===
get(1) on ArrayList  : Swiggy
get(1) on LinkedList : Swiggy
indexOf(Swiggy)      : 1
After set(0, Meesho) : [Meesho, Swiggy, Zomato]
subList(0,2)         : [Meesho, Swiggy]

=== Duplicates and order preserved ===
ArrayList with duplicates: [Meesho, Swiggy, Zomato, Swiggy, Swiggy]

Layer 3b — Set

Set<E> extends Collection and adds the uniqueness guarantee. It introduces no new methods beyond Collection — the contract change is purely behavioural: add() returns false and does nothing if the element already exists. The SortedSet sub-interface adds first(), last(), headSet(), tailSet(), and subSet(). NavigableSet extends SortedSet further with floor(), ceiling(), lower(), higher(), and descendingSet().

Output:
=== HashSet — fastest, no order ===
Contents  : [Delhi, Mumbai, Bengaluru]
add(Mumbai) again: false

=== LinkedHashSet — no duplicates, insertion order ===
Contents  : [Mumbai, Delhi, Bengaluru]

=== TreeSet — no duplicates, sorted order ===
Contents    : [10, 20, 50, 60, 80]
first()     : 10
last()      : 80
floor(55)   : 50
ceiling(55) : 60
headSet(50) : [10, 20]
tailSet(50) : [50, 60, 80]

Layer 3c — Queue and Deque

Queue<E> extends Collection and models a processing line. It adds two method pairs: add()/offer() (insert at tail — offer returns false on failure instead of throwing), and remove()/poll() (remove from head — poll returns null instead of throwing), plus element()/peek() (inspect head without removal). Deque extends Queue and adds operations on both ends.

Output:
=== ArrayDeque as Queue — FIFO ===
Queue     : [TICKET-001, TICKET-002, TICKET-003]
peek()    : TICKET-001
poll()    : TICKET-001
Remaining : [TICKET-002, TICKET-003]

=== ArrayDeque as Stack — LIFO (Deque) ===
History   : [/cart, /products, /home]
peek()    : /cart
pop()     : /cart
History   : [/products, /home]

=== PriorityQueue — processes smallest first ===
Processing order: 1 2 3 4 5

Layer 3d — Map (Separate Branch)

Map<K,V> does not extend Collection. It defines its own contract: unique keys mapped to values. Core methods: put(K,V), get(K), remove(K), containsKey(K), containsValue(V), keySet(), values(), entrySet(), size(), isEmpty(). SortedMap adds firstKey(), lastKey(), headMap(), tailMap(). NavigableMap extends SortedMap with floorKey(), ceilingKey(), and range views.

Output:
=== HashMap — fastest, no key order ===
Contents     : {Razorpay=2014, Paytm=2010, CRED=2018, PhonePe=2015}
get(PhonePe) : 2015
put replaces : 2018

=== LinkedHashMap — insertion order preserved ===
Contents : {Razorpay=2014, PhonePe=2015, Paytm=2010, CRED=2018}

=== TreeMap — keys sorted, NavigableMap methods ===
Sorted keys  : {CRED=2018, Paytm=2010, PhonePe=2015, Razorpay=2014}
firstKey()   : CRED
lastKey()    : Razorpay
floorKey(P)  : Paytm
ceilingKey(P): Paytm
headMap(P)   : {CRED=2018}

When to Use Each Level of the Hierarchy

Choosing the right level of the hierarchy prevents two common mistakes: being too specific (coupling code to ArrayList when List or Collection is sufficient) and being too vague (using Collection when the caller genuinely needs index access).

Use as a VARIABLE TYPE or PARAMETER TYPE:

  Iterable<T>     — only when a method needs to iterate (for-each only)
  Collection<T>   — when a method needs add/remove/contains/size + iteration
  List<T>         — when callers need index access, ordering, or subList
  Set<T>          — when the contract is uniqueness and no ordering
  Queue<T>        — when callers use offer/poll/peek FIFO semantics
  Deque<T>        — when both-end access is required
  Map<K,V>        — when key-value association is the contract
  SortedSet<T>    — when sorted iteration and range operations are needed
  NavigableSet<T> — when floor/ceiling/headSet/tailSet are needed
  SortedMap<K,V>  — when sorted key iteration is needed
  NavigableMap<K,V>— when floor/ceiling/headMap/tailMap are needed

Use as an IMPLEMENTATION (right side of assignment only):

  ArrayList       — default List: random access, bulk append, sequential scan
  LinkedList      — List + Deque: frequent head/tail insert-delete
  HashSet         — default Set: fastest add/contains/remove, no order
  LinkedHashSet   — Set with insertion order
  TreeSet         — Set with sorted order or range navigation
  ArrayDeque      — default Queue/Deque/Stack: fast both-end operations
  PriorityQueue   — Queue with priority ordering (min-heap)
  HashMap         — default Map: fastest put/get/remove, no key order
  LinkedHashMap   — Map with insertion order (or LRU with access order)
  TreeMap         — Map with sorted key order or range navigation

Internal Working of Each Branch

The diagram below shows how each major implementation stores data internally.

INTERNAL STRUCTURE COMPARISON

ArrayList (Object[]):
  ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
  │ A  │ B  │ C  │null│null│null│null│null│null│null│
  └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
  index: 0    1    2                              9
  size=3, capacity=10 — grows 1.5x when full

LinkedList (doubly-linked nodes):
  null ← [prev|A|next] ↔ [prev|B|next] ↔ [prev|C|next] → null
            ↑                                     ↑
          first                                 last
  O(1) at head/tail, O(n) at index

HashSet / HashMap (hash table — array of buckets):
  table[0]: null
  table[3]: Node("Java") → null
  table[5]: Node("Go")   → null
  table[7]: Node("Rust") → Node("Python") → null  ← collision chain
  hashCode(key) → bucket index → equals() for exact match
  O(1) average, degrades to O(n) on all-same-bucket collisions
  Java 8+: converts chains > 8 to Red-Black tree (O(log n) worst case)

TreeSet / TreeMap (Red-Black tree):
              30(B)
            /       \
          20(R)     50(R)
         /    \    /    \
       10(B) 25(B)40(B) 60(B)
  All keys in BST order — in-order traversal always sorted
  Guaranteed O(log n) for all operations regardless of insertion order

ArrayDeque (circular array — head and tail move instead of shifting):
  array: [null | "B" | "C" | "D" | null | null]
                  ↑                 ↑
                head              tail
  addFirst moves head left; addLast moves tail right
  Wraps around when end reached — no shifting needed

Basic Example

Output

Size: 2
Size: 2
List allows duplicates, Set does not.

How it works:

1. ›List<String> and Set<String> are both concrete implementations that sit under the same Collection<E> interface in the hierarchy — that is why the same printSize(Collection<String>) method accepts either one.
2. ›ArrayList keeps insertion order and allows duplicates, while HashSet enforces uniqueness — adding "Java" twice to the set leaves its size unchanged.
3. ›Writing a method against the Collection interface rather than a specific class (ArrayList or HashSet) is the core benefit of the hierarchy: the method works with any current or future Collection implementation.

Performance Considerations

Thread safety: All standard implementations above are not thread-safe. For concurrent use: ConcurrentHashMap for concurrent Map, CopyOnWriteArrayList for read-heavy concurrent List, ConcurrentLinkedQueue for concurrent Queue, Collections.synchronizedXxx() wrappers for simple single-lock access.

Best Practices

Declare variables and parameters using the widest interface that covers your operations. List<T> if callers need ordering and index access. Collection<T> if only iteration and basic add/remove are needed. Map<K,V> for key-value access. This makes code more flexible and communicates the contract clearly. During code reviews, declaring ArrayList<String> result = new ArrayList<>() as a method return type is a common flag — it forces callers to depend on a specific implementation unnecessarily.

Use NavigableSet and NavigableMap when sorted range operations are needed. Declaring NavigableMap<String,Integer> map = new TreeMap<>() exposes floorKey(), ceilingKey(), headMap(), and tailMap() that would be hidden behind a plain Map<K,V> declaration. Use the widest interface for parameters, but the most specific useful interface for variables where the extra methods are needed.

Program to the hierarchy, not to the implementation. When switching from HashSet to LinkedHashSet for iteration-order consistency, only the constructor line changes if the variable is declared as Set<T>. When switching from ArrayList to CopyOnWriteArrayList for thread safety, only the constructor changes if the variable is declared as List<T>. The hierarchy exists precisely to make substitution like this safe.

Use Map.merge() and Map.computeIfAbsent() for idiomatic accumulation patterns. map.merge(key, 1, Integer::sum) accumulates a counter without a null check. map.computeIfAbsent(key, k -> new ArrayList<>()).add(value) builds a multi-value map safely. These methods are part of the Map interface in Java 8+ and should replace the verbose if (map.containsKey(key)) / else patterns that appear in older code.

Common Mistakes

Mistake 1 — Using the Implementation Type as Parameter Type

Mistake 2 — Choosing a Collection Based on Name, Not Access Pattern

Mistake 3 — Ignoring That Map Is Not a Collection

Mistake 4 — Using Sorted Implementation Without Providing Comparable or Comparator

Interview Questions

Q1. What is the Java Collections hierarchy and how is it structured?

The hierarchy has two independent branches. The Collection branch starts with java.lang.Iterable, extends to java.util.Collection, and splits into List (ordered, duplicates allowed, indexed), Set (unique elements, no duplicates), and Queue (processing order, typically FIFO). The Map branch is completely separate — Map<K,V> does not extend Collection because its key-value structure does not fit the single-element add(E) contract. Both branches live in java.util. Understanding the two-branch structure is what interviewers at both service-based and product-based companies test first.

Q2. Why does Map not extend Collection in Java?

Collection<E> models a group of individual elements — it defines add(E element) as the insertion operation. Map<K,V> models associations between keys and values — every entry is inherently two things. There is no clean way to express add(Map.Entry<K,V>) as equivalent to add(E) without breaking the Collection contract semantics. The design decision to keep Map separate keeps the abstraction clean. You access Map data through collection views: keySet() returns Set<K>, values() returns Collection<V>, and entrySet() returns Set<Map.Entry<K,V>> — all of which participate normally in the Collection hierarchy.

Q3. What is the difference between Collection and Collections in Java?

java.util.Collection (singular) is an interface — the root of the Collection hierarchy. It defines the contract that List, Set, and Queue implement. java.util.Collections (plural) is a final utility class — it cannot be instantiated and has only static methods: sort(), reverse(), shuffle(), binarySearch(), min(), max(), frequency(), unmodifiableList(), synchronizedMap(), and more. This is one of the most common interview trick questions at service-based companies.

Q4. What is the difference between Iterable and Iterator?

Iterable<E> is an interface that a collection implements — it declares one method: iterator(). Any class implementing Iterable can be used in a for-each loop. Iterator<E> is what iterator() returns — the actual cursor object with hasNext(), next(), and remove() methods that do the traversal. Iterable is the factory; Iterator is the product. The distinction matters when you need to remove elements safely during traversal — you must call iterator.remove() on the Iterator, not collection.remove() on the Collection, to avoid ConcurrentModificationException.

Q5. What does the SortedSet and NavigableSet sub-hierarchy add to Set?

SortedSet<E> extends Set and adds the guarantee that elements are always in sorted order. It adds first(), last(), headSet(toElement) (elements less than toElement), tailSet(fromElement) (elements ≥ fromElement), and subSet(from, to). NavigableSet<E> extends SortedSet and adds floor/ceiling navigation: floor(e) (largest element ≤ e), ceiling(e) (smallest element ≥ e), lower(e) (largest element strictly < e), higher(e) (smallest element strictly > e), and descendingSet(). TreeSet is the only standard implementation of NavigableSet.

Q6. What is the difference between Comparable and Comparator in the Collections hierarchy?

Comparable<T> is implemented by a class to define its natural ordering — the single default sort order built into the class via compareTo(T other). TreeSet and TreeMap use this automatically when no comparator is provided. Comparator<T> is an external ordering strategy — a separate object or lambda that defines a custom sort order without modifying the class. A class can have only one Comparable ordering but unlimited Comparator orderings. In the hierarchy, TreeSet(Comparator) and TreeMap(Comparator) constructors accept an explicit Comparator, overriding whatever natural ordering the elements may have.

FAQs

What is the root of the Java Collections hierarchy?

java.lang.Iterable<E> is the root of the Collection branch. It is in java.lang (auto-imported) and declares the iterator() method that enables for-each loops. java.util.Collection<E> extends Iterable and is the root of the actual Collections Framework. Map<K,V> has its own separate root and does not participate in the Iterable/Collection chain directly.

Can I add any collection to another collection using addAll?

Yes — Collection.addAll(Collection<? extends E> c) accepts any collection whose element type is the same or a subtype. list.addAll(set) and set.addAll(list) both compile and work correctly. Map is not a Collection, so you cannot call list.addAll(map) directly — use list.addAll(map.values()) or list.addAll(map.keySet()) to add the collection views.

What is the difference between HashSet, LinkedHashSet, and TreeSet?

All three are Set implementations — all reject duplicates. HashSet uses a hash table — fastest for add/remove/contains at O(1) average, no guaranteed iteration order. LinkedHashSet extends HashSet and maintains insertion order through a doubly-linked list alongside the hash table — still O(1) average, slightly more memory, predictable iteration. TreeSet uses a Red-Black tree — O(log n) for all operations, but elements are always iterated in sorted ascending order and range navigation methods (floor, ceiling, headSet) are available.

When should I use LinkedList instead of ArrayList?

LinkedList is worth choosing when insertions and removals at the head (front) of the list are the primary operation on a large list — addFirst() and removeFirst() are O(1) on LinkedList, O(n) on ArrayList. For a FIFO queue, LinkedList as a Queue was historically common. However, ArrayDeque is now the recommended default for both stack and queue use — it is faster than LinkedList for head/tail operations due to lower memory overhead and better cache locality. Choose LinkedList only when you genuinely need both the List and Deque interfaces on the same object simultaneously.

What is the difference between HashMap and LinkedHashMap?

HashMap stores entries in a hash table — O(1) average for all operations, but iteration order is undefined and may change after a rehash. LinkedHashMap extends HashMap and maintains an additional doubly-linked list of all entries in either insertion order (default) or access order (when constructed with new LinkedHashMap<>(capacity, loadFactor, true)). Access-order mode makes LinkedHashMap the standard foundation for LRU (Least Recently Used) caches when combined with removeEldestEntry() override. The performance cost over HashMap is minimal.

What is the purpose of the NavigableMap interface?

NavigableMap<K,V> extends SortedMap and adds fine-grained navigation operations: floorKey(k) (largest key ≤ k), ceilingKey(k) (smallest key ≥ k), lowerKey(k) (largest key strictly < k), higherKey(k) (smallest key strictly > k), pollFirstEntry() (remove and return smallest), pollLastEntry() (remove and return largest), and descendingMap() (reverse-order view). TreeMap is the standard implementation. These methods are invaluable for range-based lookups — finding the nearest price, the next available time slot, or all keys within a date range.

How does the hierarchy help with writing flexible, reusable methods?

The hierarchy lets you write methods that accept the widest contract needed, making them reusable with any conforming implementation. A method that accepts Collection<T> works with ArrayList, HashSet, TreeSet, or LinkedList. A method that accepts Iterable<T> works with all of those plus custom classes. A method that only needs Map<K,V> works with HashMap, TreeMap, and LinkedHashMap interchangeably. Programming to the interface — not the implementation — is what the entire hierarchy is designed to enable.

Summary

The Java Collections hierarchy has two independent branches: Collection (with List, Set, and Queue sub-interfaces) for single-element containers, and Map for key-value associations. Every concrete class — ArrayList, HashSet, TreeMap, ArrayDeque — implements one or more interfaces from this hierarchy, and the interface level determines what operations are available and what performance those operations provide.

The hierarchy solves one fundamental problem: writing code that works with the right contract, not the right class. A method accepting List<T> works with ArrayList and LinkedList. A method accepting Collection<T> works with all lists, sets, and queues. A method accepting Map<K,V> works with every map implementation. This substitutability — guaranteed by the hierarchy — is what makes Java collections reusable, testable, and maintainable across large codebases.

For interviews: draw the hierarchy from memory, explain why Map does not extend Collection, know the difference between Collection and Collections, and understand what each interface layer adds beyond its parent.

What to Read Next