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.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Linear Structures — Arrays and Lists
The most fundamental way to store a sequence is in a line, and the whole trade-off here lives in one question: contiguous memory or chained pointers? Arrays give you instant indexed access but pay for inserts and resizes, while linked lists flip that — cheap insertion and deletion at the cost of $O(n)$ random access. The variants below tune that balance for specific needs, from ring buffers for fixed-size streaming queues to skip lists that fake balanced-tree search speed with nothing but stacked linked lists.
| Type | Example | Description |
|---|---|---|
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. | |
list = []list.append(5) | • Resizable array that automatically grows when capacity is exceeded • amortized $O(1)$ append by doubling capacity when full. | |
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. | |
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. |