Complete Data Structures Mastery Guide
Introduction: Why Data Structures Matter
Data structures are the foundation of efficient programming. They determine how data is organized in memory and dramatically impact application performance, scalability, and resource usage.
Companies like Google, Facebook, and Microsoft prioritize strong data structure knowledge in hiring because engineers who understand data structures write:
- 50-100x faster code - Choosing the right structure can reduce execution time from seconds to milliseconds
- Better memory usage - Efficient structures reduce memory consumption by 70-90%
- Scalable solutions - Systems that handle millions of requests without crashing
- Maintainable code - Well-structured data is easier to understand and modify
This comprehensive guide covers every major data structure used in production systems, with implementation patterns, complexity analysis, and real-world applications.
1. Arrays - The Foundation Data Structure
What Are Arrays?
An array is a contiguous block of memory containing elements of the same data type. It's the most fundamental data structure and the basis for understanding more complex structures.
Key Characteristics:
- Fixed Size - Size defined at declaration (in most languages)
- Contiguous Memory - All elements stored sequentially
- Fast Access - O(1) access time using index
- Slow Insertion/Deletion - O(n) time for middle elements
- Type Homogeneity - All elements must be same type
Array Operations and Complexity
Operation Time Complexity Space Complexity
Access by index O(1) O(1)
Search O(n) O(1)
Insertion O(n) O(1)
Deletion O(n) O(1)Real-World Array Applications
1. Image Processing
Pixel array: 2D array where each element = color value
Performance-critical: Millions of pixels processed per frame2. Caching Mechanisms
CPU Cache uses fixed-size arrays for fast data retrieval
Memory layout: contiguous for cache line efficiency3. Database Indexing
B+ tree nodes use arrays for sorted key storage
Binary search requires contiguous array structurePractical Implementation Example
public class DynamicArray<T> {
private T[] elements;
private int size;
private static final int INITIAL_CAPACITY = 10;
@SuppressWarnings("unchecked")
public DynamicArray() {
elements = new Object[INITIAL_CAPACITY];
size = 0;
}
public void add(T element) {
if (size == elements.length) {
resize(elements.length * 2);
}
elements[size++] = element;
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return elements[index];
}
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
System.arraycopy(elements, index + 1, elements, index, size - index - 1);
size--;
}
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
T[] newElements = new Object[newCapacity];
System.arraycopy(elements, 0, newElements, 0, size);
elements = newElements;
}
}2. Linked Lists - Dynamic Data Structures
Understanding Linked Lists
A linked list is a linear data structure where elements (nodes) are dynamically allocated. Each node contains:
- Data - The actual value
- Pointer(s) - Reference to next node (and previous in doubly-linked)
Advantages Over Arrays:
- ✓ Dynamic sizing - grow/shrink as needed
- ✓ Efficient insertion/deletion - O(1) if position known
- ✓ No pre-allocation needed
Disadvantages:
- ✗ No random access - must traverse from head
- ✗ Extra memory - pointers overhead
- ✗ Cache unfriendly - nodes scattered in memory
Linked List Variants and Use Cases
1. Singly Linked List
Node → Node → Node → null
Used: Implement stacks, simple queues2. Doubly Linked List
null ← Node ↔ Node ↔ Node → null
Used: LRU Cache, navigation (forward/backward)3. Circular Linked List
Node → Node → Node ↻ (points back to first)
Used: Round-robin scheduling, music playlistsComplete Implementation
public class SinglyLinkedList<T> {
private Node<T> head;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
// Insert at beginning - O(1)
public void insertFirst(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = head;
head = newNode;
size++;
}
// Insert at position - O(n)
public void insertAt(int index, T data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
insertFirst(data);
return;
}
Node<T> current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
Node<T> newNode = new Node<>(data);
newNode.next = current.next;
current.next = newNode;
size++;
}
// Delete at position - O(n)
public T deleteAt(int index) {
if (index < 0 || index >= size || head == null) {
throw new IndexOutOfBoundsException();
}
T data;
if (index == 0) {
data = head.data;
head = head.next;
} else {
Node<T> current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
data = current.next.data;
current.next = current.next.next;
}
size--;
return data;
}
// Search - O(n)
public boolean contains(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) return true;
current = current.next;
}
return false;
}
public int getSize() { return size; }
}3. Stacks - LIFO Data Structure
Stack Operations
Push (add to top) - O(1)
Pop (remove top) - O(1)
Peek (view top) - O(1)
Search - O(n)Real-World Stack Applications
1. Browser Back Button
Press page A → Push A to stack
Press page B → Push B to stack
Click back → Pop B from stack, show A2. Function Call Stack
main() calls func1() → Push func1
func1 calls func2() → Push func2
func2 returns → Pop func23. Expression Evaluation
Infix: 3 + 4 * 2
Convert to postfix: 3 4 2 * +
Evaluate using stack: [3, 4, 2] → multiply 4*2 → add 3+8 = 11Stack Implementation
public class Stack<T> {
private Node<T> top;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) throw new EmptyStackException();
T data = top.data;
top = top.next;
size--;
return data;
}
public T peek() {
if (isEmpty()) throw new EmptyStackException();
return top.data;
}
public boolean isEmpty() { return size == 0; }
public int getSize() { return size; }
}4. Queues - FIFO Data Structure
Queue Operations
Enqueue (add to rear) - O(1)
Dequeue (remove front) - O(1)
Peek (view front) - O(1)Queue Variants
1. Simple Queue (FIFO)
[Front] ← 1, 2, 3 ← [Rear]
Operations: dequeue 1, enqueue 4 → [2, 3, 4]2. Circular Queue
Wraps around when rear reaches end
More efficient space usage in fixed-size queue3. Priority Queue
Elements retrieved based on priority, not arrival order
Used in: OS scheduling, Dijkstra's algorithm, Huffman coding4. Deque (Double-Ended Queue)
Add/remove from both front and rear
Insert at front: prepend operation
Insert at rear: append operationReal-World Queue Applications
1. CPU Scheduling
Process arrives → Added to ready queue
CPU selects → Processes in FIFO order
Process completes → Removed from queue2. Printer Queue
Document 1 submitted → Queue it
Document 2 submitted → Queue it
Printer processes → FIFO order3. Message Processing
Message arrives → Enqueue
Worker processes → Dequeue oldest message
Handles backpressure → Queue grows if workers slowQueue Implementation
public class Queue<T> {
private Node<T> front, rear;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) { this.data = data; }
}
public void enqueue(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
front = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
size++;
}
public T dequeue() {
if (isEmpty()) throw new NoSuchElementException();
T data = front.data;
front = front.next;
if (isEmpty()) rear = null;
size--;
return data;
}
public T peek() {
if (isEmpty()) throw new NoSuchElementException();
return front.data;
}
public boolean isEmpty() { return size == 0; }
public int getSize() { return size; }
}5. Trees - Hierarchical Data Structures
Binary Trees
A binary tree has at most 2 children per node.
A
/ \
B C
/ \
D ETypes:
- Full Binary Tree - Every node has 0 or 2 children
- Complete Binary Tree - All levels filled except possibly last
- Perfect Binary Tree - All internal nodes have 2 children, all leaves same depth
- Balanced Tree - Height difference ≤ 1
Binary Search Tree (BST)
public class BinarySearchTree<T extends Comparable<T>> {
private Node<T> root;
private static class Node<T> {
T data;
Node<T> left, right;
Node(T data) { this.data = data; }
}
// Insert - O(log n) average, O(n) worst
public void insert(T data) {
root = insertRecursive(root, data);
}
private Node<T> insertRecursive(Node<T> node, T data) {
if (node == null) return new Node<>(data);
int cmp = data.compareTo(node.data);
if (cmp < 0) {
node.left = insertRecursive(node.left, data);
} else if (cmp > 0) {
node.right = insertRecursive(node.right, data);
}
return node;
}
// Search - O(log n) average, O(n) worst
public boolean search(T data) {
return searchRecursive(root, data);
}
private boolean searchRecursive(Node<T> node, T data) {
if (node == null) return false;
int cmp = data.compareTo(node.data);
if (cmp < 0) {
return searchRecursive(node.left, data);
} else if (cmp > 0) {
return searchRecursive(node.right, data);
}
return true;
}
// In-order traversal: Left → Root → Right (sorted order)
public void inOrder() {
inOrderRecursive(root);
}
private void inOrderRecursive(Node<T> node) {
if (node == null) return;
inOrderRecursive(node.left);
System.out.print(node.data + " ");
inOrderRecursive(node.right);
}
}AVL Trees - Self-Balancing BSTs
AVL trees maintain balance factor and rebalance on insertion/deletion to guarantee O(log n) operations.
Balance Factor = Height(left) - Height(right)
Valid range: -1, 0, 1
If violated: Perform rotations (LL, RR, LR, RL)Red-Black Trees
Rules:
- Every node is red or black
- Root is black
- Leaves (null) are black
- Red nodes have black children
- All paths from node to leaf have same black node count
Used in: Linux kernel schedulers, Java's TreeMap, C++ STL map
6. Hash Tables - Fast Lookup
How Hash Tables Work
1. Key → Hash Function → Index
2. Store value at index in array
3. Collision handling (chaining or probing)Collision Resolution Strategies
1. Chaining (Separate Chaining)
Hash table: [Linked List | Linked List | Linked List | ...]
Collision: Add to chain
Pros: Easy implementation
Cons: Extra memory for pointers2. Open Addressing
Linear Probing: Find next empty slot
Quadratic Probing: Skip increasingly
Double Hashing: Use second hash function
Pros: Better cache locality
Cons: Clustering, deletion issuesHash Table Implementation
public class HashTable<K, V> {
private static final int INITIAL_CAPACITY = 16;
private Entry<K, V>[] table;
private int size;
private float loadFactor = 0.75f;
@SuppressWarnings("unchecked")
public HashTable() {
table = new Entry[INITIAL_CAPACITY];
size = 0;
}
private static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
public void put(K key, V value) {
if (size >= table.length * loadFactor) {
resize();
}
int index = hash(key);
Entry<K, V> entry = table[index];
// Check if key exists (update)
while (entry != null) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
entry = entry.next;
}
// Insert new entry at beginning of chain
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = table[index];
table[index] = newEntry;
size++;
}
public V get(K key) {
int index = hash(key);
Entry<K, V> entry = table[index];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
private int hash(K key) {
return Math.abs(key.hashCode()) % table.length;
}
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] oldTable = table;
table = new Entry[oldTable.length * 2];
size = 0;
for (Entry<K, V> entry : oldTable) {
while (entry != null) {
put(entry.key, entry.value);
entry = entry.next;
}
}
}
}7. Graphs - Network Representations
Graph Basics
Components:
- Vertices (nodes)
- Edges (connections)
Types:
- Directed - Edges have direction
- Undirected - Edges bidirectional
- Weighted - Edges have weights
- Cyclic - Contains cycles
- Acyclic - No cycles (DAG)
Graph Representations
1. Adjacency Matrix
O(1) edge lookup but O(V²) space
Good for: Dense graphs, small graphs2. Adjacency List
O(V+E) space, O(degree) edge lookup
Good for: Sparse graphs, large graphsGraph Traversal Algorithms
Depth-First Search (DFS) - O(V+E)
public void dfs(Vertex start) {
Set<Vertex> visited = new HashSet<>();
Stack<Vertex> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
Vertex current = stack.pop();
if (!visited.contains(current)) {
visited.add(current);
System.out.print(current + " ");
for (Vertex neighbor : current.neighbors) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
}Breadth-First Search (BFS) - O(V+E)
public void bfs(Vertex start) {
Set<Vertex> visited = new HashSet<>();
Queue<Vertex> queue = new Queue<>();
queue.enqueue(start);
visited.add(start);
while (!queue.isEmpty()) {
Vertex current = queue.dequeue();
System.out.print(current + " ");
for (Vertex neighbor : current.neighbors) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.enqueue(neighbor);
}
}
}
}Famous Graph Algorithms
1. Dijkstra's Algorithm - Shortest path O(E log V) 2. Bellman-Ford - Shortest path (handles negative weights) O(VE) 3. Floyd-Warshall - All pairs shortest paths O(V³) 4. Topological Sort - DAG ordering O(V+E) 5. Strongly Connected Components - Find SCCs O(V+E)
Key Takeaways for Interviews
- Understand Trade-offs - Every structure trades speed for space
- Complexity Analysis - Know average vs worst case
- Implementation - Can you code it from scratch?
- Real-World Use - When/why to use each structure
- Optimization - Can you improve space/time?
Study Strategy:
- Implement each structure completely
- Solve 50+ problems using them
- Understand when to use which
- Practice coding without references