Skip to content

Instantly share code, notes, and snippets.

@coderfiregun

coderfiregun/java collections.md

Last active November 1, 2025 03:55
Show Gist options
  • Save coderfiregun/52d159ae75ee2a12b4993db74ce28b7c to your computer and use it in GitHub Desktop.
Save coderfiregun/52d159ae75ee2a12b4993db74ce28b7c to your computer and use it in GitHub Desktop.
Download ZIP
Java Collections
Raw
java collections.md

🎯 Java Collections — LLD Interview Cheatsheet

Organized by Collection Hierarchy for easy memorization
Interface methods → Implementations → Complexities

📊 Table of Contents

  1. Collection Hierarchy Overview
  2. List Interface & Implementations
  3. Set Interface & Implementations
  4. Queue/Deque Interface & Implementations
  5. Map Interface & Implementations
  6. Sample Usage Examples
  7. Quick Decision Guide

🌲 Collection Hierarchy Overview

Collection (interface)
├── List (interface)
│   ├── ArrayList
│   ├── LinkedList
│   ├── Vector (legacy)
│   └── CopyOnWriteArrayList (concurrent)
│
├── Set (interface)
│   ├── HashSet
│   ├── LinkedHashSet
│   │
│   └── SortedSet (interface)
│       └── NavigableSet (interface)
│           ├── TreeSet
│           └── ConcurrentSkipListSet (concurrent)
│   
│   └── CopyOnWriteArraySet (concurrent)
│
└── Queue (interface)
    ├── PriorityQueue
    ├── ConcurrentLinkedQueue (concurrent)
    │
    ├── Deque (interface)
    │   ├── ArrayDeque
    │   ├── LinkedList
    │   └── ConcurrentLinkedDeque (concurrent)
    │
    └── BlockingQueue (interface, concurrent)
        ├── ArrayBlockingQueue
        ├── LinkedBlockingQueue
        ├── PriorityBlockingQueue
        ├── DelayQueue
        └── SynchronousQueue

Map (separate hierarchy)
├── HashMap
├── LinkedHashMap
├── Hashtable (legacy)
├── ConcurrentHashMap (concurrent)
│
└── SortedMap (interface)
    └── NavigableMap (interface)
        ├── TreeMap
        └── ConcurrentSkipListMap (concurrent)

└── Special: EnumMap, IdentityHashMap, WeakHashMap

📋 List Interface & Implementations

List Interface Methods

// Basic operations
boolean add(E e)           // Add at end
void add(int index, E e)   // Add at index
E get(int index)           // Access by index
E set(int index, E e)      // Replace at index
E remove(int index)        // Remove by index
boolean remove(Object o)   // Remove by value
int size()
boolean contains(Object o)
void clear()
int indexOf(Object o)
List<E> subList(int from, int to)

Implementations & Complexities

Implementation add(e) add(i,e) get(i) set(i,e) remove(i) remove(o) contains
ArrayList O(1)* O(n) O(1) O(1) O(n) O(n) O(n)
LinkedList O(1) O(n) O(n) O(n) O(n) O(n) O(n)
Vector O(1)* O(n) O(1) O(1) O(n) O(n) O(n)
CopyOnWriteArrayList O(n) O(n) O(1) O(n) O(n) O(n) O(n)

*Amortized O(1) due to dynamic resizing

LinkedList as Deque (Additional O(1) operations)

addFirst(e), addLast(e)
removeFirst(), removeLast()
getFirst(), getLast()

When to Use

  • ArrayList: Default choice, fast random access
  • LinkedList: Frequent operations at head/tail (use as Deque)
  • CopyOnWriteArrayList: Thread-safe, read-heavy workloads (90%+ reads)

🔑 Set Interface & Implementations

1️⃣ Set Interface (Base)

// Basic operations
boolean add(E e)
boolean remove(Object o)
boolean contains(Object o)
int size()
boolean isEmpty()
void clear()

Implementations:

