Welcome to the Data Structures Reference Guide! This repository just a personal notes serves as a foundational overview of the most common data structures used in computer science and software engineering. Whether you are implementing them from scratch in C++ or Java, or just brushing up on algorithm optimization, this guide breaks down the essentials.
When evaluating data structures, we use Big O Notation to describe the performance or complexity of an algorithm.
- Time Complexity: How long an operation takes as the dataset grows.
- Space Complexity: How much memory an operation uses as the dataset grows.
- Common Complexities: O(1) [Constant], O(log n) [Logarithmic], O(n) [Linear], O(n log n) [Log-linear], O(n^2) [Quadratic].
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together, making it easy to calculate the position of each element by simply adding an offset to a base value.
- Use Cases: Storing tabular data, implementing matrices, lookup tables.
- Time Complexity:
- Access: O(1)
- Search: O(n)
- Insertion/Deletion (at end): O(1)
- Insertion/Deletion (in middle): O(n)
A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element (node) points to the next.
- Types: Singly Linked List, Doubly Linked List, Circular Linked List.
- Use Cases: Dynamic memory allocation, implementing stacks and queues, playlist navigation.
- Time Complexity:
- Access/Search: O(n)
- Insertion/Deletion (at known node): O(1)
A stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO (Last In First Out).
- Use Cases: Undo mechanisms in text editors, reversing a word, parsing expressions, recursive function call management.
- Time Complexity:
- Push (Insert): O(1)
- Pop (Remove): O(1)
- Peek/Top: O(1)
A queue is a linear structure that follows the FIFO (First In First Out) principle. Items are added at the rear and removed from the front.
- Types: Simple Queue, Circular Queue, Priority Queue, Deque (Double Ended Queue).
- Use Cases: Task scheduling, breadth-first search (BFS) algorithms, handling asynchronous requests.
- Time Complexity:
- Enqueue (Insert): O(1)
- Dequeue (Remove): O(1)
Hash tables (or Hash Maps) store elements in key-value pairs. They use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
- Use Cases: Database indexing, caching, password verification, fast data lookups.
- Time Complexity (Average Case):
- Search: O(1)
- Insertion: O(1)
- Deletion: O(1)
- (Note: Worst-case is O(n) if there are many hash collisions)
A tree is a hierarchical data structure consisting of nodes connected by edges. The top node is the root, and nodes with no children are leaves.
[Image of Binary Search Tree data structure]
- Types: * Binary Tree: Each node has at most two children.
- Binary Search Tree (BST): Left child is smaller than the parent; right child is larger. Excellent for searching and sorting.
- Balanced Trees (AVL, Red-Black): Maintain O(log n) height.
- Tree Traversals: In-order, Pre-order, Post-order.
- Use Cases: Hierarchical data (file systems), fast searching/sorting, routing algorithms.
- Time Complexity (BST Average Case):
- Access/Search: O(log n)
- Insertion/Deletion: O(log n)
A graph consists of a finite set of vertices (or nodes) and a set of edges connecting these vertices.
- Types: Directed, Undirected, Weighted, Unweighted.
- Representations: Adjacency Matrix, Adjacency List.
- Use Cases: Social networks, GPS navigation (shortest path), recommendation engines.
- Time Complexity: Varies heavily based on the representation and the specific algorithm used (e.g., Dijkstra's, BFS, DFS).
Note: The "best" data structure always depends on the specific problem you are trying to solve. Consider the tradeoffs between memory usage and execution speed when designing your systems.