~/learning/programming/data-structures
Data Structures
10 notes·updated
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 represent sequences of text; their encoding and indexing behavior depend on the language.
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 | Depends on encoding and operation | Text representation varies by language | Text manipulation |
| Stacks | O(1) push/pop | LIFO | Undo, recursion, DFS |
| Queues | O(1) enqueue/dequeue | FIFO | BFS, buffering |
| Trees | O(log n) balanced BST; O(n) worst case without balancing | Hierarchical | Sorted data, hierarchies |
| Heaps | O(1) find min/max | Complete binary tree | Priority queues |
| Graphs | Depends on representation and operation | Nodes + edges | Networks, pathfinding |
| Hash Tables | O(1) average | Key-value | Fast lookups |
| Sets/Maps | O(1) average | Unique elements | Membership, associations |