Implementation add remove contains Ordering Null Thread-Safe
HashSet O(1) O(1) O(1) None ✅ (1) ❌
LinkedHashSet O(1) O(1) O(1) Insertion ✅ (1) ❌

2️⃣ SortedSet Interface (extends Set)

Additional methods for sorted collections:

E first()                           // Lowest element
E last()                            // Highest element
SortedSet<E> headSet(E toElement)   // Elements < toElement
SortedSet<E> tailSet(E fromElement) // Elements >= fromElement
SortedSet<E> subSet(E from, E to)   // Elements in range [from, to)
Comparator<? super E> comparator()  // Returns comparator or null

3️⃣ NavigableSet Interface (extends SortedSet)

Additional navigation methods:

// Navigation (find nearest elements)
E lower(E e)           // Greatest element strictly < e
E floor(E e)           // Greatest element <= e
E ceiling(E e)         // Smallest element >= e
E higher(E e)          // Smallest element strictly > e

// Retrieval and removal
E pollFirst()          // Remove and return lowest
E pollLast()           // Remove and return highest

// Range views (inclusive/exclusive bounds)
NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean inclusive)
NavigableSet<E> tailSet(E from, boolean inclusive)

// Reverse view
NavigableSet<E> descendingSet()
Iterator<E> descendingIterator()

Implementations:

Implementation add remove contains first/last ceiling/floor Null Thread-Safe
TreeSet O(log n) O(log n) O(log n) O(log n) O(log n) ❌ ❌
ConcurrentSkipListSet O(log n) O(log n) O(log n) O(log n) O(log n) ❌ ✅

Concurrent Sets (Special)

Implementation add remove contains Use Case
CopyOnWriteArraySet O(n) O(n) O(n) Read-heavy, rare writes

When to Use Sets

  • HashSet: Fast lookup, no ordering
  • LinkedHashSet: Preserve insertion order
  • TreeSet: Sorted order + range queries (NavigableSet methods)
  • ConcurrentSkipListSet: Thread-safe + sorted
  • CopyOnWriteArraySet: Thread-safe + read-heavy

🧺 Queue/Deque Interface & Implementations

1️⃣ Queue Interface (Base)

// Add operations (return false/throw on failure)
boolean offer(E e)     // Add if possible, return false if full
boolean add(E e)       // Add or throw exception

// Remove operations
E poll()               // Remove head, return null if empty
E remove()             // Remove head, throw exception if empty

// Examine operations
E peek()               // Return head, null if empty
E element()            // Return head, throw exception if empty

Implementations:

Implementation offer/add poll/remove peek Use Case
PriorityQueue O(log n) O(log n) O(1) Priority-based (min-heap)
ConcurrentLinkedQueue O(1) O(1) O(1) Non-blocking, unbounded

2️⃣ Deque Interface (extends Queue)

Additional double-ended operations:

// First element operations
offerFirst(e), addFirst(e)
pollFirst(), removeFirst()
peekFirst(), getFirst()

// Last element operations
offerLast(e), addLast(e)
pollLast(), removeLast()
peekLast(), getLast()

// Stack operations (use Deque instead of Stack!)
push(e)   // Same as addFirst()
pop()     // Same as removeFirst()

Implementations:

Implementation offer poll peek Use Case
ArrayDeque O(1) O(1) O(1) Default stack/queue
LinkedList O(1) O(1) O(1) Implements List + Deque
ConcurrentLinkedDeque O(1) O(1) O(1) Thread-safe deque

3️⃣ BlockingQueue Interface (extends Queue)

Additional blocking operations for thread coordination:

// Blocking operations
void put(E e) throws InterruptedException        // Block if full
E take() throws InterruptedException             // Block if empty

// Timed operations
boolean offer(E e, long timeout, TimeUnit unit)  // Try with timeout
E poll(long timeout, TimeUnit unit)              // Try with timeout

// Check capacity
int remainingCapacity()

Implementations:

