• English • Jackey

Java Data Structures Quick Reference for LeetCode - Complete Cheat Sheet

Master essential Java data structures for coding interviews with this comprehensive guide covering Queue, Stack, List, Set, Map, Heap, String, and Array utilities. Includes method signatures, time complexity, and LeetCode patterns from 11-year FAANG veteran.

#java #data-structures #leetcode #interview-prep #cheat-sheet #reference-guide #algorithm

Introduction: Your Interview Swiss Army Knife

When solving LeetCode problems in Java, knowing which data structure to use and which methods are available can make the difference between a quick solve and getting stuck for 30 minutes.

This guide is your quick reference cheat sheet for the most common Java data structures used in coding interviews. After 11+ years at Microsoft, Booking.com, and Alibaba, I’ve distilled the essential operations you’ll reach for again and again.

How to Use This Guide

  • During prep: Read through each section to familiarize yourself with available methods
  • During practice: Keep this open as a quick lookup reference
  • Before interviews: Review the time complexity tables to avoid performance pitfalls

Java Version Notes

  • This guide covers Java 8+ features
  • All code examples are interview-ready (no external dependencies)
  • Focus on java.util.* package (standard library)

1. Queue & Stack Operations

ArrayDeque (Recommended for Stacks & Queues)

ArrayDeque is the modern, preferred implementation for both queue and stack operations. It’s faster than LinkedList and Stack.

As a Queue (FIFO)

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

// Add elements (back of queue)
queue.offer(1);        // Returns boolean, O(1)
queue.add(2);          // Throws exception on failure, O(1)

// Remove elements (front of queue)
Integer val = queue.poll();  // Returns null if empty, O(1)
Integer val = queue.remove(); // Throws exception if empty, O(1)

// Peek (don't remove)
Integer val = queue.peek();  // Returns null if empty, O(1)
Integer val = queue.element(); // Throws exception if empty, O(1)

// Size
int size = queue.size();     // O(1)
boolean empty = queue.isEmpty(); // O(1)

As a Stack (LIFO)

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

// Push (add to top)
stack.push(1);         // O(1)

// Pop (remove from top)
Integer val = stack.pop();   // Throws exception if empty, O(1)

// Peek (don't remove)
Integer val = stack.peek();  // Returns null if empty, O(1)

// Size
int size = stack.size();     // O(1)
boolean empty = stack.isEmpty(); // O(1)

As a Deque (Double-Ended Queue)

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

// Add to front
deque.offerFirst(1);   // O(1)
deque.addFirst(2);     // O(1)

// Add to back
deque.offerLast(3);    // O(1)
deque.addLast(4);      // O(1)

// Remove from front
Integer val = deque.pollFirst();  // O(1)
Integer val = deque.removeFirst(); // O(1)

// Remove from back
Integer val = deque.pollLast();   // O(1)
Integer val = deque.removeLast();  // O(1)

// Peek
Integer front = deque.peekFirst(); // O(1)
Integer back = deque.peekLast();   // O(1)

Stack (Legacy - Avoid in Interviews)

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

stack.push(1);         // O(1)
Integer val = stack.pop();   // O(1)
Integer val = stack.peek();  // O(1)
boolean empty = stack.empty(); // O(1)
int pos = stack.search(1);   // O(n), returns 1-based position

⚠️ Interview Tip: Prefer ArrayDeque over Stack. Interviewers may comment that Stack is legacy code.

Comparison Table

OperationArrayDeque (Queue)ArrayDeque (Stack)LinkedListStack (Legacy)
Add/Pushoffer() O(1)push() O(1)offer() O(1)push() O(1)
Remove/Poppoll() O(1)pop() O(1)poll() O(1)pop() O(1)
Peekpeek() O(1)peek() O(1)peek() O(1)peek() O(1)
Speed⚡ Fastest⚡ FastestSlowerSlower

Common LeetCode Patterns

Monotonic Stack: Track next greater/smaller element

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        int idx = stack.pop();
        // Process...
    }
    stack.push(i);
}

