Data structures and algorithms are fundamental concepts in computer science that form the building blocks for efficient problem solving and software development. A solid understanding of DSA is crucial for writing optimized code, improving program performance, and excelling in technical interviews.
This document provides an in-depth overview of common data structures, key algorithms, time complexity analysis, and other important DSA concepts. We'll explore the theoretical foundations as well as practical implementations and applications.
Data structures are ways of organizing and storing data so that it can be accessed and worked with efficiently. They define the relationship between data, and the operations that can be performed on the data.
An array is a collection of elements stored at contiguous memory locations. It is the simplest and most widely used data structure.
Key characteristics:
- Fixed size (in most programming languages)
- Elements are accessed using an index
- Contiguous memory allocation
Operations and time complexities:
- Access: O(1)
- Search: O(n)
- Insertion: O(n)
- Deletion: O(n)
A linked list is a linear data structure where elements are stored in nodes. Each node contains a data field and a reference (link) to the next node in the sequence.
Types:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Operations and time complexities:
- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Deletion: O(1)
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element inserted into the stack is the first one to be removed.
Key operations:
- Push: Add an element to the top
- Pop: Remove the top element
- Peek: View the top element without removing it
Time complexity for all operations: O(1)
A queue is a linear structure which follows the First-In-First-Out (FIFO) principle. The first element inserted into the queue is the first one to be removed.
Key operations:
- Enqueue: Add an element to the rear
- Dequeue: Remove the front element
- Front: Get the front element
Time complexity for all operations: O(1)
A tree is a hierarchical data structure consisting of nodes connected by edges. It has a root node and subtrees of children with a parent node.
Types:
- Binary Tree
- Binary Search Tree (BST)
- AVL Tree
- Red-Black Tree
- B-Tree
Operations and time complexities (for a balanced BST):
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)
A graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph.
Types:
- Directed Graph
- Undirected Graph
- Weighted Graph
Common representations:
- Adjacency Matrix
- Adjacency List
A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
Time complexity (average case):
- Search: O(1)
- Insertion: O(1)
- Deletion: O(1)
An algorithm is a step-by-step procedure or formula for solving a problem. It is the foundation for all computer programming and is essential for efficient problem-solving.
Sorting algorithms arrange elements in a specific order (usually ascending or descending).
-
Bubble Sort
- Time complexity: O(n^2)
- Space complexity: O(1)
-
Selection Sort
- Time complexity: O(n^2)
- Space complexity: O(1)
-
Insertion Sort
- Time complexity: O(n^2)
- Space complexity: O(1)
-
Merge Sort
- Time complexity: O(n log n)
- Space complexity: O(n)
-
Quick Sort
- Time complexity: O(n log n) average, O(n^2) worst case
- Space complexity: O(log n)
-
Heap Sort
- Time complexity: O(n log n)
- Space complexity: O(1)
Sorting Algorithms Comparison
Searching algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
-
Linear Search
- Time complexity: O(n)
-
Binary Search
- Time complexity: O(log n)
-
Depth-First Search (DFS)
- Time complexity: O(V + E) where V is the number of vertices and E is the number of edges
-
Breadth-First Search (BFS)
- Time complexity: O(V + E)
-
Dijkstra's Algorithm (Shortest Path)
- Time complexity: O((V + E) log V) with binary heap
-
Bellman-Ford Algorithm (Shortest Path with negative edges)
- Time complexity: O(VE)
-
Floyd-Warshall Algorithm (All-pairs shortest path)
- Time complexity: O(V^3)
-
Kruskal's Algorithm (Minimum Spanning Tree)
- Time complexity: O(E log E) or O(E log V)
-
Prim's Algorithm (Minimum Spanning Tree)
- Time complexity: O((V + E) log V) with binary heap
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
Examples:
- Fibonacci Series
- Knapsack Problem
- Longest Common Subsequence
- Matrix Chain Multiplication
A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
Examples:
- Fractional Knapsack Problem
- Huffman Coding
- Prim's and Kruskal's algorithms for Minimum Spanning Tree
Time complexity is a way to represent the amount of time required by the program to run till its completion. It's generally calculated as a function of input size.
Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.
Common time complexities:
- O(1): Constant time
- O(log n): Logarithmic time
- O(n): Linear time
- O(n log n): Linearithmic time
- O(n^2): Quadratic time
- O(2^n): Exponential time
Space complexity is a measure of how much working storage an algorithm needs.
Balanced trees are a type of tree data structure where the height of the left and right subtrees of every node differs by at most one.
Examples:
- AVL Trees
- Red-Black Trees
- B-Trees
A trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.
A Segment Tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array.
A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.