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. There are many different types of data structures, generally built upon simpler primitive data types.
These notes are meant to be a quick reference for the most common data structures and their use cases. They are not meant to be a comprehensive guide, but rather a starting point for further exploration.
It is recommended to go through the notes in the order they are presented, as the concepts build on each other, even if you are already familiar with them.
Arrays
Arrays are the simplest and most widely used data structure. They are used to store a collection of data, but they are not suitable for storing large amounts of data. Arrays are best used for small collections of data, or when the number of items is known in advance.
Strings
Strings are a collection of characters, and are used to represent text. They are a special type of array, and are used to store and manipulate text data. Strings are immutable, meaning that once they are created, they cannot be changed. They are best used for storing and manipulating small amounts of text data.
Linked Lists
Linked lists are a collection of nodes, where each node contains a value and a reference to the next node in the list. They are used to store and manipulate data, and are best used for storing and manipulating large amounts of data.
Stacks
Stacks are a collection of elements, where elements are added and removed from the top of the stack. They are used to store and manipulate data, and are best used for storing and manipulating data in a last-in, first-out (LIFO) manner.
Queues
Queues are a collection of elements, where elements are added to the back of the queue and removed from the front of the queue. They are used to store and manipulate data, and are best used for storing and manipulating data in a first-in, first-out (FIFO) manner.
Trees
Trees are a collection of nodes, where each node contains a value and a reference to its children. They are used to store and manipulate data, and are best used for storing and manipulating hierarchical data.
Graphs
Graphs are a collection of nodes, where each node contains a value and a reference to its neighbors. They are used to store and manipulate data, and are best used for storing and manipulating data with complex relationships.
Hash Tables
Hash tables are a collection of key-value pairs, where each key is unique. They are used to store and manipulate data, and are best used for storing and manipulating data with fast lookups.
Sets and Maps
Sets and maps are collections of elements, where each element is unique. They are used to store and manipulate data, and are best used for storing and manipulating data with unique elements.
Cheatsheet
| Data Structure | Type | Access | Features | Use Cases | Use in Algorithms | Typical Problems |
|---|---|---|---|---|---|---|
| Arrays | Linear | O(1) access, O(n) search | Fixed size, contiguous memory | Fast access, known number of elements | Efficient access by index, static datasets, sorting, simple lookups | Binary search, array rotation, prefix sum |
| Linked Lists | Linear | O(n) access and search | Dynamic size, non-contiguous memory | Frequent insertions/deletions | Dynamic insertion/deletion, implementing stacks/queues | Reverse linked list, merge sorted lists, cycle detection |
| Strings | Linear (array of characters) | O(1) access, O(n) search/modify | Immutable (in some languages) | Text manipulation | String manipulation, pattern matching, substrings | Palindromes, anagrams, string transformations |
| Stacks | LIFO (Last-In-First-Out) | O(1) for push/pop | Top accessible only | Undo operations, recursion | Last-in-first-out operations, backtracking, depth-first search, syntax parsing | Valid parentheses, reverse Polish notation, next greater element |
| Queues | FIFO (First-In-First-Out) | O(1) for enqueue/dequeue | Front and rear operations | Order processing, breadth-first search | First-in-first-out operations, breadth-first search, caching, buffering | Level order traversal in trees, sliding window problems, queue reconstruction by height |
| Trees | Hierarchical | O(log n) for BST, O(n) otherwise | Branching structure, parent-children relationship | Hierarchical data, efficient searches | Hierarchical data, sorted data, recursive solutions | Tree traversal, BST operations, segment trees |
| Heaps | Tree-based (Min/Max) | O(1) find min/max, O(log n) insert/delete | Complete binary tree, heap property | Priority queues, scheduling | Priority queuing, efficient extraction of min/max elements, heap sort | Kth largest element, merge k sorted lists, median finder |
| Graphs | Network | O(V) or O(V^2) (depending on representation) | Nodes (vertices), edges (connections) | Network routing, social networks | Network modeling, pathfinding, relational problems | Graph traversal (DFS, BFS), shortest path, cycle detection |
| Hash Tables | Key-Value pairs | O(1) average access/search/insert/delete | Hash function, collision handling | Quick lookups, unique data representation | Fast lookups, data indexing, frequency counting, unique item tracking | Two sum, group anagrams, substring concatenation |
| Sets and Maps | Collection of unique elements (Set) and key-value pairs (Map) | O(1) average for most operations | Based on hash tables or trees | Checking membership (Set), associative data storage (Map) | Checking for item uniqueness, mapping relationships, count-based problems | Duplicate detection, longest substring without repeating characters, map-based grouping |