Java Collections¶

Collections Hierarchy¶

Java Collections Hierarchy

Java Map Hierarchy

List Implementations¶

ArrayList¶

// Dynamic array - most commonly used
List<String> list = new ArrayList<>();
list.add("A");           // O(1) amortized
list.add(0, "B");        // O(n) - shifts elements
list.get(0);             // O(1) - random access
list.set(0, "C");        // O(1)
list.remove(0);          // O(n) - shifts elements
list.remove("A");        // O(n) - search + shift
list.contains("A");      // O(n)
list.size();             // O(1)

// Initialize with capacity to avoid resizing
List<String> sized = new ArrayList<>(1000);

// Create from existing collection
List<String> copy = new ArrayList<>(existingList);

// Immutable list (Java 9+)
List<String> immutable = List.of("A", "B", "C");

Operation	Time Complexity
add(E)	O(1) amortized
add(index, E)	O(n)
get(index)	O(1)
set(index, E)	O(1)
remove(index)	O(n)
remove(Object)	O(n)
contains(Object)	O(n)
size()	O(1)

Use When: Random access needed, mostly additions at end, infrequent insertions/deletions in middle.

LinkedList¶

// Doubly-linked list - also implements Deque
LinkedList<String> list = new LinkedList<>();
list.add("A");           // O(1)
list.addFirst("B");      // O(1)
list.addLast("C");       // O(1)
list.get(0);             // O(n) - must traverse
list.getFirst();         // O(1)
list.getLast();          // O(1)
list.remove(0);          // O(n) - traverse to index
list.removeFirst();      // O(1)
list.removeLast();       // O(1)

// As a Queue
list.offer("D");         // O(1) - add to end
list.poll();             // O(1) - remove from front
list.peek();             // O(1) - view front

// As a Stack
list.push("E");          // O(1) - add to front
list.pop();              // O(1) - remove from front

Operation	Time Complexity
add(E)	O(1)
add(index, E)	O(n)
get(index)	O(n)
getFirst/getLast	O(1)
removeFirst/removeLast	O(1)
remove(index)	O(n)
contains(Object)	O(n)

Use When: Frequent insertions/deletions at both ends, implementing queue/deque, iterator-based removal.

ArrayList vs LinkedList¶

Aspect	ArrayList	LinkedList
Memory	Compact, contiguous	Higher (node overhead)
Random Access	O(1)	O(n)
Insert at End	O(1) amortized	O(1)
Insert at Start	O(n)	O(1)
Insert in Middle	O(n)	O(n)*
Cache Performance	Better (locality)	Worse (scattered)

*LinkedList: O(1) for insert itself, but O(n) to find position

Rule of Thumb: Use ArrayList unless you need constant-time insertions at both ends.

Set Implementations¶

HashSet¶

// Hash table - fastest for add/remove/contains
Set<String> set = new HashSet<>();
set.add("A");            // O(1) average
set.remove("A");         // O(1) average
set.contains("A");       // O(1) average
set.size();              // O(1)

// No duplicates
set.add("A");
set.add("A");            // Returns false, size still 1

// No ordering guaranteed
for (String s : set) {
    // Order may vary between runs
}

// Initialize with capacity and load factor
Set<String> optimized = new HashSet<>(1000, 0.75f);

Operation	Average	Worst Case
add(E)	O(1)	O(n)
remove(Object)	O(1)	O(n)
contains(Object)	O(1)	O(n)

Use When: Fast lookups needed, order doesn't matter, no duplicates.

LinkedHashSet¶

// Hash table + linked list - maintains insertion order
Set<String> set = new LinkedHashSet<>();
set.add("C");
set.add("A");
set.add("B");

for (String s : set) {
    // Always: C, A, B (insertion order)
}

Operation	Time Complexity
add(E)	O(1)
remove(Object)	O(1)
contains(Object)	O(1)
Iteration	O(n) in insertion order

Use When: Need HashSet performance + predictable iteration order.

TreeSet¶

