Java Collections: Comprehensive Notes for Interviews, OA, and Leetcode

1. Overview of Java Collections Framework

The Java Collections Framework provides a set of classes and interfaces for storing and manipulating data efficiently. It includes:

• Interfaces: List, Set, Map, Queue, Deque

• Implementations: ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, PriorityQueue, etc.

---

2. List

What is a List?

• A List is an ordered collection that allows duplicate elements.

• Common implementations:

  • ArrayList: Resizable-array implementation.

  • LinkedList: Doubly-linked list implementation.

How to Initialize a List?

// ArrayList Initialization
List<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);

// LinkedList Initialization
List<Integer> linkedList = new LinkedList<>();
linkedList.add(3);
linkedList.add(4);

Common Functions & Methods (with complexity):

How to Use Common Methods?

arrayList.add(5);                    // add element
int x = arrayList.get(1);            // get element
arrayList.set(2, 100);               // update element
arrayList.remove(0);                 // remove by index
boolean hasVal = arrayList.contains(100); // check contains
int idx = arrayList.indexOf(100);    // index of element
arrayList.clear();                   // clear all

Time Complexity:

Space Complexity:

• ArrayList: O(n) for storage.

• LinkedList: O(n) for nodes + O(n) pointers.

Use Cases:

• Use ArrayList for fast random access.

• Use LinkedList for frequent insertions/deletions.

---

3. Set

What is a Set?

• A Set is an unordered collection that does not allow duplicate elements.

• Common implementations:

  • HashSet: Backed by a HashMap.

  • TreeSet: Sorted set backed by a balanced binary tree.

How to Initialize a Set?

// HashSet Initialization
Set<Integer> hashSet = new HashSet<>();
hashSet.add(5);
hashSet.add(6);

// TreeSet Initialization
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(7);
treeSet.add(8);

Common Functions & Methods (with complexity):

How to Use Common Methods?

hashSet.add(10);                // add element
hashSet.remove(5);              // remove element
boolean exists = hashSet.contains(6); // check contains
treeSet.first();                // first element in sorted order
treeSet.last();                 // last element in sorted order

Time Complexity:

Space Complexity:

• HashSet: O(n) for storage.

• TreeSet: O(n) for nodes.

Use Cases:

• Use HashSet for fast lookups.

• Use TreeSet for sorted sets.

---

4. Map

What is a Map?

• A Map stores key-value pairs.

• Common implementations:

  • HashMap: Unordered key-value store.

  • TreeMap: Sorted key-value store.

How to Initialize a Map?

// HashMap Initialization
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("key1", 10);
hashMap.put("key2", 20);

// TreeMap Initialization
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("key3", 30);
treeMap.put("key4", 40);

Common Functions & Methods (with complexity):

How to Use Common Methods?

hashMap.put("a", 1);                    // add entry
int value = hashMap.get("key1");        // get value
hashMap.remove("key2");                 // remove entry
boolean hasKey = hashMap.containsKey("a"); // check if key exists
for (String k : hashMap.keySet()) {     // iterate keys
    System.out.println(k + " " + hashMap.get(k));
}

Time Complexity:

Space Complexity:

• HashMap: O(n) for storage.

• TreeMap: O(n) for nodes.

Use Cases:

• Use HashMap for fast lookups.

• Use TreeMap for sorted key-value pairs.

---

5. Queue

What is a Queue?

• A Queue is a collection designed for FIFO (First-In-First-Out) order.

• Common implementations:

  • LinkedList: Implements Queue interface.

  • PriorityQueue: A queue where elements are ordered by priority.

How to Initialize a Queue?

// LinkedList Queue Initialization
Queue<Integer> linkedListQueue = new LinkedList<>();
linkedListQueue.add(50);
linkedListQueue.add(60);

// PriorityQueue Initialization
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(70);
priorityQueue.add(80);

Common Functions & Methods (with complexity):

How to Use Common Methods?

queue.add(100);
queue.offer(200);
int head = queue.poll();        // retrieves and removes head or null
queue.peek();                   // retrieves but does not remove head

Time Complexity:

Space Complexity:

• LinkedList Queue: O(n) for storage.

• PriorityQueue: O(n) for heap.

Use Cases:

• Use PriorityQueue for ordering elements based on priority.

---

6. Deque

What is a Deque?

• A Deque is a double-ended queue that allows inserting and removing elements from both ends.