Sliding Window Maximum: Use deque to maintain max in window

Deque<Integer> deque = new ArrayDeque<>(); // Store indices

2. List Operations

ArrayList (Dynamic Array)

Best for random access and sequential iteration.

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

// Add elements
list.add(1);           // Add to end, O(1) amortized
list.add(0, 10);       // Insert at index, O(n)

// Access elements
int val = list.get(0); // O(1)
list.set(0, 20);       // O(1)

// Remove elements
list.remove(0);        // Remove by index, O(n)
list.remove(Integer.valueOf(10)); // Remove by value, O(n)

// Search
boolean exists = list.contains(10); // O(n)
int index = list.indexOf(10);       // O(n), returns -1 if not found
int lastIdx = list.lastIndexOf(10); // O(n)

// Size
int size = list.size();      // O(1)
boolean empty = list.isEmpty(); // O(1)
list.clear();                // O(n)

// Sorting
Collections.sort(list);      // O(n log n)
Collections.sort(list, Collections.reverseOrder()); // Descending

// Conversion
int[] arr = list.stream().mapToInt(i -> i).toArray(); // To array

LinkedList (Doubly-Linked List)

Best for frequent insertions/deletions at both ends.

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

// Add at ends
list.addFirst(1);      // O(1)
list.addLast(2);       // O(1)

// Remove from ends
Integer first = list.removeFirst(); // O(1)
Integer last = list.removeLast();   // O(1)

// Peek (don't remove)
Integer first = list.peekFirst();   // O(1), returns null if empty
Integer last = list.peekLast();     // O(1)

// Access (slow!)
int val = list.get(0); // O(n) - avoid this!

Comparison Table

OperationArrayListLinkedList
Access by indexO(1)O(n) ❌
Add/Remove at endO(1)O(1)
Add/Remove at beginningO(n)O(1) ✅
Add/Remove at middleO(n)O(n)
Memory overheadLowHigh (pointers)
Use caseRandom accessFrequent head/tail ops

Common LeetCode Patterns

Two Pointers:

int left = 0, right = list.size() - 1;
while (left < right) {
    // Process...
    left++;
    right--;
}

Binary Search on Sorted List:

Collections.sort(list);
int idx = Collections.binarySearch(list, target); // O(log n)
// Returns index if found, or (-(insertion point) - 1) if not found

3. Set Operations

HashSet (Unordered)

Best for fast lookups when order doesn’t matter.

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

// Add elements
boolean added = set.add(1);     // O(1), returns false if already exists

// Remove elements
boolean removed = set.remove(1); // O(1)

// Check existence
boolean exists = set.contains(1); // O(1)

// Size
int size = set.size();      // O(1)
boolean empty = set.isEmpty(); // O(1)

// Iteration
for (int val : set) {
    // Unordered!
}

// Set operations
Set<Integer> set2 = new HashSet<>(Arrays.asList(2, 3, 4));
set.addAll(set2);           // Union
set.retainAll(set2);        // Intersection
set.removeAll(set2);        // Difference

TreeSet (Sorted)

Best for maintaining sorted order and range queries.

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

// Add/Remove (same as HashSet but O(log n))
set.add(5);                 // O(log n)
set.remove(5);              // O(log n)
boolean exists = set.contains(5); // O(log n)

// Sorted access
Integer first = set.first();    // O(log n), smallest element
Integer last = set.last();      // O(log n), largest element

// Range queries
Integer ceil = set.ceiling(4);  // O(log n), smallest >= 4, null if none
Integer floor = set.floor(4);   // O(log n), largest <= 4, null if none
Integer higher = set.higher(4); // O(log n), smallest > 4
Integer lower = set.lower(4);   // O(log n), largest < 4

// Subset views
SortedSet<Integer> head = set.headSet(5);    // Elements < 5
SortedSet<Integer> tail = set.tailSet(5);    // Elements >= 5
SortedSet<Integer> sub = set.subSet(2, 8);   // Elements [2, 8)

