All topics
122 / 101
library
beginner

Java Collections Framework Overview

Navigate the JCF hierarchy: know which interface to use, which implementation to pick, and the time complexities.

One hierarchy, and the decision is which interface you need, then which implementation.

JCF = a well-organized kitchen. Lists = shelves (ordered). Sets = spice rack (no duplicates). Maps = labeled drawers (key → value). Queues = prep station (FIFO). Each has different containers optimized for different access patterns.

Key Concepts

1
    Iterable
      Collection
        List     ordered, duplicates allowed, indexed
        Set      no duplicates
        Queue    for processing in some order
          Deque  both ends
      Map        key to value -- NOT a Collection
2
Map is deliberately outside Collection, because its element is a pair, so add(E) makes no sense.
MapCollectionadd(E)
3
Pick the interface from the question.
    need an index or duplicates      List
    need uniqueness                  Set
    need lookup by key               Map
    need FIFO or LIFO                Deque
4
Then the implementation, with the default in the right column.
    List    ArrayList      O(1) get, O(1) amortised append      default
            LinkedList     O(n) get -- use only as a Deque
5
    Set     HashSet        O(1), no order                        default
            LinkedHashSet  O(1), insertion order
            TreeSet        O(log n), sorted, range queries
6
    Map     HashMap        O(1), no order                        default
            LinkedHashMap  O(1), insertion or access order
            TreeMap        O(log n), sorted, range queries
            ConcurrentHashMap   thread-safe, no locking on read
7
    Deque   ArrayDeque     O(1) both ends                        default
            PriorityQueue  O(log n), smallest first
8
ArrayList is almost always right for a list. LinkedList wins only when you insert and remove at the ends, and ArrayDeque beats it even there — because one array of references beats a node object per element for cache locality.
ArrayListLinkedListArrayDeque
9
The amortised cost of ArrayList.add is the detail worth knowing: the array doubles when full, so a single add is occasionally O(n) while the average stays O(1).
ArrayList.add
10
HashMap is O(1) only with a decent hashCode. All keys colliding degrades it to O(n), softened to O(log n) since Java 8, which turns a long bucket into a tree.
HashMaphashCode
11
The legacy classes to avoid.
    Vector       synchronized ArrayList      use ArrayList
    Hashtable    synchronized HashMap        use ConcurrentHashMap
    Stack        extends Vector              use ArrayDeque
12
And Collections.synchronizedMap is not the same as ConcurrentHashMap. The wrapper locks the whole map on every operation; ConcurrentHashMap locks per bucket and not at all for reads.
Collections.synchronizedMapConcurrentHashMap
13
What the interviewer is probing.1. "When would you choose LinkedList over ArrayList?" Probing: whether you repeat folklore or know the measurement. Stalls: "When you insert in the middle." Moves up: rarely — finding the position is O(n) anyway, and ArrayDeque beats it for queue use; ArrayList wins on cache locality almost everywhere.
14
2. "What does 'amortised O(1)' mean for ArrayList.add?" Probing: precision. Stalls: "It is always fast." Moves up: the array doubles when full, so one add is occasionally O(n) while the average stays constant.
15
3. "Why is HashMap O(1) only with a good hashCode?" Probing: the dependency. Stalls: "It is always O(1)." Moves up: all keys colliding degrades it to a single bucket — O(n), softened to O(log n) since Java 8 when a long bucket becomes a tree.
16
4. "Which legacy classes should you avoid and what replaces them?" Probing: currency. Stalls: "They are all fine." Moves up: Vector and Hashtable synchronise everything — use ArrayList and ConcurrentHashMap; Stack extends Vector — use ArrayDeque.
Use cases:CollectionsData StructuresFundamentals