Data Structures Cheat Sheet
Data structures are essential components used to organize, manage, and store data efficiently. This cheat sheet provides an overview of common data structures, their properties, and use cases.
Arrays
Definition: A collection of elements identified by index or key.
Characteristics:
Fixed size (static arrays) or dynamic size (dynamic arrays).
Elements stored in contiguous memory locations.
Operations:
Access:
O(1)Search:
O(n)Insertion:
O(n)(worst case)Deletion:
O(n)(worst case)
Use Cases: Storing collections of data, implementing other data structures like heaps and hash tables.
Linked Lists
Definition: A collection of nodes where each node contains data and a reference (link) to the next node.
Types: Singly linked list, doubly linked list, circular linked list.
Operations:
Access:
O(n)Search:
O(n)Insertion:
O(1)(at head)Deletion:
O(1)(at head)
Use Cases: Dynamic memory allocation, implementing stacks and queues, scenarios requiring frequent insertions and deletions.
Stacks
Definition: A linear data structure following Last In, First Out (LIFO) principle.
Operations:
Push:
O(1)Pop:
O(1)Peek/Top:
O(1)
Use Cases: Expression evaluation, syntax parsing, undo mechanisms in software.
Queues
Definition: A linear data structure following First In, First Out (FIFO) principle.
Types: Simple queue, circular queue, priority queue, deque (double-ended queue).
Operations:
Enqueue:
O(1)Dequeue:
O(1)Peek/Front:
O(1)
Use Cases: Scheduling algorithms, breadth-first search (BFS) in graphs, buffering data streams.
Trees
Definition: A hierarchical data structure consisting of nodes with a parent-child relationship.
Types: Binary tree, binary search tree (BST), AVL tree, red-black tree, B-tree.
Operations:
Search:
O(log n)(BST)Insertion:
O(log n)(BST)Deletion:
O(log n)(BST)Traversal:
O(n)(preorder, inorder, postorder)
Use Cases: Hierarchical data representation, database indexing (B-trees), sorting and searching algorithms.
Heaps
Definition: A specialized tree-based data structure satisfying the heap property (max-heap or min-heap).
Operations:
Insert:
O(log n)Delete (root):
O(log n)Peek (root):
O(1)
Use Cases: Priority queues, heap sort algorithm, graph algorithms like Dijkstra’s shortest path.
Hash Tables
Definition: A data structure that maps keys to values using a hash function.
Operations:
Insert:
O(1)(average case)Search:
O(1)(average case)Delete:
O(1)(average case)
Use Cases: Fast data retrieval, implementing associative arrays, caching, databases.
Graphs
Definition: A collection of vertices (nodes) connected by edges.
Types: Directed graph (digraph), undirected graph, weighted graph, unweighted graph.
Operations:
Add Vertex:
O(1)Add Edge:
O(1)Search:
O(V + E)(BFS/DFS)
Use Cases: Network routing, social networks, dependency graphs, pathfinding algorithms.
Common Operations and Complexities
+----------------+----------+----------+-----------+----------+----------------------------------------------------------+
| Data Structure | Access | Search | Insertion | Deletion | Use Cases |
+----------------+----------+----------+-----------+----------+----------------------------------------------------------+
| Array | O(1) | O(n) | O(n) | O(n) | Static data storage, lookup tables |
| Linked List | O(n) | O(n) | O(1) | O(1) | Dynamic memory allocation, frequent insertions/deletions |
| Stack | O(n) | O(n) | O(1) | O(1) | Function call management, backtracking algorithms |
| Queue | O(n) | O(n) | O(1) | O(1) | Task scheduling, BFS |
| Binary Tree | O(log n) | O(log n) | O(log n) | O(log n) | Hierarchical data, sorted data |
| Heap | O(n) | O(log n) | O(log n) | O(log n) | Priority queues, heap sort |
| Hash Table | O(n) | O(1) | O(1) | O(1) | Fast lookups, indexing |
| Graph | O(V+E) | O(V+E) | O(1) | O(1) | Network modeling, pathfinding |
+----------------+----------+----------+-----------+----------+----------------------------------------------------------+
Summary
Arrays: Best for fixed-size collections with fast access.
Linked Lists: Ideal for dynamic collections with frequent insertions/deletions.
Stacks and Queues: Useful for LIFO and FIFO operations, respectively.
Trees: Efficient for hierarchical data and sorted operations.
Heaps: Optimal for priority-based tasks.
Hash Tables: Excellent for fast key-value lookups.
Graphs: Essential for representing networks and connections.
This cheat sheet provides a high-level overview of common data structures, their properties, and use cases. For detailed implementations and more advanced data structures, refer to specific programming resources and documentation.