Data Structures

Group:

Data Structure	Shape	Group	Description	Time Complexity (Average)				Time Complexity (Worst)				Space
Data Structure	Shape	Group	Description	Access	Search	Insert	Delete	Access	Search	Insert	Delete	Space
Array		List	A collection of elements, each identified by an index or a key	Θ(1)	Θ(n)	Θ(n)	Θ(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Stack		List	Follows the Last-In-First-Out (LIFO) principle	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Queue		List	Follows the First-In-First-Out (FIFO) principle	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Deque		List	A double-ended queue that allows insertion and deletion at both the front and back	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Vector		List	A dynamic array that automatically resizes itself when elements are added or removed	Θ(1)	Θ(n)	Θ(n)	Θ(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Single-Linked-List		List	Consists of nodes, each containing data and a reference to the next node. It allows efficient insertion and deletion at the head or tail	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Double-Linked-List		List	Extends the single-linked list by having references to both the next and previous nodes. It enables bidirectional traversal	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Skip-List		List	Probabilistic data structure, it uses multiple levels of linked lists	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(n)	O(n)	O(n)	O(n)	O(n log(n))
Binary-Search-Tree		Tree	Consists of nodes, each having at most two children	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Cartesian-Tree		Tree	Binary tree where the values of nodes satisfy the heap property with respect to both the parent and the child	N/A	Θ(log(n))	Θ(log(n))	Θ(log(n))	N/A	O(n)	O(n)	O(n)	O(n)
B-Tree		Tree	Self-balancing tree structure that maintains sorted data and is commonly used in databases and file systems	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Red-Black-Tree		Tree	Self-balancing binary search tree that maintains balance through color-coded nodes	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Splay-Tree		Tree	Self-adjusting binary search tree. It reorganizes itself during operations to improve access times for frequently accessed nodes	N/A	Θ(log(n))	Θ(log(n))	Θ(log(n))	N/A	O(log(n))	O(log(n))	O(log(n))	O(n)
AVL-Tree		Tree	Self-balancing binary search tree. It ensures that the height difference between left and right subtrees is at most one	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
KD-Tree		Tree	Binary tree used for efficient multidimensional data search. It partitions space into regions based on data points	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Min-Heap		Tree	The parent is less than or equal to its children	Θ(1)	Θ(n)	Θ(log(n))	Θ(log(n))	O(1)	O(n)	O(log(n))	O(log(n))	O(n)
Max-Heap		Tree	The parent is greater than or equal to its children	Θ(1)	Θ(n)	Θ(log(n))	Θ(log(n))	O(1)	O(n)	O(log(n))	O(log(n))	O(n)
Segment-Tree		Tree	A binary tree used for storing intervals or segments, allowing efficient range queries and updates	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Hash-Table		Other	Uses a hash function to map keys to indices in an array	N/A	Θ(1)	Θ(1)	Θ(1)	N/A	O(n)	O(n)	O(n)	O(n)
Graph		Other	Consists of nodes connected by edges	Θ(1)	Θ(V + E)	Θ(1)	Θ(1)	O(1)	O(V + E)	O(1)	O(1)	O(V + E)

Senior-level notes

What an interviewer wants to hear beyond the Big-O row. Not every data structure has notes yet — this list grows as interview material surfaces.

Array

Senior insight

Contiguous memory is the secret. Access is O(1) because the CPU computes `base + i · stride` and prefetches the next cache line — linked lists lose on every traversal for the same Big-O because they thrash the cache. In realtime systems, pre-size the array or use a ring buffer to avoid the O(n) doubling spike that tail-latency charts will show.

Common traps

Mid-array insert / delete is O(n), even though access is O(1)
Treating amortized O(1) append as if every single append is O(1) — one in log₂n calls is O(n)

Follow-up questions

? When would a linked list actually beat a dynamic array in practice?
? How does cache-line size (typically 64 bytes) affect the constant factor?

Patterns that use this:Two Pointers, Sliding Window, Binary Search, Interval Merge / Sweep, Dynamic Programming, Greedy

Stack

Senior insight

Recursive algorithms quietly use the program call stack as this data structure — so any recursive DFS is one stack-overflow away from the same bug that explicit iterative DFS avoids. Reach for an explicit stack when depth might exceed ~10k frames.

Common traps

Not handling the empty-stack case on pop / peek (language-dependent: None vs exception)
Using a stack where a monotonic stack would solve the problem in O(n) amortized

Follow-up questions

? How would you evaluate an expression in reverse Polish notation?
? When would you prefer a deque over a stack for LIFO work?

Patterns that use this:Depth-First Search, Monotonic Stack

Queue

Senior insight

An unbounded queue is a latent memory leak — producers faster than consumers will consume all RAM. Production queues always have a bound, plus a policy for what to do when full (backpressure, drop-oldest, drop-newest, block).

Common traps

Using a plain list as a queue in Python (`pop(0)` is O(n)) — use `collections.deque`
Treating an in-process queue as a message broker without durability guarantees

Follow-up questions

? Implement a circular queue in a fixed-size array
? What does a bounded queue give you that an unbounded one does not?

Patterns that use this:Breadth-First Search, Topological Sort

Single-Linked-List

Senior insight

The O(1) insert is only at the head (or at a known node) — arbitrary-position insert still requires an O(n) traversal to find the predecessor. The cache-unfriendly layout makes linked lists slower than arrays in practice for almost all workloads. Real wins: constant-time splicing of known nodes (LRU cache), persistent data structures, intrusive lists in kernels.

Common traps

Losing the head reference while reversing — always save `next` before updating a pointer
Leaking the predecessor's `next` pointer when deleting a node in the middle

Follow-up questions

? Reverse a linked list iteratively and recursively — complexity of each?
? Why does LRU cache use a doubly-linked list specifically?

Patterns that use this:Fast / Slow Pointers

Binary-Search-Tree

Senior insight

A plain BST degrades to a linked list under sorted insertion — worst case O(n) per op. Production code always uses a self-balancing variant (Red-Black, AVL, B-tree). Java's `TreeMap` uses Red-Black because it tolerates more imbalance per rotation than AVL, giving faster writes; AVL wins on read-heavy workloads.

Common traps

Using a plain BST for unsorted input without noticing the adversarial case
Deleting a node with two children without the predecessor / successor swap

Follow-up questions

? Why Red-Black over AVL in most stdlibs?
? How do B-trees trade node fan-out for fewer disk seeks?

Patterns that use this:Depth-First Search

Min-Heap

Senior insight

Binary heaps are stored as arrays: index i has children 2i+1 and 2i+2. That's why the constant factor is tiny and the structure fits in cache. For Top-K problems, a size-K heap beats a full sort at O(n log k) — mentioning this out loud signals seniority.

Common traps

Forgetting Python's `heapq` is a min-heap only — invert signs for max-heap behavior
Using a heap to find the median of a stream with just one heap (two heaps are required)

Follow-up questions

? Implement a priority queue with custom keys
? Streaming median: why two heaps and how do you keep them balanced?

Patterns that use this:Top-K / Heap

Max-Heap

Patterns that use this:Top-K / Heap

Hash-Table

Senior insight

Amortized O(1), but the worst case is O(n) under collisions or adversarial input — hash-flooding DoS attacks exploit this, which is why runtimes use randomized hash seeds. Resize is O(n) and stops the world: in latency-sensitive code, pre-size with an expected capacity.

Common traps

Using as an unbounded cache — memory grows without bound (see LRU / LFU)
Mutating a key after insertion — the entry becomes unreachable
Iteration order is not insertion order in older languages (Python 3.7+ preserves it; Go randomizes it intentionally)

Follow-up questions

? Implement an LRU cache on top of a hash map + doubly-linked list
? Open addressing vs separate chaining — which is faster and when?
? What is hash flooding and how does SipHash mitigate it?

Patterns that use this:Sliding Window

Graph

Senior insight

Representation choice dominates complexity. Adjacency list is O(V + E) space — right for sparse graphs. Adjacency matrix is O(V²) space with O(1) edge-existence checks — right for dense graphs or when you're doing many edge queries.

Common traps

Using BFS on a weighted graph for shortest path — it's wrong; use Dijkstra
Forgetting that undirected edges must be added in both directions in an adjacency list

Follow-up questions

? When does Bellman-Ford beat Dijkstra?
? Detect a cycle in a directed vs undirected graph — different approaches, why?

Patterns that use this:Breadth-First Search, Depth-First Search, Topological Sort