LLD FOCUSED

Data Structures Cheat Sheet

The core data structures needed for building scalable Low-Level Designs, with time complexity analysis.

Lookups

HashMap / Dict

Time: O(1) avg | Space: O(n)

Key-value store. Essential for O(1) lookups, caching, and counting frequencies.

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
// Get with default
int val = map.getOrDefault("B", 0);
// Iterate
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}
Linear

Queue / Deque

Time: O(1) ops | Space: O(n)

FIFO structure. Vital for BFS (Breadth-First Search) and processing tasks in order.

Queue<String> queue = new LinkedList<>();
queue.offer("Task1"); // Enqueue
String task = queue.poll(); // Dequeue
// Deque (Double Ended)
Deque<String> deck = new ArrayDeque<>();
deck.addFirst("Urgent");
Ordering

Priority Queue / Heap

Time: O(log n) add/remove | Space: O(n)

Retrieves the min/max element in O(1). Crucial for Dijkstra's, Top-K problems, and merging intervals.

// Min Heap (Default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder()
);
minHeap.add(10);
int top = minHeap.poll(); // Removes smallest
Linear

Linked List

Time: O(1) insert/del at known node | Space: O(n)

Nodes with pointers. Important for LRU Cache implementation (Doubly Linked List).

class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}
// Java's built-in doubly linked list
LinkedList<String> list = new LinkedList<>();
list.addFirst("Head");
list.removeLast();
Lookups

HashSet / Set

Time: O(1) avg | Space: O(n)

Unordered collection of unique elements. Used for O(1) existence checks and removing duplicates.

Set<String> set = new HashSet<>();
set.add("A");
boolean exists = set.contains("A");
// Operations
set.remove("A");
set.clear();
Hierarchical

Tree / BST

Time: O(h) search | Space: O(n)

Hierarchical structure. Used for File Systems, Organization Charts, and specialized databases.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
// DFS Traversal
void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // process(root.val);
    traverse(root.right);
}