// Red-Black tree - sorted order
Set<String> set = new TreeSet<>();
set.add("C");
set.add("A");
set.add("B");

for (String s : set) {
    // Always: A, B, C (natural order)
}

// NavigableSet operations
TreeSet<Integer> nums = new TreeSet<>();
nums.addAll(List.of(1, 3, 5, 7, 9));

nums.first();            // 1
nums.last();             // 9
nums.lower(5);           // 3 (strictly less)
nums.floor(5);           // 5 (less or equal)
nums.higher(5);          // 7 (strictly greater)
nums.ceiling(5);         // 5 (greater or equal)
nums.headSet(5);         // [1, 3] (less than 5)
nums.tailSet(5);         // [5, 7, 9] (>= 5)
nums.subSet(3, 7);       // [3, 5] (>= 3, < 7)

// Custom comparator
Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));

Operation	Time Complexity
add(E)	O(log n)
remove(Object)	O(log n)
contains(Object)	O(log n)
first/last	O(log n)

Use When: Need sorted order, range queries, finding nearest elements.

Set Comparison¶

Feature	HashSet	LinkedHashSet	TreeSet
Order	None	Insertion	Sorted
add/remove/contains	O(1)	O(1)	O(log n)
Null allowed	Yes (1)	Yes (1)	No*
Memory	Lowest	Medium	Highest

*TreeSet allows null only if Comparator handles it

Queue Implementations¶

PriorityQueue¶

// Min-heap by default
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);        // O(log n)
minHeap.offer(2);
minHeap.offer(8);
minHeap.peek();          // 2 (smallest) - O(1)
minHeap.poll();          // 2 (removes smallest) - O(log n)

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
maxHeap.peek();          // 8 (largest)

// Custom objects
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

Operation	Time Complexity
offer(E)	O(log n)
poll()	O(log n)
peek()	O(1)
remove(Object)	O(n)
contains(Object)	O(n)

Use When: Processing elements by priority, finding min/max, top K problems.

ArrayDeque¶

// Resizable array deque - faster than LinkedList
Deque<String> deque = new ArrayDeque<>();

// As a Stack (LIFO)
deque.push("A");         // O(1)
deque.push("B");
deque.pop();             // "B" - O(1)
deque.peek();            // "A" - O(1)

// As a Queue (FIFO)
deque.offer("C");        // O(1) - add to end
deque.poll();            // "A" - O(1) - remove from front

// Double-ended operations
deque.addFirst("X");     // O(1)
deque.addLast("Y");      // O(1)
deque.removeFirst();     // O(1)
deque.removeLast();      // O(1)

Operation	Time Complexity
push/pop	O(1)
offer/poll	O(1)
addFirst/addLast	O(1)
removeFirst/removeLast	O(1)
get(index)	Not supported

Use When: Stack or queue needed, better performance than Stack/LinkedList.

Common Operations¶

Bulk Operations¶

List<String> list1 = new ArrayList<>(List.of("A", "B", "C"));
List<String> list2 = new ArrayList<>(List.of("B", "C", "D"));

// Union
Set<String> union = new HashSet<>(list1);
union.addAll(list2);  // [A, B, C, D]

// Intersection
Set<String> intersection = new HashSet<>(list1);
intersection.retainAll(list2);  // [B, C]

// Difference
Set<String> difference = new HashSet<>(list1);
difference.removeAll(list2);  // [A]

// Check containment
list1.containsAll(list2);  // false

Sorting¶

List<Integer> numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5));

// Natural order
Collections.sort(numbers);  // [1, 1, 3, 4, 5]
numbers.sort(null);         // Same as above

// Custom comparator
numbers.sort(Comparator.reverseOrder());  // [5, 4, 3, 1, 1]

// Complex objects
List<Person> people = ...;
people.sort(Comparator.comparing(Person::getLastName)
    .thenComparing(Person::getFirstName)
    .thenComparingInt(Person::getAge));

Searching¶

List<Integer> sorted = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9);