// Remove first/last
Integer first = set.pollFirst();  // O(log n), remove and return
Integer last = set.pollLast();    // O(log n)

LinkedHashSet (Insertion Order)

Maintains insertion order with HashSet performance.

Set<Integer> set = new LinkedHashSet<>();
// Same methods as HashSet, but iteration preserves insertion order

Comparison Table

OperationHashSetTreeSetLinkedHashSet
Add/RemoveO(1) ✅O(log n)O(1) ✅
ContainsO(1) ✅O(log n)O(1) ✅
OrderNoneSorted ✅Insertion ✅
Range queries❌✅ ceiling/floor❌
Use caseFast lookupSorted dataPreserve order

Common LeetCode Patterns

Find Duplicates:

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (!seen.add(num)) {
        // Duplicate found!
    }
}

Two Sum with Set:

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (seen.contains(target - num)) {
        return true;
    }
    seen.add(num);
}

4. Map Operations

HashMap (Unordered)

Best for fast key-value lookups when order doesn’t matter.

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

// Put elements
map.put("key", 1);          // O(1), returns old value or null
map.putIfAbsent("key", 2);  // O(1), only put if key doesn't exist

// Get elements
Integer val = map.get("key");     // O(1), returns null if not found
Integer val = map.getOrDefault("key", 0); // O(1), with default

// Check existence
boolean hasKey = map.containsKey("key");   // O(1)
boolean hasVal = map.containsValue(1);     // O(n) - slow!

// Remove
Integer removed = map.remove("key");       // O(1), returns old value

// Size
int size = map.size();      // O(1)
boolean empty = map.isEmpty(); // O(1)

// Iteration (BEST PRACTICE)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

// Iterate keys only
for (String key : map.keySet()) {
    // O(n)
}

// Iterate values only
for (Integer value : map.values()) {
    // O(n)
}

// Compute methods (Java 8+)
map.merge("key", 1, Integer::sum);  // Increment by 1
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
map.computeIfAbsent("key", k -> 0);
map.computeIfPresent("key", (k, v) -> v + 1);

TreeMap (Sorted by Keys)

Best for maintaining sorted key order and range queries.

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

// Basic operations (same as HashMap but O(log n))
map.put(5, "five");         // O(log n)
String val = map.get(5);    // O(log n)
map.remove(5);              // O(log n)

// Sorted access
Integer firstKey = map.firstKey();  // O(log n), smallest key
Integer lastKey = map.lastKey();    // O(log n), largest key

Map.Entry<Integer, String> firstEntry = map.firstEntry();  // O(log n)
Map.Entry<Integer, String> lastEntry = map.lastEntry();    // O(log n)

// Range queries
Integer ceilKey = map.ceilingKey(4);  // O(log n), smallest key >= 4
Integer floorKey = map.floorKey(4);   // O(log n), largest key <= 4
Integer higherKey = map.higherKey(4); // O(log n), smallest key > 4
Integer lowerKey = map.lowerKey(4);   // O(log n), largest key < 4

Map.Entry<Integer, String> ceilEntry = map.ceilingEntry(4);
Map.Entry<Integer, String> floorEntry = map.floorEntry(4);

// Submap views
SortedMap<Integer, String> head = map.headMap(5);    // Keys < 5
SortedMap<Integer, String> tail = map.tailMap(5);    // Keys >= 5
SortedMap<Integer, String> sub = map.subMap(2, 8);   // Keys [2, 8)

// Remove first/last
Map.Entry<Integer, String> first = map.pollFirstEntry();  // O(log n)
Map.Entry<Integer, String> last = map.pollLastEntry();    // O(log n)

LinkedHashMap (Insertion/Access Order)

Maintains insertion order or access order (useful for LRU Cache).

// Insertion order (default)
Map<Integer, String> map = new LinkedHashMap<>();

// Access order (for LRU Cache)
Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
// Parameters: initialCapacity, loadFactor, accessOrder=true

// Override removeEldestEntry for LRU eviction
Map<Integer, String> lruCache = new LinkedHashMap<Integer, String>(capacity, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > capacity;
    }
};

Comparison Table

OperationHashMapTreeMapLinkedHashMap
Put/Get/RemoveO(1) ✅O(log n)O(1) ✅
OrderNoneSorted ✅Insertion/Access ✅
Range queries❌✅ ceiling/floor❌
Use caseFast lookupSorted keysLRU cache

Common LeetCode Patterns

Frequency Map:

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

Sliding Window with Map:

Map<Character, Integer> window = new HashMap<>();
int left = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window.put(c, window.getOrDefault(c, 0) + 1);
    
    while (/* condition */) {
        char d = s.charAt(left);
        window.put(d, window.get(d) - 1);
        if (window.get(d) == 0) window.remove(d);
        left++;
    }
}

5. Heap / PriorityQueue

PriorityQueue (Min Heap by Default)

Best for maintaining top K elements or processing in priority order.

// Min heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max heap (reverse order)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Custom comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// Add elements
pq.offer(5);           // O(log n), returns boolean
pq.add(3);             // O(log n), throws exception on failure

// Remove elements
Integer min = pq.poll();   // O(log n), returns null if empty
Integer min = pq.remove(); // O(log n), throws exception if empty

// Peek (don't remove)
Integer min = pq.peek();   // O(1), returns null if empty
Integer min = pq.element(); // O(1), throws exception if empty

// Size
int size = pq.size();      // O(1)
boolean empty = pq.isEmpty(); // O(1)

// Remove specific element (slow!)
pq.remove(5);          // O(n) - avoid if possible!

// Contains (slow!)
boolean exists = pq.contains(5); // O(n) - avoid!

Custom Comparators

// Compare by first element of array
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// Compare by custom object field
class Task {
    int priority;
    String name;
}
PriorityQueue<Task> pq = new PriorityQueue<>((a, b) -> a.priority - b.priority);

// Multiple criteria
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) return a[0] - b[0];  // First by a[0]
    return a[1] - b[1];                     // Then by a[1]
});

// Using Comparator.comparing (Java 8+)
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparing(t -> t.priority)
);

Comparison Table

OperationPriorityQueue
Add/OfferO(log n)
Poll/RemoveO(log n)
PeekO(1)
Remove specificO(n) ❌
ContainsO(n) ❌
OrderingMin heap (default)

Common LeetCode Patterns

Top K Elements:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();  // Remove smallest
    }
}
// minHeap now contains top K largest elements
int kthLargest = minHeap.peek();

Merge K Sorted Lists:

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// Add first node from each list
for (ListNode head : lists) {
    if (head != null) pq.offer(head);
}

while (!pq.isEmpty()) {
    ListNode node = pq.poll();
    // Add to result...
    if (node.next != null) pq.offer(node.next);
}

Sliding Window Maximum (alternative to deque):

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// Store [value, index] pairs

6. String Utilities

String (Immutable)

Strings are immutable in Java - every modification creates a new string.

String s = "hello";

// Access
int len = s.length();           // O(1)
char c = s.charAt(0);           // O(1)

// Substring
String sub = s.substring(1);    // O(n), "ello"
String sub = s.substring(1, 4); // O(n), "ell" [inclusive, exclusive)

// Search
int idx = s.indexOf('l');       // O(n), first occurrence, returns -1 if not found
int idx = s.indexOf("ll");      // O(n), substring search
int lastIdx = s.lastIndexOf('l'); // O(n), last occurrence

boolean starts = s.startsWith("he");  // O(k) where k = prefix length
boolean ends = s.endsWith("lo");      // O(k) where k = suffix length

boolean contains = s.contains("ll");  // O(n)

// Comparison
boolean eq = s.equals("hello");       // O(n), content comparison
boolean eqIgnore = s.equalsIgnoreCase("HELLO"); // O(n)
int cmp = s.compareTo("world");       // O(n), lexicographic

// Modification (creates new string!)
String upper = s.toUpperCase();       // O(n)
String lower = s.toLowerCase();       // O(n)
String trim = s.trim();               // O(n), remove leading/trailing whitespace
String replaced = s.replace('l', 'r'); // O(n), "herro"
String replaced = s.replaceAll("l+", "L"); // O(n), regex

// Split
String[] parts = s.split(",");        // O(n)
String[] parts = s.split(",", 2);     // Limit to 2 parts

// Join (Java 8+)
String joined = String.join(",", "a", "b", "c"); // "a,b,c"

// Conversion
char[] chars = s.toCharArray();       // O(n)
byte[] bytes = s.getBytes();          // O(n)

// Check empty
boolean empty = s.isEmpty();          // O(1), checks length == 0
boolean blank = s.isBlank();          // O(n), checks if only whitespace (Java 11+)

StringBuilder (Mutable)

Use for frequent string modifications to avoid creating many intermediate strings.

StringBuilder sb = new StringBuilder();
StringBuilder sb = new StringBuilder(capacity); // Pre-allocate
StringBuilder sb = new StringBuilder("initial"); // With initial string

// Append
sb.append("hello");        // O(1) amortized
sb.append(123);            // O(1), works with any type
sb.append(true);           // O(1)
sb.append('x');            // O(1)

// Insert
sb.insert(0, "prefix");    // O(n), insert at index

// Delete
sb.deleteCharAt(0);        // O(n), remove character at index
sb.delete(0, 3);           // O(n), remove [start, end)

// Replace
sb.setCharAt(0, 'H');      // O(1), replace character
sb.replace(0, 3, "Hi");    // O(n), replace [start, end)

// Access
char c = sb.charAt(0);     // O(1)
int len = sb.length();     // O(1)

// Reverse
sb.reverse();              // O(n)

// Convert to string
String s = sb.toString();  // O(n)

// Clear
sb.setLength(0);           // O(1), resets length

StringBuffer (Thread-Safe)

Same API as StringBuilder but synchronized (slower). Use only if you need thread safety.

StringBuffer sbuf = new StringBuffer();
// Same methods as StringBuilder

Performance Comparison

OperationStringStringBuilderStringBuffer
Concat/ModifyO(n) per op ❌O(1) amortized ✅O(1) amortized
Thread-safe✅❌✅
SpeedSlow for many ops⚡ FastSlower (sync)
Use caseFew modificationsMany modificationsThread-safe

⚠️ Interview Tip: If you’re building a string in a loop, always use StringBuilder!

// ❌ BAD - O(n²) because each concat creates new string
String result = "";
for (String s : strings) {
    result += s;  // Creates new string every time!
}

// ✅ GOOD - O(n)
StringBuilder sb = new StringBuilder();
for (String s : strings) {
    sb.append(s);
}
String result = sb.toString();

Common LeetCode Patterns

Palindrome Check:

// Method 1: Two pointers on original string
int left = 0, right = s.length() - 1;
while (left < right) {
    if (s.charAt(left) != s.charAt(right)) return false;
    left++;
    right--;
}

// Method 2: Reverse with StringBuilder
String reversed = new StringBuilder(s).reverse().toString();
return s.equals(reversed);

String Building:

StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
    if (isValid(c)) {
        sb.append(c);
    }
}
return sb.toString();

Character Frequency:

int[] freq = new int[26];  // For lowercase a-z
for (char c : s.toCharArray()) {
    freq[c - 'a']++;
}

7. Array Utilities

Arrays Class

Static utility methods for array operations.

int[] arr = {5, 2, 8, 1, 9};

// Sorting
Arrays.sort(arr);              // O(n log n), in-place, ascending
Arrays.sort(arr, 0, 3);        // O(k log k), sort subarray [0, 3)

// For object arrays with comparator
Integer[] nums = {5, 2, 8, 1, 9};
Arrays.sort(nums, Collections.reverseOrder());  // Descending
Arrays.sort(nums, (a, b) -> a - b);             // Custom comparator

// 2D array sorting
int[][] intervals = {{2, 5}, {1, 3}, {4, 6}};
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // Sort by first element

// Binary search (MUST be sorted first!)
Arrays.sort(arr);
int idx = Arrays.binarySearch(arr, 8);  // O(log n)
// Returns index if found, or (-(insertion point) - 1) if not found

// Copy
int[] copy = Arrays.copyOf(arr, arr.length);      // O(n), copy entire array
int[] copy = Arrays.copyOf(arr, 10);              // O(n), resize (pad with 0)
int[] range = Arrays.copyOfRange(arr, 1, 4);     // O(k), copy [1, 4)

// Fill
Arrays.fill(arr, 0);           // O(n), fill entire array
Arrays.fill(arr, 0, 3, -1);    // O(k), fill [0, 3) with -1

// Compare
boolean eq = Arrays.equals(arr1, arr2);          // O(n), shallow equality
int cmp = Arrays.compare(arr1, arr2);            // O(n), lexicographic

// Deep equals for multidimensional arrays
boolean eq = Arrays.deepEquals(matrix1, matrix2);

// Convert to string
String s = Arrays.toString(arr);                 // "[5, 2, 8, 1, 9]"
String s = Arrays.deepToString(matrix);          // For multidimensional

// Convert to list
List<Integer> list = Arrays.asList(1, 2, 3);     // Fixed-size list!
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3)); // Mutable

Primitive Array Operations

int[] arr = {1, 2, 3, 4, 5};

// Length (field, not method!)
int len = arr.length;          // O(1), NO parentheses!

// Clone (shallow copy)
int[] copy = arr.clone();      // O(n)

// System.arraycopy (fastest way to copy)
int[] dest = new int[5];
System.arraycopy(arr, 0, dest, 0, 5);  // O(n)
// Parameters: src, srcPos, dest, destPos, length

Collections Utility (for Lists)

List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));

// Sorting
Collections.sort(list);                          // O(n log n), ascending
Collections.sort(list, Collections.reverseOrder()); // Descending
Collections.sort(list, (a, b) -> a - b);        // Custom comparator

// Binary search (MUST be sorted!)
Collections.sort(list);
int idx = Collections.binarySearch(list, 8);    // O(log n)

// Min/Max
int min = Collections.min(list);                // O(n)
int max = Collections.max(list);                // O(n)

// Reverse
Collections.reverse(list);                      // O(n)

// Shuffle
Collections.shuffle(list);                      // O(n), random permutation

// Frequency
int count = Collections.frequency(list, 5);     // O(n), count occurrences

// Fill
Collections.fill(list, 0);                      // O(n), replace all elements

// Swap
Collections.swap(list, 0, 4);                   // O(1), swap two elements

Common LeetCode Patterns

Two Pointers on Sorted Array:

Arrays.sort(arr);
int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return true;
    else if (sum < target) left++;
    else right--;
}

Binary Search Template:

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;  // Not found

Prefix Sum:

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// Sum of [i, j] = prefix[j + 1] - prefix[i]

8. Quick Reference Tables

Time Complexity Summary

Data StructureAdd/InsertRemoveAccess/GetSearchNotes
ArrayListO(1) end, O(n) middleO(n)O(1)O(n)Best for random access
LinkedListO(1) endsO(1) endsO(n) ❌O(n)Best for head/tail ops
HashSetO(1)O(1)-O(1)Fast lookup, no order
TreeSetO(log n)O(log n)-O(log n)Sorted, range queries
HashMapO(1)O(1)O(1)O(1) keyFast key-value lookup
TreeMapO(log n)O(log n)O(log n)O(log n) keySorted keys, range queries
PriorityQueueO(log n)O(log n)O(1) peekO(n)Min/Max heap
ArrayDequeO(1)O(1)--Best for stack/queue

When to Use Which Data Structure

Need fast lookup by key?
├─ Order matters?
│  ├─ YES → TreeMap (sorted) or LinkedHashMap (insertion)
│  └─ NO → HashMap ✅
│
Need unique elements only?
├─ Order matters?
│  ├─ YES → TreeSet (sorted) or LinkedHashSet (insertion)
│  └─ NO → HashSet ✅
│
Need ordered sequence with duplicates?
├─ Random access by index?
│  ├─ YES → ArrayList ✅
│  └─ NO → LinkedList (if many head/tail operations)
│
Need FIFO (queue) or LIFO (stack)?
└─ ArrayDeque ✅
│
Need always access min/max?
└─ PriorityQueue ✅

Common Pitfalls

PitfallWhy It’s WrongSolution
list.remove(1) on List<Integer>Removes index 1, not value 1Use list.remove(Integer.valueOf(1))
Using == for stringsCompares references, not contentUse s1.equals(s2)
poll() vs remove()poll() returns null, remove() throwsKnow the difference for nulls
String concat in loopO(n²) timeUse StringBuilder
LinkedList.get(i) in loopO(n²) timeUse iterator or ArrayList
Modifying collection while iteratingConcurrentModificationExceptionUse iterator.remove()
Forgetting to sort before binary searchWrong resultsAlways sort first!
arr.length()Compile error (it’s a field)Use arr.length (no parentheses)

9. Common Interview Patterns by Data Structure

Pattern → Data Structure Mapping

PatternBest Data StructureExample Problems
Sliding WindowHashMap (frequency), DequeLongest Substring Without Repeating Characters
Two PointersArrayList (sorted)Two Sum II, Container With Most Water
Monotonic StackArrayDeque (as stack)Next Greater Element, Largest Rectangle
Top K ElementsPriorityQueueKth Largest Element, Top K Frequent
Frequency CountingHashMapValid Anagram, Group Anagrams
Fast LookupHashSetContains Duplicate, Two Sum
Range QueriesTreeMap/TreeSetCount of Range Sum, My Calendar
LRU CacheLinkedHashMapLRU Cache (LC 146)
Merge K SortedPriorityQueueMerge K Sorted Lists
Graph BFS/DFSArrayDeque (queue for BFS)Number of Islands

10. Conclusion: Your Interview Arsenal

Key Takeaways

  1. Default Choices: HashMap for lookups, ArrayList for sequences, ArrayDeque for stack/queue
  2. Need Sorted?: Use TreeMap/TreeSet for automatic ordering
  3. String Building?: Always use StringBuilder in loops
  4. Binary Search?: Remember to sort first with Arrays.sort()
  5. Time Complexity: Know the O(1) vs O(log n) vs O(n) operations

Practice Strategy

Week 1-2: Implement basic operations for each data structure

  • Create small programs using ArrayList, HashMap, ArrayDeque
  • Practice conversions (Array ↔ List, String ↔ char[])

Week 3-4: Solve pattern-specific problems

Week 5+: Time yourself and practice explaining your data structure choices

Final Interview Tips

✅ Do:

  • Explain why you chose a particular data structure
  • Mention time complexity of key operations
  • Use modern APIs (ArrayDeque over Stack)
  • Consider edge cases (null, empty, duplicates)

❌ Don’t:

  • Use legacy classes (Vector, Hashtable, Stack)
  • Forget to check for null/empty
  • Mix up method names (poll vs pop, length vs length())
  • Modify strings in loops without StringBuilder

Ready to Master Java for Interviews?

This reference guide covers 90% of the data structures you’ll use in LeetCode and real interviews. Bookmark this page and revisit it as you practice.

For deeper dives into specific algorithms, check out my other articles on Binary Search, Monotonic Stack, and LRU Cache.

Happy coding! 🚀

About the author: Jackey has 11+ years of experience at Microsoft, Booking.com, and Alibaba, conducting 500+ technical interviews. This guide distills practical knowledge from real interview scenarios.

← Back to Blog