A data structures cheat sheet can serve as a quick reference for understanding and implementing different data structures. Here’s a cheat sheet covering some commonly used data structures:
Arrays
- Definition:
- Collection of elements stored in contiguous memory locations.
- Operations:
- Access:
arr[index] - Insertion:
arr.push(element) - Deletion:
arr.splice(index, 1)
- Access:
Linked Lists
- Definition:
- Series of nodes where each node points to the next one.
- Operations:
- Insertion:
insert(node, value) - Deletion:
delete(node) - Traversal:
while (node) { ... }
- Insertion:
Stacks
- Definition:
- Linear data structure that follows the Last In, First Out (LIFO) principle.
- Operations:
- Push:
stack.push(element) - Pop:
stack.pop() - Peek:
stack[stack.length - 1]
- Push:
Queues
- Definition:
- Linear data structure that follows the First In, First Out (FIFO) principle.
- Operations:
- Enqueue:
queue.push(element) - Dequeue:
queue.shift() - Peek:
queue[0]
- Enqueue:
Trees
- Binary Tree:
- Tree structure where each node has at most two children.
- Binary Search Tree (BST):
- Binary tree with left child smaller and right child greater.
- Operations:
- Insertion:
insert(node, value) - Deletion:
delete(node, value) - Traversal: Inorder, Preorder, Postorder
- Insertion:
Hash Tables
- Definition:
- Data structure that maps keys to values.
- Operations:
- Insertion:
hashTable[key] = value - Access:
value = hashTable[key] - Deletion:
delete hashTable[key]
- Insertion:
Heaps
- Min Heap:
- Complete binary tree where the parent is smaller than its children.
- Max Heap:
- Complete binary tree where the parent is larger than its children.
- Operations:
- Insertion:
heap.push(element) - Extraction:
root = heap.pop()
- Insertion:
Graphs
- Definition:
- Collection of nodes (vertices) and edges.
- Types:
- Directed Graph
- Undirected Graph
- Representations:
- Adjacency Matrix
- Adjacency List
Trie
- Definition:
- Tree-like data structure used to store a dynamic set of strings.
- Operations:
- Insertion:
insert(key) - Search:
search(key) - Prefix Search:
startsWith(prefix)
- Insertion:
Disjoint Set (Union-Find)
- Definition:
- Data structure that keeps track of a set of elements partitioned into disjoint sets.
- Operations:
- Union:
union(x, y) - Find:
find(x)
- Union:
This cheat sheet provides a quick overview of various data structures and their basic operations. Each data structure has its use cases and trade-offs, so understanding them helps in selecting the appropriate one for specific scenarios.