Implementation offer poll take put Capacity Use Case
ArrayBlockingQueue O(1) O(1) O(1) O(1) Fixed Bounded producer-consumer
LinkedBlockingQueue O(1) O(1) O(1) O(1) Optional Unbounded producer-consumer
PriorityBlockingQueue O(log n) O(log n) O(log n) O(log n) Unbounded Priority queue, thread-safe
DelayQueue O(log n) O(log n) O(log n) O(log n) Unbounded Elements available after delay
SynchronousQueue O(1) O(1) O(1) O(1) 0 Direct handoff between threads

When to Use Queues

  • ArrayDeque: Default for stack/queue (single-threaded)
  • PriorityQueue: Task scheduling, top-K problems
  • ConcurrentLinkedQueue: Lock-free, high-throughput
  • ArrayBlockingQueue: Bounded producer-consumer
  • LinkedBlockingQueue: Optionally bounded producer-consumer
  • DelayQueue: Rate limiting, scheduled tasks
  • SynchronousQueue: Thread handoff (no storage)

🗺 Map Interface & Implementations

1️⃣ Map Interface (Base)

// Basic operations
V put(K key, V value)
V get(Object key)
V remove(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()
void clear()

// Views
Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()

// Java 8+ methods
V putIfAbsent(K key, V value)
V getOrDefault(Object key, V defaultValue)
V compute(K key, BiFunction<K,V,V> remappingFunction)
V computeIfAbsent(K key, Function<K,V> mappingFunction)
V computeIfPresent(K key, BiFunction<K,V,V> remappingFunction)
V merge(K key, V value, BiFunction<V,V,V> remappingFunction)

Implementations:

Implementation put get remove containsKey containsValue Null Key Null Value Thread-Safe
HashMap O(1) O(1) O(1) O(1) O(n) ✅ (1) ✅ ❌
LinkedHashMap O(1) O(1) O(1) O(1) O(n) ✅ (1) ✅ ❌
Hashtable O(1) O(1) O(1) O(1) O(n) ❌ ❌ ✅ (legacy)
ConcurrentHashMap O(1) O(1) O(1) O(1) O(n) ❌ ❌ ✅

LinkedHashMap Special Modes

// Insertion-order (default)
new LinkedHashMap<>()

// Access-order (for LRU cache)
new LinkedHashMap<>(capacity, 0.75f, true)

// Override for LRU eviction
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

2️⃣ SortedMap Interface (extends Map)

Additional methods for sorted maps:

K firstKey()                              // Lowest key
K lastKey()                               // Highest key
SortedMap<K,V> headMap(K toKey)           // Keys < toKey
SortedMap<K,V> tailMap(K fromKey)         // Keys >= fromKey
SortedMap<K,V> subMap(K fromKey, K toKey) // Keys in range [from, to)
Comparator<? super K> comparator()        // Returns comparator or null

3️⃣ NavigableMap Interface (extends SortedMap)

Additional navigation methods:

// Key navigation (find nearest keys)
K lowerKey(K key)           // Greatest key strictly < key
K floorKey(K key)           // Greatest key <= key
K ceilingKey(K key)         // Smallest key >= key
K higherKey(K key)          // Smallest key strictly > key

// Entry navigation
Map.Entry<K,V> lowerEntry(K key)
Map.Entry<K,V> floorEntry(K key)
Map.Entry<K,V> ceilingEntry(K key)
Map.Entry<K,V> higherEntry(K key)

// First/Last with removal
Map.Entry<K,V> pollFirstEntry()
Map.Entry<K,V> pollLastEntry()

// Range views (inclusive/exclusive bounds)
NavigableMap<K,V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
NavigableMap<K,V> headMap(K to, boolean inclusive)
NavigableMap<K,V> tailMap(K from, boolean inclusive)

// Reverse view
NavigableMap<K,V> descendingMap()
NavigableSet<K> descendingKeySet()

Implementations:

Implementation put get remove Ordering Thread-Safe
TreeMap O(log n) O(log n) O(log n) Sorted ❌
ConcurrentSkipListMap O(log n) O(log n) O(log n) Sorted ✅

Special Map Implementations

Implementation put get Special Behavior Use Case
EnumMap O(1) O(1) Keys must be enum Enum keys (fastest)
IdentityHashMap O(1) O(1) Uses == not equals() Object identity
WeakHashMap O(1) O(1) Keys are weak refs (GC eligible) Memory-sensitive caches

When to Use Maps

  • HashMap: Default choice, fast, no ordering
  • LinkedHashMap: Insertion order OR LRU cache (accessOrder=true)
  • TreeMap: Sorted keys + range queries (NavigableMap methods)
  • ConcurrentHashMap: Thread-safe, high concurrency
  • EnumMap: Keys are enums (ultra-fast)

💻 Sample Usage Examples

Example 1: LRU Cache (LinkedHashMap)

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

// Usage
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1);         // Access key 1
cache.put(4, "four"); // Evicts key 2 (LRU)

