🎯 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 as new ArrayList<>()
  • Common pitfalls: concurrent modification, null returns from get(), ordering surprises
💼 Interview reality: "Explain ArrayList vs LinkedList" and "How does HashMap work internally?" appear in nearly every Java backend interview. This lesson covers the what and when; the internal mechanics (hashing, load factor) appear in the interview Q&A below.

🛒 Real-world scenario

🛒
Real-world scenario · NaijaCart
NaijaCart — Tunde's order management engine (Lagos)

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.

InterfaceOrdered?Duplicates?Key implLookup
List✅ insertion order✅ allowedArrayList, LinkedListO(1) index
Set❌ (HashSet) / ✅ (LinkedHashSet)❌ not allowedHashSet, TreeSetO(1) avg
Map❌ (HashMap) / ✅ (TreeMap sorted)Keys uniqueHashMap, TreeMapO(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.

javac ListDemo.java && java ListDemo
ListDemo.javaLesson 14 · NaijaCart shopping cart
verified output
=== NaijaCart — Shopping Cart === Items added : [Phone Case, USB-C Cable, Screen Protector, USB-C Cable, Wireless Charger] Size : 5 Index 2 : Screen Protector Has cable? : true After remove: [Phone Case, Screen Protector, USB-C Cable, Wireless Charger] Sorted : [Phone Case, Screen Protector, USB-C Cable, Wireless Charger] Cart summary: 1. Phone Case 2. Screen Protector 3. USB-C Cable 4. Wireless Charger

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.

javac SetDemo.java && java SetDemo
SetDemo.javaLesson 14 · NaijaCart deduplication
verified output
=== NaijaCart — Deduplication with Set === Incoming events : 6 Unique orders : 4 (dropped 2 duplicates) Insertion order : [ORD-001, ORD-003, ORD-002, ORD-004] Sorted order : [ORD-001, ORD-002, ORD-003, ORD-004] Pending dispatch: [ORD-003, ORD-004]

🗺️ 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".

javac MapDemo.java && java MapDemo
MapDemo.javaLesson 14 · NaijaCart product catalogue
verified output
=== NaijaCart — Product Catalogue === Product Price (₦) -------------------------------------- Earbuds 5,800.00 Phone Case 1,500.00 Screen Protector 800.00 USB-C Cable 2,200.00 Wireless Charger 3,500.00 Lookup 'USB-C Cable': ₦2,200.00 Has 'Tablet'? : false 'Tablet' price : ₦0.00 (default) Catalogue total: ₦13,800.00 (5 items)

Tip: Wrap a HashMap in a TreeMap — new TreeMap<>(existingMap) — to iterate in sorted key order without permanently changing the original structure.

⚠️ Common mistakes

Using == to compare List contents
list1 == list2 compares references. Use list1.equals(list2) to compare contents element by element.
Iterating a List and removing elements
Calling list.remove() inside a for-each throws ConcurrentModificationException. Use an Iterator or collect removals and call removeAll after.
Expecting HashSet order to be consistent
HashSet order is unpredictable and can change between JVM versions. Use LinkedHashSet for insertion order, TreeSet for sorted order.
Confusing Map.get() returning null
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

EasyWhat is the difference between ArrayList and LinkedList?
+

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.

EasyWhy is HashMap not thread-safe and what should you use instead?
+

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.

MediumHow does HashSet detect duplicates?
+

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.

MediumWhat does getOrDefault() solve that get() does not?
+

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.

HardWhat is the time complexity of HashMap.put() and why?
+

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

Question 1 of 5
Which collection guarantees no duplicate elements?
Question 2 of 5
map.get("key") returns what when the key doesn't exist?
Question 3 of 5
Which List method inserts at a specific index?
Question 4 of 5
TreeSet vs HashSet — what's the difference?
Question 5 of 5
To iterate a Map by key→value pairs, use:
0
/ 5
Quiz complete!

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() and equals() consistently for objects in Sets/Maps.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →