Java Collections Framework - DSA Interview Quick

Reference
Table of Contents
1. Collection Hierarchy Overview
2. List Interface
3. Queue Interface
4. Set Interface
5. Map Interface
6. Collections Utility Class
7. Comparator vs Comparable

Collection Hierarchy Overview

Collection (Interface)
├── List (Interface)
│ ├── ArrayList
│ ├── LinkedList
│ └── Vector (Stack extends this)
├── Queue (Interface)
│ ├── LinkedList
│ ├── PriorityQueue
│ └── Deque (Interface)
│ ├── ArrayDeque
│ └── LinkedList
└── Set (Interface)
├── HashSet
├── LinkedHashSet
└── SortedSet (Interface)
└── TreeSet

Map (Interface) - separate hierarchy

├── HashMap
├── LinkedHashMap
└── SortedMap (Interface)
└── TreeMap
List Interface
ArrayList

What: Dynamic array, resizable array implementation.

When to use:

Fast random access (O(1))

Frequent reads, less frequent insertions/deletions
When you need index-based access

How to use:

java
 // Creation
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> listWithCapacity = new ArrayList<>(100);
ArrayList<Integer> listFromCollection = new ArrayList<>([Link](1, 2, 3));

// Common operations
[Link](10); // Add at end - O(1) amortized
[Link](0, 5); // Add at index - O(n)
[Link](0); // Get element - O(1)
[Link](0, 15); // Update element - O(1)
[Link](0); // Remove by index - O(n)
[Link]([Link](10)); // Remove by value - O(n)
[Link](); // Get size
[Link](); // Check if empty
[Link](10); // Check if contains - O(n)
[Link](); // Remove all elements

// Iteration
for (int i = 0; i < [Link](); i++) {
[Link]([Link](i));
}

for (Integer num : list) {

[Link](num);
}

[Link](num -> [Link](num));

Iterator<Integer> it = [Link]();
while ([Link]()) {
[Link]([Link]());
}

Time Complexity:

Access: O(1)
Search: O(n)
Insertion: O(n) - O(1) at end
Deletion: O(n)

LinkedList
What: Doubly linked list implementation.

When to use:
 Frequent insertions/deletions at beginning or middle
When you need a queue or deque
Don't need random access

How to use:

java

// Creation
LinkedList<Integer> list = new LinkedList<>();

// List operations
[Link](10); // Add at end
[Link](5); // Add at beginning
[Link](15); // Add at end
[Link](0); // Get element - O(n)
[Link](); // Get first element
[Link](); // Get last element
[Link](); // Remove first
[Link](); // Remove last

// Queue operations
[Link](20); // Add to end (queue)
[Link](); // Remove from front
[Link](); // View front element

// Deque operations
[Link](1); // Add to front
[Link](30); // Add to end
[Link](); // Remove from front
[Link](); // Remove from end

// Iteration (same as ArrayList)

for (Integer num : list) {
[Link](num);
}

Time Complexity:

Access: O(n)
Search: O(n)
Insertion: O(1) at ends, O(n) in middle
Deletion: O(1) at ends, O(n) in middle
Stack

What: LIFO (Last In First Out) data structure, extends Vector.

When to use:

Expression evaluation
Backtracking problems
DFS traversal

How to use:

java

// Creation
Stack<Integer> stack = new Stack<>();

// Operations
[Link](10); // Push element
[Link](); // Pop and return top element
[Link](); // View top element without removing
[Link](); // Check if empty
[Link](10); // Returns 1-based position from top

// Iteration
for (Integer num : stack) {
[Link](num);
}

// Note: Prefer using Deque instead of Stack

Deque<Integer> stack2 = new ArrayDeque<>();
[Link](10);
[Link]();
[Link]();

Time Complexity: All operations O(1)

Queue Interface
PriorityQueue
What: Min-heap by default, elements ordered by natural ordering or comparator.

When to use:

When you need min/max element quickly

Dijkstra's algorithm, Huffman coding
 K-th largest/smallest problems

How to use:

java

// Creation
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
PriorityQueue<Integer> withCapacity = new PriorityQueue<>(100);

// With custom comparator

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // Max heap

// Operations
[Link](10); // Add element - O(log n)
[Link](20); // Add element - O(log n)
[Link](); // Remove and return min - O(log n)
[Link](); // View min without removing - O(1)
[Link](10); // Remove specific element - O(n)
[Link]();
[Link]();

// Iteration (not in sorted order)

for (Integer num : pq) {
[Link](num);
}

// To get sorted output

while (![Link]()) {
[Link]([Link]());
}

Time Complexity:

Insert: O(log n)
Remove min/max: O(log n)
Peek: O(1)

ArrayDeque
What: Resizable array implementation of Deque interface.

When to use:

Faster than LinkedList for stack and queue operations

 No capacity restrictions
Not thread-safe

How to use:

java

// Creation
ArrayDeque<Integer> deque = new ArrayDeque<>();

// Queue operations
[Link](10); // Add to end
[Link](); // Remove from front
[Link](); // View front

// Deque operations
[Link](5); // Add to front
[Link](15); // Add to end
[Link](); // Remove from front
[Link](); // Remove from end
[Link](); // View front
[Link](); // View end

// Stack operations (preferred over Stack class)

[Link](20); // Push to front
[Link](); // Pop from front

// Iteration
for (Integer num : deque) {
[Link](num);
}

Time Complexity: All operations O(1)

Set Interface
HashSet

What: Hash table implementation, no duplicates, no order.

When to use:

Fast lookup, insertion, deletion

When you don't care about order
Removing duplicates
How to use:

java

// Creation
HashSet<Integer> set = new HashSet<>();
HashSet<Integer> setWithCapacity = new HashSet<>(100);
HashSet<Integer> setFromCollection = new HashSet<>([Link](1, 2, 3));

// Operations
[Link](10); // Add element - O(1)
[Link](10); // Remove element - O(1)
[Link](10); // Check if contains - O(1)
[Link]();
[Link]();
[Link]();

// Iteration
for (Integer num : set) {
[Link](num);
}

Iterator<Integer> it = [Link]();
while ([Link]()) {
[Link]([Link]());
}

Time Complexity:

Add: O(1)
Remove: O(1)
Contains: O(1)

LinkedHashSet
What: HashSet with insertion order maintained.

When to use:

Need HashSet benefits + insertion order

Slightly slower than HashSet

How to use:

java
 LinkedHashSet<Integer> set = new LinkedHashSet<>();
// All operations same as HashSet
// Maintains insertion order during iteration

TreeSet
What: Red-black tree implementation, sorted order, implements NavigableSet.

When to use:

Need sorted elements

Range queries (floor, ceiling, higher, lower)
When you need first/last elements

How to use:

java
 // Creation
TreeSet<Integer> set = new TreeSet<>();
TreeSet<Integer> reverseSet = new TreeSet<>([Link]());
TreeSet<Integer> withComparator = new TreeSet<>((a, b) -> b - a);

// Operations
[Link](10); // Add element - O(log n)
[Link](10); // Remove element - O(log n)
[Link](10); // Check if contains - O(log n)
[Link](); // Get smallest element
[Link](); // Get largest element

// NavigableSet operations
[Link](15); // Largest element <= 15
[Link](15); // Smallest element >= 15
[Link](15); // Largest element < 15
[Link](15); // Smallest element > 15
[Link](); // Remove and return smallest
[Link](); // Remove and return largest

// Range views
[Link](10); // Elements < 10
[Link](10); // Elements >= 10
[Link](5, 15); // Elements >= 5 and < 15

// Iteration (sorted order)

for (Integer num : set) {
[Link](num);
}

// Descending iteration
Iterator<Integer> descIt = [Link]();
while ([Link]()) {
[Link]([Link]());
}

Time Complexity:

Add: O(log n)
Remove: O(log n)
Contains: O(log n)
Map Interface
HashMap

What: Hash table implementation, key-value pairs, no order.

When to use:

Fast lookup by key

Constant time operations
Most common map implementation

How to use:

java
 // Creation
HashMap<String, Integer> map = new HashMap<>();
HashMap<String, Integer> mapWithCapacity = new HashMap<>(100);

// Operations
[Link]("key1", 10); // Add/update - O(1)
[Link]("key1"); // Get value - O(1)
[Link]("key2", 0); // Get with default value
[Link]("key1"); // Remove - O(1)
[Link]("key1"); // Check key exists - O(1)
[Link](10); // Check value exists - O(n)
[Link]();
[Link]();
[Link]();

// Update operations
[Link]("key2", 20); // Add if key doesn't exist
[Link]("key1", 15); // Replace value if key exists
[Link]("key3", k -> 30); // Compute if absent
[Link]("key1", 5, Integer::sum); // Merge values

// Iteration
// 1. Using entrySet (most efficient)
for ([Link]<String, Integer> entry : [Link]()) {
[Link]([Link]() + " : " + [Link]());
}

// 2. Using keySet
for (String key : [Link]()) {
[Link](key + " : " + [Link](key));
}

// 3. Using values
for (Integer value : [Link]()) {
[Link](value);
}

// 4. Using forEach
[Link]((key, value) -> [Link](key + " : " + value));

Time Complexity:

Put: O(1)
Get: O(1)
Remove: O(1)
LinkedHashMap
What: HashMap with insertion order (or access order) maintained.

When to use:

Need HashMap benefits + predictable iteration order

LRU cache implementation (with access order)

How to use:

java

// Creation
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
// Access order (true = access order, false = insertion order)
LinkedHashMap<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true);

// All operations same as HashMap

// Maintains insertion/access order during iteration

TreeMap

What: Red-black tree implementation, sorted by keys, implements NavigableMap.

When to use:

Need sorted keys

Range queries on keys
First/last key operations

How to use:

java
 // Creation
TreeMap<Integer, String> map = new TreeMap<>();
TreeMap<Integer, String> reverseMap = new TreeMap<>([Link]());

// Operations (same as HashMap)

[Link](1, "one"); // O(log n)
[Link](1); // O(log n)
[Link](1); // O(log n)

// NavigableMap operations
[Link](); // Get smallest key
[Link](); // Get largest key
[Link](5); // Largest key <= 5
[Link](5); // Smallest key >= 5
[Link](5); // Largest key < 5
[Link](5); // Smallest key > 5
[Link](); // Remove and return smallest
[Link](); // Remove and return largest

// Range views
[Link](10); // Keys < 10
[Link](10); // Keys >= 10
[Link](5, 15); // Keys >= 5 and < 15

// Iteration (sorted by keys)

for ([Link]<Integer, String> entry : [Link]()) {
[Link]([Link]() + " : " + [Link]());
}

Time Complexity:

Put: O(log n)
Get: O(log n)
Remove: O(log n)

Collections Utility Class

The Collections class provides static methods for working with collections.

Sorting

java
 List<Integer> list = new ArrayList<>([Link](5, 2, 8, 1, 9));

// Natural order sorting

[Link](list); // [1, 2, 5, 8, 9]

// Reverse order
[Link](list, [Link]()); // [9, 8, 5, 2, 1]

// Custom comparator
[Link](list, (a, b) -> b - a);

// Reverse a list
[Link](list);

// Shuffle
[Link](list);

Searching

java

List<Integer> list = [Link](1, 2, 5, 8, 9);

// Binary search (list must be sorted)

int index = [Link](list, 5); // Returns index or negative if not found

Finding Min/Max

java

List<Integer> list = [Link](5, 2, 8, 1, 9);

int min = [Link](list); // 1

int max = [Link](list); // 9

// With comparator
int maxAbs = [Link](list, (a, b) -> [Link](a) - [Link](b));
Frequency and Fill

java

List<Integer> list = [Link](1, 2, 2, 3, 2);

int freq = [Link](list, 2); // 3

List<Integer> list2 = new ArrayList<>([Link](1, 2, 3));

[Link](list2, 0); // [0, 0, 0]

Other Utilities

java

// Swap elements
[Link](list, 0, 1);

// Rotate list
[Link](list, 2); // Rotate right by 2 positions

// Create immutable collections

List<Integer> immutableList = [Link](list);
Set<Integer> immutableSet = [Link](set);
Map<String, Integer> immutableMap = [Link](map);

// Empty collections
List<Integer> emptyList = [Link]();
Set<Integer> emptySet = [Link]();
Map<String, Integer> emptyMap = [Link]();

// Singleton collections
List<Integer> singletonList = [Link](42);
Set<Integer> singletonSet = [Link](42);

Comparator vs Comparable
Comparable Interface

What: Defines natural ordering for a class. Implemented by the class itself.
When to use:

Single default sorting sequence

You own the class and can modify it

How to use:

java

class Student implements Comparable<Student> {

String name;
int age;

public Student(String name, int age) {

[Link] = name;
[Link] = age;
}

@Override
public int compareTo(Student other) {
// Natural ordering by age
return [Link] - [Link];
// For descending: return [Link] - [Link];
}

@Override
public String toString() {
return name + "(" + age + ")";
}
}

// Usage
List<Student> students = new ArrayList<>();
[Link](new Student("Alice", 22));
[Link](new Student("Bob", 20));
[Link](new Student("Charlie", 21));

[Link](students); // Sorts by age (natural ordering)

[Link](students); // [Bob(20), Charlie(21), Alice(22)]

// TreeSet will use natural ordering

TreeSet<Student> set = new TreeSet<>();
[Link](students); // Automatically sorted by age
Comparator Interface

What: Defines custom ordering. Separate class or lambda expression.

When to use:

