1. Collection Framework — Overview
Quick Reference
List
Duplicate + Ordered + Index Based
Queue
First In First Out (FIFO)
Synchronized
Thread Safe classes
Legacy
Older thread-safe classes, mostly superseded
Legend
List
Set
Queue
Map
Synchronized / Thread Safe
Legacy
Naming Patterns
Hash→No Insertion Order Guarantee
Linked→Insertion Order
Tree→Sorted Order
Collection vs Collections vs Map vs Arrays
TypeInterface
RepresentsGroup of Objects — List, Set, Queue
StoresSingle value elements
TypeUtility Class (java.util)
Providessort() reverse() shuffle() binarySearch() min() max()
StoresKey + Value pair (separate hierarchy from Collection)
TypeUtility Class for raw Java arrays (not Collections)
2. Hierarchy Trees
Collection Framework Hierarchy
│
│
├── Collection (I): Root Interface for List, Set and Queue.
│ │
│ ├── List (I): Duplicate Allowed, Insertion Order Preserved, Index Based
│ │ ├── ArrayList (C): Dynamic Array Structure, Random Access Fast, Middle Insertion/Deletion Slow
│ │ ├── LinkedList (C): Doubly Linked List Structure,Insertion/Deletion Fast, Random Access Slow
│ │ ├── Vector (C): Same as ArrayList, Synchronized & Thread Safe, Legacy
│ │ │ └── Stack (C): Last In First Out (LIFO)
│ │
│ ├── Set (I): Unique Elements (No Duplicates)
│ │ ├── HashSet (C): No Insertion Order Guarantee
│ │ │ └── LinkedHashSet (C): Insertion Order
│ │ │
│ │ └── SortedSet (I): Elements are automatically stored in sorted order
│ │ └── NavigableSet (I): SortedSet + Navigation Methods
│ │ └── TreeSet (C): Sorted Order, Red-Black Tree
│ │
│ └── Queue (I): First In First Out (FIFO)
│ ├── PriorityQueue (C): Based on Priority (Default: Ascending Order)
│ ├── Deque (I): Double Ended Queue
│ │ ├── ArrayDeque (C)
│ │ └── LinkedList (C)
│ │
│ └── BlockingQueue (I): Multithreading
│ ├── LinkedBlockingQueue (C)
│ ├── ArrayBlockingQueue (C)
│ └── PriorityBlockingQueue (C)
Map Hierarchy
└── Map (I): Key-Value Pair, Keys Unique, Values Duplicate
│
├── HashMap (C): No Insertion Order Guarantee, 1 Null Key Allowed
│ └── LinkedHashMap (C): Insertion Order, 1 Null Key Allowed
│
├── WeakHashMap (C): If key has no strong reference, GC can remove the corresponding entry
├── IdentityHashMap (C): Uses == instead of equals() for key comparison
├── Hashtable (C): Synchronized & Thread Safe, No Null Key/Value, Legacy, Whole Map Locked
├── ConcurrentHashMap (C): Modern Thread Safe Map, No Null Key/Value, Better Performance than Hashtable, Bucket/Node Locked
│
└── SortedMap (I): Keys are automatically stored in sorted order
└── NavigableMap (I): SortedMap + Navigation Methods
└── TreeMap (C): Sorted by Key, No Null Key, Red-Black Tree
3. List — ArrayList, LinkedList, Vector, Stack
Internal Structures
ArrayList — Dynamic Array
ArrayList[ E0 | E1 | E2 | ... | En ]
Contiguous memory → random access is O(1)
Growth Formula
Default capacity = 10. When full → New Capacity = Old + (Old / 2).
LinkedList — Doubly Linked List
NULL ← [Prev|A|Next] ⇄ [Prev|B|Next] ⇄ [Prev|C|Next] → NULL
Each node = Data + Next Pointer + Previous Pointer. Fast insert/delete at ends, slow random access.
Time Complexity
ArrayList
| Operation | Complexity |
|---|
| get(index) | O(1) |
| add(end) | O(1) |
| add(middle) | O(n) |
| remove(middle) | O(n) |
| contains() / search | O(n) |
LinkedList
| Operation | Complexity |
|---|
| get(index) | O(n) |
| add(first) / add(last) | O(1) |
| remove(first) / remove(last) | O(1) |
| search | O(n) |
ArrayList vs LinkedList vs Vector
ArrayList
Dynamic array, fast read, slow middle insert/delete, less memory.
Most Common Choice
Use: Employee List, Product List, Config Data
LinkedList
Doubly linked list, slow read, fast insert/delete, more memory.
Frequent Insert/Delete
Use: Undo/Redo, Browser History, Playlist
Vector / Stack
Legacy, synchronized, thread safe, slower than ArrayList. Stack = LIFO built on Vector.
Avoid in New Code
Prefer instead: ArrayDeque
Stack Flow (LIFO) & Performance Summary
push() / pop()
push(A)
→
push(B)
→
pop() returns B
Operations: push(), pop(), peek(). Real use: Undo, Browser Back, Books Stack. ArrayDeque is modern & faster than legacy Stack.
List Performance Summary
| Implementation | Read | Insert | Delete |
|---|
| ArrayList | Fast | Slow | Slow |
| LinkedList | Slow | Fast | Fast |
| Vector | Medium | Slow | Slow |
| Stack | Medium | Medium | Medium |
4. Set — HashSet, LinkedHashSet, TreeSet
HashSet Internal Working
add("Java")
→
hashCode()
→
Bucket
→
equals()
→
No Duplicate → Insert
HashSet is backed by a HashMap internally — elements are stored as keys, with a dummy constant object as the value.
TreeSet — Auto Sorted (Red-Black Tree)
Insert: 40, 20, 60, 30
↓
Sorted Automatically: 20, 30, 40, 60
Supports natural ordering or a custom Comparator; range queries and navigation methods (first(), last(), ceiling(), floor()).
Set Implementations Compared
HashSet
No order guarantee, one null allowed, fastest lookup.
add/remove/contains O(1)
Use: Unique Emails, User IDs, Product Codes
LinkedHashSet
Backed by LinkedHashMap, maintains insertion order, slightly slower + more memory.
O(1)
Use: Ordered unique data
TreeSet
Sorted order, no null, natural ordering or Comparator.
O(log n)
Use: Leaderboard, Rankings, Alphabetical Order
5. Queue & Deque — PriorityQueue, ArrayDeque, BlockingQueue
Queue Hierarchy
Collection → Queue (I) — FIFO
├── PriorityQueue (C): Binary Heap, priority order (not FIFO)
└── Deque (I): Double Ended Queue
├── ArrayDeque (C): resizable circular array, fastest
└── LinkedList (C): legacy queue/deque choice
Deque operations: addFirst(), addLast(), removeFirst(), removeLast() — all O(1) on ArrayDeque.
Queue Implementations
| Impl | Order | Insert/Remove |
|---|
| PriorityQueue | Priority (heap) | O(log n) |
| ArrayDeque | FIFO / Double Ended | O(1) |
| LinkedList (as Queue) | FIFO — Legacy Choice | O(1) |
BlockingQueue (multithreading): LinkedBlockingQueue, ArrayBlockingQueue, PriorityBlockingQueue.
When To Use — Real Examples
PriorityQueue→Task Scheduler, CPU Scheduling, Dijkstra, Top-N
ArrayDeque→Better than Stack & better than LinkedList as Queue
BlockingQueue→Producer-consumer, thread pool task queues
6. Map — HashMap, LinkedHashMap, TreeMap, Hashtable, ConcurrentHashMap
HashMap
Array → Bucket → Linked List → Red-Black Tree (Java 8+). Fast, unordered.
1 Null Key, Multiple Null ValuesNot Thread Safe
put/get/remove: O(1) avg
LinkedHashMap
HashMap + Doubly Linked List — maintains insertion order, supports LRU Cache.
O(1)
Use: LRU Cache, Recent Searches
TreeMap
Red-Black Tree, sorted keys, no null key, Comparator supported.
O(log n)
Use: Sorted key iteration, range queries
Hashtable
Legacy, synchronized, whole map locked, no null key/value — slower.
Avoid in New Code
Use instead: ConcurrentHashMap
ConcurrentHashMap
Modern thread-safe map, bucket/node-level locking, high concurrency, no null key/value.
Preferred For Multithreading
Use: Session Store, In-Memory Cache
WeakHashMap / IdentityHashMap
WeakHashMap: GC removes entry if key has no strong reference. IdentityHashMap: uses == instead of equals().
Rare / Special Purpose
Map Comparisons
Thread SafetyNot Thread Safe
NullAllows null key/value
SpeedFast, Preferred
Thread SafetyThread Safe (whole map locked)
NullNo null key/value
SpeedSlow, Legacy
ThreadingSingle Thread, No Synchronization
ThreadingMulti Thread, Fine-Grained Locking, High Performance
7. Hashing & HashMap Internal Working
General Hashing Flow
Key
→
hashCode()
→
Hash Function
→
Bucket Index
→
Store / Retrieve Value
hashCode() finds the bucket, equals() finds the exact object. Rule: equal objects must return the same hashCode(); different objects may share a hashCode (collision).
put() and get() Flow (need to use from collections)
put(key, value)
hashCode(key) → Bucket Index
↓
Bucket Empty? → Yes → Insert
↓ No (Collision)
equals() checks Linked List nodes
↓
Duplicate Key → Update Value / Else → Add Node
get(key)
hashCode(key) → Find Bucket
↓
Traverse Bucket, run equals()
↓
Key Found → Return Value
↓
Not Found → return null
Default Values, Collision Handling, Treeification & Load Factor
Default Config
Initial Capacity → 16
Load Factor → 0.75
Threshold → Capacity × Load Factor = 16 × 0.75 = 12
On inserting the 13th element → Resize (Rehashing) happens
Why 0.75? Best balance of memory use, performance, and low collision rate. Why capacity 16? Power of 2 → fast bucket index calculation.
Collision Handling
Java 7 → Linked List only
Java 8+ → Linked List, converts to Red-Black Tree if bucket nodes > 8 AND table capacity ≥ 64 (Treeification)
Untreeification → Tree reverts to Linked List if bucket size falls below 6
Rehashing & Time Complexity
Rehashing on Threshold Crossed
All existing nodes are rehashed and reassigned to new buckets on capacity growth.
HashMap Time Complexity
| Operation | Average | Worst |
|---|
| put() | O(1) | O(log n) |
| get() | O(1) | O(log n) |
| remove() | O(1) | O(log n) |
8. Iterator, ListIterator & Fail-Fast vs Fail-Safe
DirectionForward Only
Works OnAll Collections
MethodshasNext() next() remove()
DirectionForward + Backward
Works OnList only
Methodsprevious() hasPrevious() set() add()
For-each: simple, read only, cannot remove. Iterator: can safely remove during traversal via iterator.remove().
Works OnOriginal Collection
BehaviorThrows ConcurrentModificationException if modified during iteration
ExamplesArrayList, HashMap, HashSet, TreeMap
Works OnA Copy of the Collection
BehaviorNo exception, but more memory
ExamplesConcurrentHashMap, CopyOnWriteArrayList
9. Comparable vs Comparator & Sorting
PurposeNatural Sorting Order
ImplementedInside the class
MethodcompareTo()
LogicSingle Sorting Logic
Use WhenEmployee ID, Roll No, Product Code
PurposeCustom Sorting Order
ImplementedOutside the class
Methodcompare()
LogicMultiple Sorting Logics
Use WhenSalary, Name, Age, Department
compareTo() Return Values
Negative → current object is smaller
Zero → equal
Positive → current object is greater
Sorting APIs
Collections.sort(list) → natural order (Comparable)
Collections.sort(list, comparator) → custom order
list.sort(comparator) → Java 8+, preferred
Multi-level: Comparator.comparing().thenComparing().thenComparing()
Reverse: Collections.reverseOrder() / comparator.reversed()
10. Collections & Arrays Utility Classes
Collections Class — Common Methods
sort() reverse() shuffle() swap() fill() copy() binarySearch()
min() max() frequency() disjoint() rotate() replaceAll()
binarySearch() requires a sorted list. frequency() counts occurrences. min()/max() find smallest/largest element.
Arrays Class — Common Methods
sort() binarySearch() equals() fill() copyOf() copyOfRange() deepEquals() toString() stream()
Collections works with Collection objects (List, Set). Arrays works with raw Java arrays.
11. Performance Summary — All Collections
Set & Map — Search / Order
| Implementation | Search | Order |
|---|
| HashSet | O(1) | No |
| LinkedHashSet | O(1) | Insertion |
| TreeSet | O(log n) | Sorted |
| HashMap | O(1) | No |
| LinkedHashMap | O(1) | Insertion |
| TreeMap | O(log n) | Sorted |
| Hashtable | O(1) | No |
| ConcurrentHashMap | O(1) | No |
List & Queue — Insert / Remove
| Implementation | Read | Insert | Search |
|---|
| ArrayList | O(1) | O(n) | O(n) |
| LinkedList | O(n) | O(1)* | O(n) |
| Vector | O(1) | O(n) | O(n) |
| PriorityQueue | — | O(log n) | — |
| ArrayDeque | — | O(1) | — |
* O(1) only at head/tail of LinkedList.
12. Which Collection Should I Use?
Random Access→ArrayList
Frequent Insert/Delete→LinkedList
Unique Elements→HashSet
Ordered Unique Elements→LinkedHashSet
Sorted Unique Elements→TreeSet
Key-Value Storage→HashMap
Ordered Map→LinkedHashMap
Sorted Keys→TreeMap
Thread Safe Map→ConcurrentHashMap
Queue→ArrayDeque
Priority Processing→PriorityQueue
Real Project Use Cases
ArrayList→Employee/Customer/Order List
LinkedList→Undo/Redo, Browser History, Playlist
HashSet→Unique Emails, Roles, Tags
TreeSet→Leaderboard, Ranking, Scoreboard
HashMap→Caching, Config, Session Data, API Mapping
LinkedHashMap→LRU Cache, Recent Searches
ConcurrentHashMap→Session Store, In-Memory Cache
PriorityQueue→Task Scheduler, Job Queue, CPU Scheduling
13. Best Practices, Common Programs & Differences
Real Project Best Practices
✓Code to interfaces — List<Employee> list = new ArrayList<>();
✓Prefer ArrayList by default
✓Use LinkedList only for frequent insert/delete
✓Avoid Vector / Hashtable in new projects
✓Prefer ArrayDeque instead of Stack
✓Use HashMap for general key-value storage
✓Use LinkedHashMap if iteration order matters
✓Use TreeMap only when sorted keys are required
✓Prefer ConcurrentHashMap for multi-threaded access
✓Always override equals() and hashCode() together
✓Use immutable keys in HashMap, never modify after insert
✓Use Iterator.remove(), not direct removal during iteration
✓Choose initial capacity when expected size is known
✓Don't depend on HashMap iteration order
✓Don't expose mutable collections directly
✓Use Collections.unmodifiableList() or List.of() for read-only data
✓Prefer Stream API for readable transformations
Common Interview Programs
Remove Duplicates · Count Frequency · Merge Two Lists
Sort Employee by Salary/Name · Find Highest/2nd Highest Salary
Find Duplicate Elements · Common Elements · Group Objects
Convert List↔Set · Sort Map by Key/Value
Reverse/Shuffle List · Top N Elements
Word Frequency · Character Frequency
Top Interview Differences
CollectionvsCollections
CollectionsvsArrays
ListvsSet
SetvsMap
ArrayListvsLinkedList
ArrayListvsVector
VectorvsStack
HashSetvsTreeSet
HashSetvsLinkedHashSet
HashMapvsHashtable
HashMapvsConcurrentHashMap
HashMapvsLinkedHashMap
HashMapvsTreeMap
IteratorvsListIterator
ComparablevsComparator
Fail FastvsFail Safe
Common Interview "Why" Questions
Why is ArrayList faster for reads than LinkedList?
ArrayList is array-based → O(1) random access via index. LinkedList must traverse nodes → O(n).
Why does HashSet use HashMap internally?
HashSet stores elements as HashMap keys, using a shared dummy constant object as the value — reusing HashMap's hashing logic for O(1) uniqueness checks.
Why was the Red-Black Tree introduced in Java 8 HashMap?
To improve the worst-case lookup time in a heavily collided bucket from O(n) to O(log n), when a bucket has more than 8 nodes and table capacity ≥ 64.
Why is ConcurrentHashMap better than Hashtable?
Hashtable locks the entire map for every operation. ConcurrentHashMap uses fine-grained (bucket/node) locking, allowing much higher concurrency.
Why must you override hashCode() and equals() together?
HashMap/HashSet first use hashCode() to locate the bucket, then equals() to confirm the exact key. Overriding only one breaks lookups — equal objects must produce the same hashCode().
14. 50 One-Liner Revision
›Collection → Group of Objects
›Collections → Utility Class
›List → Ordered Collection
›Set → Unique Elements
›Queue → FIFO
›Deque → Double Ended Queue
›Map → Key Value Pair
›ArrayList → Dynamic Array
›LinkedList → Doubly Linked List
›Vector → Thread Safe List (Legacy)
›Stack → LIFO
›HashSet → Fastest Set
›LinkedHashSet → Ordered Set
›TreeSet → Sorted Set
›PriorityQueue → Heap Based Queue
›ArrayDeque → Best Queue/Stack
›HashMap → Fast Key Lookup
›LinkedHashMap → Ordered Map
›TreeMap → Sorted Map
›Hashtable → Legacy Thread Safe Map
›ConcurrentHashMap → Concurrent Map
›Hashing → Fast Lookup Technique
›hashCode() → Bucket Calculation
›equals() → Logical Equality
›Collision → Same Bucket
›Load Factor → Resize Threshold (0.75)
›Capacity → Bucket Count (default 16)
›Rehashing → Resize HashMap
›Treeification → List To Tree (>8 nodes)
›Untreeification → Tree To List (<6 nodes)
›Iterator → Forward Traversal
›ListIterator → Bidirectional Traversal
›Fail Fast → Throws ConcurrentModificationException
›Fail Safe → Iterates Over Copy
›Comparable → Natural Sorting
›Comparator → Custom Sorting
›Collections.sort() → Sort Collection
›binarySearch() → Fast Search (sorted list)
›shuffle() → Random Order
›reverse() → Reverse List
›frequency() → Count Occurrence
›min() / max() → Smallest / Largest Element
›WeakHashMap → GC-Friendly Keys
›IdentityHashMap → Uses == not equals()
›BlockingQueue → Multithreaded Queue
›LRU Cache → LinkedHashMap use case
›Red-Black Tree → Balances TreeMap/TreeSet/Bucket
›Arrays → Utility Class for raw Arrays
›List.of() → Immutable List (Java 9+)
15. 6-7 Yrs Interview Expectations & Revision Flow
Interviewers Expect You To Explain
✓ Collection Hierarchy ✓ Internal Working of HashMap
✓ Hashing & Collision Handling ✓ Treeification (Java 8+)
✓ Performance Trade-offs ✓ Choosing the Right Collection
✓ Comparable vs Comparator ✓ Fail Fast vs Fail Safe
✓ Thread-Safe Collections ✓ Real Project Collection Selection
15-Minute Collections Revision Flow
Collection Framework → Collection vs Map
↓
List (ArrayList / LinkedList)
↓
Set (HashSet / TreeSet)
↓
Queue (ArrayDeque / PriorityQueue)
↓
Map (HashMap / TreeMap / ConcurrentHashMap)
↓
Hashing → HashMap Internals
↓
Iterator → Comparable/Comparator → Best Practices