// Binary search (list must be sorted)
int index = Collections.binarySearch(sorted, 5);  // Returns index or (-(insertion point) - 1)

// Min/Max
int min = Collections.min(sorted);
int max = Collections.max(sorted);

// Custom comparator
Person youngest = Collections.min(people, Comparator.comparingInt(Person::getAge));

Shuffling and Rotating¶

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));

Collections.shuffle(list);           // Random order
Collections.reverse(list);           // Reverse order
Collections.rotate(list, 2);         // [4, 5, 1, 2, 3]
Collections.swap(list, 0, 4);        // Swap positions
Collections.fill(list, 0);           // All zeros

Immutable Collections¶

// Java 9+ factory methods (truly immutable)
List<String> list = List.of("A", "B", "C");
Set<String> set = Set.of("A", "B", "C");
Map<String, Integer> map = Map.of("A", 1, "B", 2);

// These throw UnsupportedOperationException on modification
// list.add("D");  // Throws!

// Unmodifiable wrappers (view, can be modified through original)
List<String> original = new ArrayList<>(List.of("A", "B"));
List<String> unmodifiable = Collections.unmodifiableList(original);
original.add("C");  // Works, unmodifiable view now shows C

// Copy to immutable (Java 10+)
List<String> immutableCopy = List.copyOf(original);

Thread-Safe Collections¶

// Legacy synchronized collections
Vector<String> vector = new Vector<>();  // Don't use
Hashtable<String, Integer> hashtable = new Hashtable<>();  // Don't use

// Synchronized wrappers
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// Iteration still needs external sync
synchronized (syncList) {
    for (String s : syncList) {
        // Safe iteration
    }
}

// Concurrent collections (preferred)
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
CopyOnWriteArraySet<String> cowSet = new CopyOnWriteArraySet<>();
ConcurrentLinkedQueue<String> concurrentQueue = new ConcurrentLinkedQueue<>();
BlockingQueue<String> blockingQueue = new LinkedBlockingQueue<>();

Big O Summary¶

Collection	Add	Remove	Get	Contains	Notes
ArrayList	O(1)*	O(n)	O(1)	O(n)	*amortized, end
LinkedList	O(1)	O(1)**	O(n)	O(n)	**at known position
HashSet	O(1)	O(1)	-	O(1)	Average case
TreeSet	O(log n)	O(log n)	-	O(log n)	Sorted
HashMap	O(1)	O(1)	O(1)	O(1)	Average case
TreeMap	O(log n)	O(log n)	O(log n)	O(log n)	Sorted
PriorityQueue	O(log n)	O(log n)	O(1)***	O(n)	***peek only
ArrayDeque	O(1)	O(1)	-	O(n)	Ends only

When to Use What¶

Need	Use
Indexed access, variable size	ArrayList
Frequent add/remove at ends	ArrayDeque
Queue (FIFO)	ArrayDeque or LinkedList
Stack (LIFO)	ArrayDeque
Priority ordering	PriorityQueue
Unique elements, fast lookup	HashSet
Unique elements, sorted	TreeSet
Unique elements, insertion order	LinkedHashSet
Key-value pairs, fast lookup	HashMap
Key-value pairs, sorted	TreeMap
Key-value pairs, insertion order	LinkedHashMap
Thread-safe map	ConcurrentHashMap
Thread-safe list with many reads	CopyOnWriteArrayList

Common Interview Questions¶

ArrayList vs LinkedList?
ArrayList: Better random access, cache-friendly, less memory
LinkedList: Better insert/remove at ends, implements Deque
HashSet vs TreeSet?
HashSet: O(1) operations, no ordering
TreeSet: O(log n) operations, sorted, range queries
How does ArrayList resize?
When full, creates new array 1.5x size, copies elements
Why is HashMap iteration order unpredictable?
Elements stored by hash bucket, bucket order varies with size and hash distribution
What's the initial capacity and load factor of HashMap?
Default capacity: 16, load factor: 0.75
Resizes when size > capacity × load factor