Data Structures and Algorithms
Documentation
1. Introduction
1.1 What are Data Structures?
A data structure is a way to organize and store data efficiently for various operations such as
retrieval, insertion, deletion, and traversal.
Examples:
● Linear Structures: Arrays, Linked Lists, Stacks, Queues.
● Non-Linear Structures: Trees, Graphs.
1.2 Importance of Data Structures
● Efficient data management in software systems.
● Optimization of time and space.
● Foundation for algorithms, databases, and system design.
2. Basic Data Structures
2.1 Arrays
● Definition: A fixed-size collection of elements of the same type stored in contiguous
memory locations.
● Operations: Access (O(1)), Search (O(n)), Insertion/Deletion (O(n)).
C# Example:
csharp
Copy code
int[] array = { 10, 20, 30, 40, 50 };
Console.WriteLine(array[2]); // Output: 30
Java Example:
java
Copy code
int[] array = { 10, 20, 30, 40, 50 };
System.out.println(array[2]); // Output: 30
2.2 Linked Lists
● Definition: A series of connected nodes where each node contains data and a reference
(pointer) to the next node.
● Types: Singly Linked List, Doubly Linked List, Circular Linked List.
● Operations: Search (O(n)), Insertion/Deletion at head (O(1)).
C# Example (Singly Linked List):
csharp
Copy code
public class Node {
public int Data;
public Node Next;
}
Node head = new Node { Data = 1, Next = null };
Node second = new Node { Data = 2, Next = null };
head.Next = second;
Java Example (Singly Linked List):
java
Copy code
class Node {
int data;
Node next;
}
Node head = new Node();
head.data = 1;
head.next = new Node();
head.next.data = 2;
2.3 Stacks
● Definition: A LIFO (Last In, First Out) data structure.
● Operations: Push (O(1)), Pop (O(1)), Peek (O(1)).
C# Example (Using Stack):
csharp
Copy code
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
Console.WriteLine(stack.Pop()); // Output: 2
Java Example (Using Stack):
java
Copy code
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // Output: 2
2.4 Queues
● Definition: A FIFO (First In, First Out) data structure.
● Operations: Enqueue (O(1)), Dequeue (O(1)).
C# Example (Using Queue):
csharp
Copy code
Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
Console.WriteLine(queue.Dequeue()); // Output: 1
Java Example (Using Queue):
java
Copy code
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
System.out.println(queue.poll()); // Output: 1
2.5 Hash Tables
● Definition: A data structure that maps keys to values using a hash function.
● Operations: Search, Insert, Delete (average O(1), worst O(n)).
C# Example:
csharp
Copy code
Dictionary<int, string> hashTable = new Dictionary<int, string>();
hashTable[1] = "One";
Console.WriteLine(hashTable[1]); // Output: One
Java Example:
java
Copy code
HashMap<Integer, String> hashTable = new HashMap<>();
hashTable.put(1, "One");
System.out.println(hashTable.get(1)); // Output: One
3. Algorithmic Complexity
3.1 Time vs Space Complexity
● Time Complexity: The amount of time an algorithm takes to complete as a function of
input size.
● Space Complexity: The amount of memory an algorithm uses.
3.2 How to Calculate Complexity
Analyze the number of iterations or operations the algorithm performs based on the size of the
input.
Example (Time Complexity):
● Summing an array:
○ Loop executes n times → O(n).
Example (Space Complexity):
● Storing an array of size n → O(n).
3.3 Common Runtimes
● Constant (O(1)): Accessing an array index.
● Logarithmic (O(log n)): Binary search.
● Linear (O(n)): Traversing a list.
● Polynomial (O(n^k)): Nested loops.
● Exponential (O(2^n)): Recursive combinations.
● Factorial (O(n!)): Permutations.
3.4 Asymptotic Notations
● Big-O (Worst case): Upper bound.
● Big-θ (Average case): Tight bound.
● Big-Ω (Best case): Lower bound.
4. Sorting Algorithms
● Detailed breakdown with pseudocode and examples in C# and Java for:
○ Bubble Sort: Compare adjacent elements.
○ Merge Sort: Divide and conquer.
○ Quick Sort: Partition-based sorting.
5. Search Algorithms
● Linear Search: Sequentially checks elements.
● Binary Search: Divides and conquers a sorted array.
C# Example (Binary Search):
csharp
Copy code
int BinarySearch(int[] array, int target) {
int left = 0, right = array.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return mid;
if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Java Example (Binary Search):
java
Copy code
int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return mid;
if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
6. Tree Data Structures
6.1 Binary Trees
● Binary Search Trees (BST): Nodes arranged such that left ≤ root ≤ right.
Tree Traversals:
● In-Order (Left, Root, Right):
● Pre-Order (Root, Left, Right):
● Post-Order (Left, Right, Root):
7. Graph Data Structures
● Representation: Adjacency Matrix, Adjacency List.
● Algorithms:
○ BFS, DFS.
○ Shortest Path: Dijkstra's Algorithm, Bellman-Ford.
○ MST: Prim's and Kruskal’s Algorithms.
8. Advanced Data Structures
● Trie: Prefix-based searching.
● Segment Tree: Range queries.
● Fenwick Tree: Efficient cumulative sum.
9. Problem Solving Techniques
● Divide and Conquer: E.g., Merge Sort.
● Dynamic Programming: E.g., Fibonacci.
● Greedy Algorithms: E.g., Huffman Coding.
