🎯 What you will learn
Arrays have a fixed size and only one type. The Java Collections Framework gives you dynamic, generic data structures for every common need. By the end of this lesson you will understand:
- List — ordered, allows duplicates, index-based access (ArrayList)
- Set — no duplicates; HashSet, LinkedHashSet, TreeSet
- Map — key-value pairs, unique keys; HashMap, TreeMap
- Program to the interface: declare as
List<T>, instantiate asnew ArrayList<>() - Common pitfalls: concurrent modification, null returns from get(), ordering surprises
🛒 Real-world scenario
NaijaCart processes 50,000 orders per day across Nigeria. Tunde, a backend engineer, needs three data structures: an ArrayList to hold cart items in insertion order, a HashSet to deduplicate duplicate webhook events, and a HashMap to look up product prices in O(1). Each structure trades off ordering, uniqueness guarantees, and lookup speed differently.
📚 The Java Collections Framework
java.util ships List, Set, and Map interfaces plus concrete implementations. All are generic — you declare the element type in angle brackets (e.g. List<String>). The golden rule: program to the interface, not the implementation — declare as List<T>, instantiate as new ArrayList<>(). Swapping implementations later requires only one line change.
| Interface | Ordered? | Duplicates? | Key impl | Lookup |
|---|---|---|---|---|
List | ✅ insertion order | ✅ allowed | ArrayList, LinkedList | O(1) index |
Set | ❌ (HashSet) / ✅ (LinkedHashSet) | ❌ not allowed | HashSet, TreeSet | O(1) avg |
Map | ❌ (HashMap) / ✅ (TreeMap sorted) | Keys unique | HashMap, TreeMap | O(1) avg |
📋 List — ordered and allows duplicates
An ArrayList stores elements in a resizable array. You get O(1) random access by index, O(n) insert/delete in the middle. Use it for cart items, result pages — any sequence where order matters and duplicates are fine.
Note: cart.remove("USB-C Cable") removes only the first occurrence. A second "USB-C Cable" remains until you call remove again. Use removeIf() to remove all matching elements in one call.
🔵 Set — no duplicates
A HashSet rejects duplicate elements silently — add() returns false if the element already exists. Use it to deduplicate webhook events, track visited IDs, or compute unique visitors.
🗺️ Map — key-value lookup
A HashMap maps unique keys to values and gives O(1) average lookup. Use it for product catalogues, caches, frequency counters, and any problem that needs "look up X by name".
Tip: Wrap a HashMap in a TreeMap — new TreeMap<>(existingMap) — to iterate in sorted key order without permanently changing the original structure.
⚠️ Common mistakes
list1 == list2 compares references. Use list1.equals(list2) to compare contents element by element.list.remove() inside a for-each throws ConcurrentModificationException. Use an Iterator or collect removals and call removeAll after.HashSet order is unpredictable and can change between JVM versions. Use LinkedHashSet for insertion order, TreeSet for sorted order.prices.get("Tablet") returns null if the key doesn't exist (not 0 or an exception). Use getOrDefault() or containsKey() before get() to avoid NullPointerException.🎤 Interview Q&A
ArrayList stores elements in a resizable array — O(1) random access by index, O(n) insert/delete in the middle. LinkedList stores elements in doubly-linked nodes — O(n) random access, O(1) insert/delete at head/tail. In practice, ArrayList is faster for most use cases due to better cache locality. Use LinkedList only when frequent head/tail insertions outweigh lookup costs.
HashMap does not synchronise reads or writes, so concurrent modifications from multiple threads can corrupt internal state. Use ConcurrentHashMap for concurrent access — it uses lock striping for high throughput. Alternatively, Collections.synchronizedMap(new HashMap<>()) wraps a HashMap with coarse locking, but ConcurrentHashMap is generally preferred.
HashSet internally uses a HashMap. When you call add(x), it computes x.hashCode() to find the bucket, then uses equals() to check if any element in that bucket matches. If both hash and equals agree, the element is a duplicate and is rejected. This is why you must override both hashCode() and equals() consistently for custom objects used in HashSets or as HashMap keys.
map.get(key) returns null when the key is absent, which can cause NullPointerException if you use the result without checking. getOrDefault(key, fallback) returns the fallback value instead of null, making the caller's code null-safe without an explicit null check. It's cleaner than map.containsKey(key) ? map.get(key) : fallback.
Average case: O(1). HashMap computes hashCode() to locate a bucket (array slot). If no collision, the entry is stored directly — O(1). If there's a collision, Java 8+ switches the bucket from a linked list to a balanced tree (red-black) once it exceeds 8 entries, keeping worst-case lookup at O(log n) per bucket rather than O(n). Overall put/get remain O(1) amortised assuming a good hash function and reasonable load factor (default 0.75).
📝 Quiz — 5 questions
map.get("key") returns what when the key doesn't exist?TreeSet vs HashSet — what's the difference?Next: Generics and Bounded Types →
✅ Key takeaways
- List: ordered, allows duplicates, index-based access. ArrayList for most cases.
- Set: no duplicates. HashSet for speed, LinkedHashSet for insertion order, TreeSet for sorted.
- Map: key-value, unique keys. HashMap O(1) avg; TreeMap sorted by key.
- Always program to the interface:
List<String> x = new ArrayList<>(). - Override
hashCode()andequals()consistently for objects in Sets/Maps.
From collections to production Spring Boot
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →