Java Collections Cheat Sheet

1. Collection Hierarchy

Collection
│
├── List
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector
│
├── Set
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
│
└── Queue
    ├── PriorityQueue
    └── Deque
        ├── ArrayDeque
        └── LinkedList

Map (separate hierarchy)
├── HashMap
├── LinkedHashMap
├── TreeMap
└── Hashtable

---

2. List

ArrayList

Features

• Dynamic array
• Fast random access
• Slower insert/delete in middle
• Allows duplicates
• Maintains insertion order

Time Complexity

Operation	Complexity
get(index)	O(1)
add()	O(1) amortized
add(index)	O(n)
remove(index)	O(n)
contains()	O(n)

Syntax

List<Integer> list = new ArrayList<>();

list.add(10);
list.add(20);
list.add(30);

System.out.println(list.get(1));

list.remove(1);

System.out.println(list.contains(10));

---

LinkedList

Features

• Doubly linked list
• Fast insertion/deletion
• Slow random access
• Can work as List + Queue + Deque

Time Complexity

Operation	Complexity
get(index)	O(n)
addFirst()	O(1)
addLast()	O(1)
removeFirst()	O(1)
removeLast()	O(1)

Syntax

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

list.addFirst(10);
list.addLast(20);

System.out.println(list.getFirst());
System.out.println(list.getLast());

list.removeFirst();
list.removeLast();

---

3. Set

HashSet

Features

• Stores unique elements
• No insertion order guarantee
• Backed by HashMap

Time Complexity

Operation	Complexity
add	O(1)
remove	O(1)
contains	O(1)

Syntax

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

set.add(10);
set.add(20);
set.add(10);

System.out.println(set);

---

LinkedHashSet

Features

• Unique elements
• Maintains insertion order

Syntax

Set<Integer> set = new LinkedHashSet<>();

---

TreeSet

Features

• Sorted set
• Uses Red-Black Tree
• Unique elements

Time Complexity

Operation	Complexity
add	O(log n)
remove	O(log n)
contains	O(log n)

Syntax

TreeSet<Integer> set = new TreeSet<>();

set.add(30);
set.add(10);
set.add(20);

System.out.println(set);

Useful Methods

set.first();
set.last();
set.ceiling(25);
set.floor(25);
set.higher(20);
set.lower(20);

---

4. Map

HashMap

Features

• Key-value pairs
• Keys are unique
• No ordering guarantee
• Allows one null key

Time Complexity

Operation	Complexity
put	O(1)
get	O(1)
remove	O(1)
containsKey	O(1)

Syntax

Map<Integer, String> map = new HashMap<>();

map.put(1, "Apple");
map.put(2, "Banana");

System.out.println(map.get(1));

map.remove(2);

System.out.println(map.containsKey(1));

Iteration

for(Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

---

LinkedHashMap

Features

• Maintains insertion order
• Used in LRU Cache

Syntax

Map<Integer, String> map = new LinkedHashMap<>();

Access Order LinkedHashMap

LinkedHashMap<Integer, Integer> map =
    new LinkedHashMap<>(16, 0.75f, true);

---

TreeMap

Features

• Sorted by keys
• Uses Red-Black Tree

Time Complexity

Operation	Complexity
put	O(log n)
get	O(log n)
remove	O(log n)

Syntax

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

Useful Methods

map.firstKey();
map.lastKey();
map.ceilingKey(10);
map.floorKey(10);
map.higherKey(10);
map.lowerKey(10);

---

5. Queue

Queue Interface

Methods

Method	Meaning
offer()	insert
poll()	remove front
peek()	get front

Syntax

Queue<Integer> q = new LinkedList<>();

q.offer(10);
q.offer(20);

System.out.println(q.peek());

q.poll();

---

6. PriorityQueue (Heap)

Min Heap (Default)

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

Top Element

• Smallest element

---

Max Heap

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

OR

PriorityQueue<Integer> pq =
    new PriorityQueue<>(Collections.reverseOrder());

Top Element

• Largest element

---

Heap Operations

Method	Meaning
add() / offer()	insert
poll()	remove top
peek()	get top

---

7. Deque

ArrayDeque

Features

• Faster than Stack
• Faster than LinkedList for queue operations
• Double-ended queue

Syntax

Deque<Integer> dq = new ArrayDeque<>();

// Front

dq.addFirst(10);
dq.removeFirst();
dq.peekFirst();

// Back

dq.addLast(20);
dq.removeLast();
dq.peekLast();

---

8. Stack

Preferred: ArrayDeque

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.push(20);

System.out.println(stack.peek());

stack.pop();

---

9. Collections Utility Methods

Sorting

Collections.sort(list);
Collections.sort(list, Collections.reverseOrder());

---

Reverse

Collections.reverse(list);

---

Max / Min

Collections.max(list);
Collections.min(list);

---

Frequency

Collections.frequency(list, 10);

---

10. Comparator

Ascending

(a, b) -> a - b

---

Descending

(a, b) -> b - a

---

Safer Comparator

Integer.compare(a, b)
Integer.compare(b, a)

---

11. Common Interview Patterns

Frequency Map

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

for(int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

---

Top K Elements

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

Use min heap of size k.

---

BFS

Queue<Integer> q = new LinkedList<>();

---

Monotonic Stack

Deque<Integer> stack = new ArrayDeque<>();

---

Sliding Window Maximum

Deque<Integer> dq = new ArrayDeque<>();

---

12. Important Differences

ArrayList vs LinkedList

Feature	ArrayList	LinkedList
Random Access	Fast	Slow
Insert/Delete Middle	Slow	Faster
Memory	Less	More

---

HashMap vs TreeMap

Feature	HashMap	TreeMap
Ordering	No	Sorted
Complexity	O(1)	O(log n)
Internal DS	Hash Table	Red-Black Tree

---

HashSet vs TreeSet

Feature	HashSet	TreeSet
Ordering	No	Sorted
Complexity	O(1)	O(log n)

---

13. Useful Java 8 Features

forEach

list.forEach(System.out::println);

---

Stream Sort

list.stream().sorted().toList();

---

Custom Object Sorting

Collections.sort(list, (a, b) -> a.age - b.age);

---

14. Common Mistakes

List remove()

list.remove(2);

Removes index 2.

To remove value:

list.remove(Integer.valueOf(2));

---

PriorityQueue is Min Heap by Default

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

Top is smallest.

---

HashMap Ordering

HashMap does NOT maintain insertion order.

Use:

LinkedHashMap

if order matters.

---

15. Most Important Interview Collections

Use Case	Collection
Frequency Count	HashMap
Unique Elements	HashSet
Sorted Data	TreeMap / TreeSet
BFS	Queue
Heap Problems	PriorityQueue
Stack Problems	ArrayDeque
LRU Cache	LinkedHashMap
Fast Random Access	ArrayList
Fast Front/Back Ops	LinkedList / ArrayDeque