Example 2: Producer-Consumer (BlockingQueue)

BlockingQueue<Task> queue = new ArrayBlockingQueue<>(100);

// Producer
queue.put(new Task()); // Blocks if full

// Consumer
Task task = queue.take(); // Blocks if empty

Example 3: Range Queries (TreeMap NavigableMap)

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(5, "five");
map.put(10, "ten");
map.put(15, "fifteen");

// NavigableMap methods
map.ceilingKey(7);      // Returns 10
map.floorKey(7);        // Returns 5
map.higherKey(10);      // Returns 15
map.lowerKey(10);       // Returns 5

// Range views
NavigableMap<Integer, String> range = map.subMap(5, true, 12, false);
// Returns: {5=five, 10=ten}

// Descending order
NavigableMap<Integer, String> desc = map.descendingMap();

Example 4: Auto-complete (TreeMap subMap)

TreeMap<String, Integer> dictionary = new TreeMap<>();
dictionary.put("apple", 1);
dictionary.put("application", 2);
dictionary.put("apply", 3);
dictionary.put("banana", 4);

// Get all words starting with "app"
String prefix = "app";
SortedMap<String, Integer> suggestions = dictionary.subMap(
    prefix, 
    prefix + Character.MAX_VALUE
);
// Returns: {apple=1, application=2, apply=3}

Example 5: NavigableSet Range Operations (TreeSet)

TreeSet<Integer> scores = new TreeSet<>();
scores.addAll(Arrays.asList(10, 20, 30, 40, 50, 60));

// NavigableSet methods
scores.ceiling(25);     // Returns 30
scores.floor(25);       // Returns 20
scores.higher(30);      // Returns 40
scores.lower(30);       // Returns 20

// Range views
NavigableSet<Integer> range = scores.subSet(20, true, 50, false);
// Returns: [20, 30, 40]

// Descending
NavigableSet<Integer> desc = scores.descendingSet();
// Returns: [60, 50, 40, 30, 20, 10]

Example 6: Task Scheduler (PriorityQueue)

class Event {
    String name;
    long timestamp;
}

PriorityQueue<Event> scheduler = new PriorityQueue<>(
    Comparator.comparing(e -> e.timestamp)
);

scheduler.offer(new Event("Task1", System.currentTimeMillis() + 5000));
scheduler.offer(new Event("Task2", System.currentTimeMillis() + 2000));

while (!scheduler.isEmpty()) {
    Event next = scheduler.poll(); // Get earliest
    // Process event
}

Example 7: Top K Elements (PriorityQueue)

class Player {
    String name;
    int score;
}

// Min-heap of size K
PriorityQueue<Player> topK = new PriorityQueue<>(10, 
    Comparator.comparing(p -> p.score)
);

void addPlayer(Player player) {
    topK.offer(player);
    if (topK.size() > 10) {
        topK.poll(); // Remove lowest
    }
}

Example 8: Rate Limiter (DelayQueue)

class DelayedToken implements Delayed {
    private final long releaseTime;
    
    public DelayedToken(long delayMs) {
        this.releaseTime = System.currentTimeMillis() + delayMs;
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(
            releaseTime - System.currentTimeMillis(), 
            TimeUnit.MILLISECONDS
        );
    }
    