Multiple sorting sequences

Cannot modify the class
Different sorting for different contexts

How to use:

java
class Student {
String name;
int age;
double gpa;

public Student(String name, int age, double gpa) {

[Link] = name;
[Link] = age;
[Link] = gpa;
}

@Override
public String toString() {
return name + "(" + age + ", " + gpa + ")";
}
}

// Method 1: Anonymous class

Comparator<Student> nameComparator = new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
return [Link]([Link]);
}
};

// Method 2: Lambda expression (preferred)

Comparator<Student> ageComparator = (s1, s2) -> [Link] - [Link];
Comparator<Student> gpaComparator = (s1, s2) -> [Link]([Link], [Link]);

// Method 3: Method reference with [Link]

Comparator<Student> nameComp = [Link](s -> [Link]);
Comparator<Student> ageComp = [Link](s -> [Link]);
Comparator<Student> gpaComp = [Link](s -> [Link]);

// Usage
List<Student> students = new ArrayList<>();
[Link](new Student("Alice", 22, 3.8));
[Link](new Student("Bob", 20, 3.5));
[Link](new Student("Charlie", 21, 3.9));

// Sort by name
[Link](students, nameComparator);
// Or: [Link](nameComparator);
 // Sort by age
[Link](students, ageComparator);

// Reverse order
[Link](students, [Link]());

// Multiple criteria - sort by GPA, then by name

Comparator<Student> multiComp = Comparator
.comparingDouble((Student s) -> [Link])
.reversed()
.thenComparing(s -> [Link]);
[Link](students, multiComp);

// Using with TreeSet/TreeMap

TreeSet<Student> sortedByName = new TreeSet<>(nameComparator);
[Link](students);

TreeMap<Student, String> map = new TreeMap<>(ageComparator);

Key Differences

Aspect Comparable Comparator

Package [Link] [Link]
Method compareTo(Object o) compare(Object o1, Object o2)
Usage Natural ordering Custom ordering
Implementation Modify the class Separate class/lambda
Sorting sequences Single Multiple
Example String, Integer, Date Custom sorting logic

Common Pitfalls

java
 // Wrong: Integer overflow for large values
Comparator<Integer> bad = (a, b) -> a - b; // Can overflow

// Right: Use [Link]

Comparator<Integer> good = (a, b) -> [Link](a, b);
// Or: [Link](x -> x)

// Wrong: Inconsistent with equals (violates contract)

// compareTo returns 0 but equals returns false

// Right: Ensure compareTo consistent with equals

@Override
public int compareTo(Student other) {
int result = [Link]([Link]);
if (result == 0) {
result = [Link]([Link], [Link]);
}
return result;
}

Quick Reference: Time Complexities

Operation ArrayList LinkedList HashSet TreeSet HashMap TreeMap
Add O(1)* O(1) O(1) O(log n) O(1) O(log n)
Remove O(n) O(1)** O(1) O(log n) O(1) O(log n)
Get O(1) O(n) N/A O(log n) O(1) O(log n)
Contains O(n) O(n) O(1) O(log n) O(1) O(log n)

*Amortized, **At ends

Common Interview Patterns

Pattern 1: Frequency Counter (HashMap)

java

Map<Character, Integer> freq = new HashMap<>();

for (char c : [Link]()) {
[Link](c, [Link](c, 0) + 1);
}
Pattern 2: Two Pointers with Set

java

Set<Integer> seen = new HashSet<>();

int left = 0;
for (int right = 0; right < [Link]; right++) {
while ([Link](arr[right])) {
[Link](arr[left++]);
}
[Link](arr[right]);
}

Pattern 3: Priority Queue for K-th Element

java

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

for (int num : nums) {
[Link](num);
if ([Link]() > k) {
[Link]();
}
}
int kthLargest = [Link]();

Pattern 4: TreeMap for Range Queries

java

TreeMap<Integer, Integer> map = new TreeMap<>();

// Get floor and ceiling
Integer floor = [Link](target);
Integer ceiling = [Link](target);

Best Practices for Interviews

1. Choose the right data structure:
Need fast lookup? → HashMap/HashSet
 Need sorted data? → TreeMap/TreeSet
Need order? → LinkedHashMap/LinkedHashSet
Need both ends access? → ArrayDeque
Need priority? → PriorityQueue
2. Initialize with capacity if known to avoid resizing
3. Use foreach loop when you don't need index
4. Prefer Deque over Stack for stack operations
5. Use computeIfAbsent for nested maps
6. Remember autoboxing cost for primitive wrappers
7. Check for null before operations if input can be null

Good luck with your interview! 🚀