• Common implementations:

  • ArrayDeque: Efficient resizable-array implementation.

How to Initialize a Deque?

// ArrayDeque Initialization
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(90);
deque.addLast(100);

Common Functions & Methods (with complexity):

How to Use Common Methods?

deque.addFirst(1);         // push to front
deque.addLast(2);          // push to end
deque.removeFirst();       // pop from front
deque.removeLast();        // pop from end

Time Complexity:

Space Complexity:

• ArrayDeque: O(n) for storage.

Use Cases:

• Use Deque for stack and queue operations in a single structure.

---

7. Stack

What is a Stack?

• A Stack is a collection designed for LIFO (Last-In-First-Out) order.

How to Initialize a Stack?

// Stack Initialization
Stack<Integer> stack = new Stack<>();
stack.push(110);
stack.push(120);
stack.pop();

Common Functions & Methods (with complexity):

How to Use Common Methods?

stack.push(100);          // add to top
int top = stack.pop();    // remove from top
int peeked = stack.peek();// view top

Time Complexity:

Space Complexity:

• Stack: O(n) for storage.

Use Cases:

• Use Stack for recursion simulation and backtracking problems.

---

8. Miscellaneous Collections

LinkedHashSet:

• Maintains insertion order.

Set<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(130);
linkedHashSet.add(140);

LinkedHashMap:

• Maintains insertion order for key-value pairs.

Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("key5", 150);
linkedHashMap.put("key6", 160);

EnumSet:

• Special set for enum types.

enum Color { RED, GREEN, BLUE }
EnumSet<Color> colors = EnumSet.of(Color.RED, Color.GREEN);

---

9. Tips and Tricks

General Tips:

1. Choose the Right Collection:

   • Use List for ordered data.

   • Use Set for unique elements.

   • Use Map for key-value pairs.

   • Use Queue for FIFO operations.

   • Use Deque for both stack and queue operations.

2. Initialization Shortcuts:

   • Use utility methods like Arrays.asList() for quick initialization:

       List<Integer> list = Arrays.asList(1, 2, 3);
     

3. Use Java Stream API for operations like filtering, mapping, etc.:

    List<Integer> filteredList = list.stream().filter(x -> x > 2).collect(Collectors.toList());
   

Interview and OA Tips:

• Time Optimization:

  • Prefer HashSet and HashMap for fast lookups (O(1)).

  • Prefer TreeSet and TreeMap for sorted collections (O(log n)).

• Space Optimization:

  • Use array-based collections (ArrayList, ArrayDeque) for lower memory overhead.

---

10. Additional Java Collection Functions Reference

List Functions

list.add(e);                // Add element to end
list.add(index, e);         // Add at index
list.get(index);            // Get element
list.set(index, e);         // Set element
list.remove(index);         // Remove by index
list.remove(Object o);      // Remove by value
list.contains(e);           // Check existence
list.indexOf(e);            // First index
list.lastIndexOf(e);        // Last index
list.clear();               // Remove all
list.isEmpty();             // Check empty
list.size();                // Size
list.subList(start, end);   // Sublist
list.toArray();             // To Array
list.iterator();            // Iterator
Collections.sort(list);     // Sort
Collections.reverse(list);  // Reverse

Set Functions

set.add(e);
set.remove(e);
set.contains(e);
set.isEmpty();
set.size();
set.clear();
set.iterator();
set.addAll(anotherSet);
set.retainAll(anotherSet);
set.removeAll(anotherSet);

Map Functions

map.put(key, value);
map.get(key);
map.remove(key);
map.containsKey(key);
map.containsValue(value);
map.size();
map.isEmpty();
map.clear();
map.keySet();
map.values();
map.entrySet();
map.putIfAbsent(key, value);
map.replace(key, value);

Queue Functions

queue.add(e);
queue.offer(e);
queue.poll();
queue.remove();
queue.peek();
queue.element();
queue.isEmpty();
queue.size();

Deque Functions

deque.addFirst(e);
deque.addLast(e);
deque.removeFirst();
deque.removeLast();
deque.peekFirst();
deque.peekLast();
deque.offerFirst(e);
deque.offerLast(e);

Stack Functions

stack.push(e);
stack.pop();
stack.peek();
stack.isEmpty();
stack.size();
stack.search(e); // 1-based position from top

---

11. How to Choose the Right Collection?

---

12. Space and Time Complexity Quick Table

* O(1) amortized; may trigger resize.

---