Java Collections Cheat Sheet: The Framework Explained

The core interfaces

Everything in the Collections Framework hangs off a few interfaces. Collection is the root for groups of individual elements, and it branches into List, Set and Queue. Map sits separately because it stores key-value pairs rather than single elements. Understanding these four - List, Set, Queue and Map - and how they differ is the foundation for everything else.

The differences are about rules: a List is an ordered sequence that allows duplicates and index access; a Set is a collection that forbids duplicate elements; a Queue holds elements for processing, typically in FIFO order; and a Map associates unique keys with values. Get these distinctions clear and the many concrete classes fall into place as implementations of these ideas.

List, Set, Map, Queue: key implementations

Each interface has a handful of implementations you'll actually use. Here's the practical cheat sheet:

• ✓List - ArrayList (fast random access, backed by a resizable array) and LinkedList (fast insertion/removal at ends, backed by a doubly linked list).
• ✓Set - HashSet (fast, unordered, uses hashing), LinkedHashSet (maintains insertion order), TreeSet (keeps elements sorted).
• ✓Map - HashMap (fast key-value lookup, unordered), LinkedHashMap (insertion order), TreeMap (sorted by key), Hashtable (legacy, synchronised).
• ✓Queue / Deque - ArrayDeque (efficient double-ended queue) and PriorityQueue (orders elements by priority).
• ✓Thread-safe options - ConcurrentHashMap and the collections from java.util.concurrent for multi-threaded use.

When to use which

Knowing the classes matters less than knowing when to pick each - which is exactly the judgment interviews and real code demand. Use an ArrayList when you mostly read by index and append; use a LinkedList when you frequently insert or remove at the ends. Choose a HashSet or HashMap when you want fast lookups and don't care about order; choose the TreeSet or TreeMap when you need sorted order; choose the LinkedHash variants when you need to preserve insertion order.

Reach for a Deque (ArrayDeque) for stack or queue behaviour, and a PriorityQueue when you always need the highest- or lowest-priority element next. For multi-threaded access, prefer the concurrent collections over legacy synchronised ones. The pattern is always: match the data structure's strengths to what your code does most.

Time and space complexity at a glance

Interviews and real performance decisions hinge on the cost of each operation. Approximate average-case complexities for the most-used collections:

• ✓ArrayList: get/set by index O(1); add at the end amortised O(1); insert/remove at an index O(n); contains O(n).
• ✓LinkedList: add/remove at the ends O(1); get/set by index O(n); contains O(n).
• ✓HashMap / HashSet: get, put/add, remove and contains average O(1), degrading toward O(log n) or O(n) when many keys collide.
• ✓LinkedHashMap / LinkedHashSet: the same average O(1) as the hash versions, but they preserve insertion order.
• ✓TreeMap / TreeSet: get, put, remove and contains O(log n), and keys/elements stay sorted.
• ✓ArrayDeque: add/remove at either end O(1) - the preferred stack and queue.
• ✓PriorityQueue: offer and poll O(log n); peek O(1).

Essential methods you'll actually use

You rarely need the whole API - a core set of methods covers most day-to-day work:

• ✓List: add, get, set, remove, indexOf, contains, size, subList, and iteration with an enhanced for-loop or iterator.
• ✓Set: add, remove, contains, size - plus the set operations addAll (union), retainAll (intersection) and removeAll (difference).
• ✓Map: put, get, remove, containsKey, keySet, values, entrySet - and the handy getOrDefault, putIfAbsent, computeIfAbsent and merge.
• ✓Queue / Deque: offer, poll and peek for queue behaviour; push, pop, addFirst/addLast and pollFirst/pollLast for stack and deque use.
• ✓Sorting: Collections.sort with a Comparable natural order, or a Comparator (e.g. Comparator.comparing) for custom order.

How HashMap works (and why equals & hashCode matter)

HashMap is the most-asked collection in interviews, so understand its mechanism. A HashMap stores entries in an array of 'buckets'. When you put a key, it computes the key's hashCode, maps that to a bucket index, and stores the entry there; multiple keys landing in the same bucket form a chain (a linked list, which modern JDKs convert to a balanced tree once a bucket grows large). A get repeats the process to find the bucket, then uses equals to pick the right entry within it.

This is why a key's equals and hashCode must be consistent: two objects that are equal must return the same hashCode, or the map will store and look them up in different buckets and appear to 'lose' entries. It's also why immutable keys (like String and Integer) are safest - mutating a key after insertion changes its hashCode and breaks retrieval. When the map fills past its load factor, it resizes (rehashes) into a bigger array to keep operations near O(1).

Common interview comparisons

Interviewers love a few classic Collections comparisons, so know them cold. ArrayList vs LinkedList: array-backed fast random access versus linked-node fast end insertion. HashMap vs TreeMap: unordered fast lookup versus sorted keys. HashMap vs Hashtable: modern and non-synchronised versus legacy and synchronised. HashSet vs TreeSet: fast unordered versus sorted. Fail-fast versus fail-safe iterators, and how HashMap handles collisions, also come up often.

The strongest answers don't just recite differences - they explain the underlying reason (data structure, ordering, thread-safety) and when you'd choose one over the other. That 'why' is what separates a memorised answer from genuine understanding, and it's what these questions are really probing.