    @Override
    public int compareTo(Delayed o) {
        return Long.compare(this.releaseTime, 
                           ((DelayedToken) o).releaseTime);
    }
}

DelayQueue<DelayedToken> tokens = new DelayQueue<>();
tokens.offer(new DelayedToken(1000));
tokens.take(); // Blocks until available

Example 9: Thread-Safe Counter (ConcurrentHashMap)

ConcurrentHashMap<String, AtomicInteger> counters = new ConcurrentHashMap<>();

// Thread-safe increment
counters.computeIfAbsent(key, k -> new AtomicInteger(0))
        .incrementAndGet();

// Alternative
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.compute(key, (k, v) -> v == null ? 1 : v + 1);

Example 10: Frequency Counter (HashMap)

Map<String, Integer> frequency = new HashMap<>();

// Method 1
frequency.put(word, frequency.getOrDefault(word, 0) + 1);

// Method 2
frequency.compute(word, (k, v) -> v == null ? 1 : v + 1);

// Method 3
frequency.merge(word, 1, Integer::sum);

🎯 Quick Decision Guide

By Feature

Need thread-safety?
  → ConcurrentHashMap, CopyOnWriteArrayList, BlockingQueue implementations

Need ordering?
  None          → HashMap, HashSet
  Insertion     → LinkedHashMap, LinkedHashSet
  Sorted        → TreeMap (NavigableMap), TreeSet (NavigableSet)
  Access (LRU)  → LinkedHashMap(capacity, 0.75f, true)

Need range queries?
  → TreeMap (NavigableMap methods), TreeSet (NavigableSet methods)

Need priority-based?
  → PriorityQueue, PriorityBlockingQueue

Need blocking operations?
  → BlockingQueue implementations

Default choices:
  List  → ArrayList
  Set   → HashSet
  Map   → HashMap
  Queue → ArrayDeque
  Stack → ArrayDeque (NOT Stack class!)

⚖️ Key Comparisons

List

ArrayList vs LinkedList:
  ✅ ArrayList: Random access (default)
  ✅ LinkedList: Head/tail operations (as Deque)

ArrayList vs CopyOnWriteArrayList:
  ✅ ArrayList: Single-threaded
  ✅ CopyOnWriteArrayList: Thread-safe, read-heavy

Set

HashSet vs LinkedHashSet vs TreeSet:
  ✅ HashSet: Fast, no order
  ✅ LinkedHashSet: Insertion order
  ✅ TreeSet: Sorted + NavigableSet methods

TreeSet vs ConcurrentSkipListSet:
  ✅ TreeSet: Single-threaded
  ✅ ConcurrentSkipListSet: Thread-safe + sorted

Map

HashMap vs LinkedHashMap vs TreeMap:
  ✅ HashMap: Fast, no order
  ✅ LinkedHashMap: Insertion/access order, LRU
  ✅ TreeMap: Sorted + NavigableMap methods

HashMap vs ConcurrentHashMap:
  ✅ HashMap: Allows null, single-threaded
  ✅ ConcurrentHashMap: No null, thread-safe

Queue

ArrayDeque vs PriorityQueue:
  ✅ ArrayDeque: FIFO/LIFO
  ✅ PriorityQueue: Priority (min-heap)

ArrayBlockingQueue vs LinkedBlockingQueue:
  ✅ ArrayBlockingQueue: Fixed capacity
  ✅ LinkedBlockingQueue: Optionally bounded

ConcurrentLinkedQueue vs BlockingQueue:
  ✅ ConcurrentLinkedQueue: Non-blocking
  ✅ BlockingQueue: Blocking operations

📦 Space Complexity

Collection Space/Element Notes
ArrayList 4-8 bytes Array overhead
LinkedList 24+ bytes Node (2 pointers)
HashMap ~32 bytes Entry + array
TreeMap ~40 bytes Node (3 pointers + color)
ConcurrentHashMap ~40 bytes Concurrency overhead
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment