Data Structures Cheat Sheet

Updated 2026-04-29

Next Topic: Descriptive Statistics Cheat Sheet

Data structures are the fundamental building blocks of computer science—organized formats for storing, accessing, and manipulating data in memory. From simple arrays to complex self-balancing trees, they determine how efficiently programs execute. The right structure can reduce an $O(n^2)$ algorithm to $O(\log n)$ —turning a sluggish system into a responsive one. Understanding data structures is not just about memorization; it's about recognizing trade-offs between time, space, and complexity for the problem at hand. When you choose a hash table over a binary search tree, you're balancing constant-time lookups against memory overhead and lack of ordering.

What This Cheat Sheet Covers

This topic spans 16 focused tables and 108 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Linear Structures — Arrays and ListsTable 2: Stacks and QueuesTable 3: Hash-Based StructuresTable 4: Binary Trees — Basic FormsTable 5: Self-Balancing Binary Search TreesTable 6: B-Trees and VariantsTable 7: HeapsTable 8: Tries and String StructuresTable 9: Advanced Tree StructuresTable 10: Graph RepresentationsTable 11: Disjoint Set StructuresTable 12: Probabilistic Data StructuresTable 13: Specialized Tree VariantsTable 14: Cache and Memory StructuresTable 15: Persistent Data StructuresTable 16: Time Complexity Summary — Common Operations

Table 1: Linear Structures — Arrays and Lists

Type	Example	Description
Array	`arr = [10, 20, 30, 40]` `arr[2] → 30`	• Contiguous block of memory storing fixed-size elements indexed from 0 • $O(1)$ access by index, but $O(n)$ insertion/deletion unless at the end.
Dynamic Array	`list = []` `list.append(5)`	• Resizable array that automatically grows when capacity is exceeded • amortized $O(1)$ append by doubling capacity when full.
Singly Linked List	`1 → 2 → 3 → null`	• Each node contains data and a pointer to the next node • $O(1)$ insertion/deletion at head, but $O(n)$ access to arbitrary elements.
Doubly Linked List	`null ← 1 ⇄ 2 ⇄ 3 → null`	• Nodes have pointers to both next and previous nodes • enables $O(1)$ bidirectional traversal and efficient removal without a predecessor pointer.

Table 1: Linear Structures — Arrays and Lists

Type	Example	Description
Array	`arr = [10, 20, 30, 40]` `arr[2] → 30`	• Contiguous block of memory storing fixed-size elements indexed from 0 • $O(1)$ access by index, but $O(n)$ insertion/deletion unless at the end.
Dynamic Array	`list = []` `list.append(5)`	• Resizable array that automatically grows when capacity is exceeded • amortized $O(1)$ append by doubling capacity when full.
Singly Linked List	`1 → 2 → 3 → null`	• Each node contains data and a pointer to the next node • $O(1)$ insertion/deletion at head, but $O(n)$ access to arbitrary elements.
Doubly Linked List	`null ← 1 ⇄ 2 ⇄ 3 → null`	• Nodes have pointers to both next and previous nodes • enables $O(1)$ bidirectional traversal and efficient removal without a predecessor pointer.