Data Structures Cheat Sheet

Summarizes core linear and non-linear data structures, their time complexities, and example implementations of stacks, queues, and hash tables.

2 PagesBeginnerMar 28, 2026

Linear Structures

Structures that store elements in a sequential order.

Array- Contiguous, fixed or dynamic-size collection with O(1) index access, O(n) insertion/deletion in the middle
Linked List- Nodes with pointers to the next (and optionally previous) node; O(1) insertion/deletion at a known position, O(n) access
Stack- LIFO structure with O(1) push/pop; used for undo history, call stacks, and expression evaluation
Queue- FIFO structure with O(1) enqueue/dequeue; used for task scheduling and BFS traversal
Deque- Double-ended queue supporting O(1) insertion/removal at both ends

Trees, Graphs & Hashing

Non-linear structures for hierarchical and connected data.

Binary Tree- Each node has at most two children; traversed via in-order, pre-order, post-order, or level-order
Binary Search Tree (BST)- Left subtree < node < right subtree; O(log n) search/insert/delete when balanced, O(n) worst case
Heap- Complete binary tree maintaining the min-heap or max-heap property; O(log n) insert/extract, O(1) peek
Hash Table- Maps keys to values via a hash function; average O(1) lookup/insert, O(n) worst case with collisions
Graph- Vertices connected by edges; represented as an adjacency list (space-efficient) or adjacency matrix (fast edge lookup)
Trie- Tree structure for storing strings by shared prefixes; O(m) lookup where m is the key length

Stack & Queue in Practice

Common Python implementations with O(1) operations.

python

# Stack using a Python liststack = []stack.append(1)   # pushstack.append(2)stack.pop()        # pop -> 2 (LIFO)# Queue using collections.deque (O(1) at both ends)from collections import dequequeue = deque()queue.append(1)     # enqueuequeue.append(2)queue.popleft()      # dequeue -> 1 (FIFO)

Hash Table & Set Usage

Counting and membership checks with O(1) average time.

python

# Hash table (dict) usagecounts = {}for word in ["a", "b", "a", "c", "b", "a"]:    counts[word] = counts.get(word, 0) + 1# {'a': 3, 'b': 2, 'c': 1}# Using a set for O(1) average membership checksseen = set()seen.add(5)5 in seen   # => True

Pro Tip

Pick the data structure by which operation dominates your workload — a hash table wins for lookups, but if you need sorted order or range queries, a balanced BST or sorted array beats it despite slower average-case lookup.

Was this cheat sheet helpful?

Algorithms & Big-O Cheat Sheet

Recursion Cheat Sheet