Data Structures

Data structures are a way of organizing and storing data so that they can be accessed and worked with efficiently. They define the relationship between the data, and the operations that can be performed on the data.

These notes are meant to be a quick reference for the most common data structures and their use cases.

Overview

Arrays

Arrays are the simplest and most widely used data structure. They store a collection of elements with O(1) access by index.

Strings

Strings are a collection of characters used to represent text. They are a special type of array, often immutable.

Linked Lists

Linked lists are a collection of nodes, where each node contains a value and a reference to the next node.

Stacks

Stacks follow LIFO (Last-In-First-Out) order. Elements are added and removed from the top.

Queues

Queues follow FIFO (First-In-First-Out) order. Elements are added to the back and removed from the front.

Trees

Trees are hierarchical structures where each node contains a value and references to its children.

Heaps

Heaps are complete binary trees that maintain a heap property, enabling efficient priority queue operations.

Graphs

Graphs are nodes with edges connecting them, used for modeling complex relationships.

Hash Tables

Hash tables store key-value pairs with O(1) average access time.

Sets and Maps

Collections of unique elements (Set) and key-value pairs (Map).

Cheatsheet

Data Structure	Access	Features	Use Cases
Arrays	O(1)	Fixed size, contiguous memory	Fast access, known size
Linked Lists	O(n)	Dynamic size	Frequent insertions/deletions
Strings	O(1)	Immutable (often)	Text manipulation
Stacks	O(1) push/pop	LIFO	Undo, recursion, DFS
Queues	O(1) enqueue/dequeue	FIFO	BFS, buffering
Trees	O(log n) BST	Hierarchical	Sorted data, hierarchies
Heaps	O(1) find min/max	Complete binary tree	Priority queues
Graphs	O(V) or O(V²)	Nodes + edges	Networks, pathfinding
Hash Tables	O(1) average	Key-value	Fast lookups
Sets/Maps	O(1) average	Unique elements	Membership, associations