Data Structures & Algorithms
Master the fundamentals of efficient programming
🚀 What are Data Structures & Algorithms?
Data Structures are ways to organize and store data efficiently. Algorithms are step-by-step procedures to solve problems. Together, they form the foundation of computer science and efficient programming!
# Simple example: Finding the maximum number
numbers = [3, 7, 2, 9, 1, 5]
# Algorithm: Linear search for maximum
max_num = numbers[0]
for num in numbers:
if num > max_num:
max_num = num
print(f"Maximum number: {max_num}") # Output: 9
Efficient
Solutions
Problem
Solving
Optimal
Performance
Why Learn Data Structures & Algorithms?
Performance
Write faster, more efficient code
Speed
Memory
Problem Solving
Develop logical thinking skills
Logic
Analysis
Career Growth
Essential for technical interviews
Interviews
Jobs
System Design
Build scalable applications
Architecture
Scale
Common Data Structures
Linear Structures
-
Arrays- Fixed size collections -
Lists- Dynamic arrays -
Stacks- LIFO (Last In, First Out) -
Queues- FIFO (First In, First Out) -
Linked Lists- Node-based chains
Non-Linear Structures
-
Trees- Hierarchical data -
Binary Trees- Two children max -
BST- Binary Search Trees -
AVL Trees- Self-balancing -
Graphs- Connected nodes
Hash-Based
-
Hash Tables- Key-value pairs -
Hash Maps- Dictionary-like -
Hash Sets- Unique elements -
Bloom Filters- Probabilistic
Specialized
-
Heaps- Priority queues -
Tries- Prefix trees -
Segment Trees- Range queries -
Disjoint Sets- Union-find
Algorithm Categories
Searching Algorithms
🔹Linear Search - Check every element
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# Example usage
numbers = [3, 7, 2, 9, 1, 5]
result = linear_search(numbers, 9)
print(f"Found at index: {result}") # Output: 3🔹Binary Search - Divide and conquer (sorted arrays)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage
sorted_numbers = [1, 2, 3, 5, 7, 9]
result = binary_search(sorted_numbers, 5)
print(f"Found at index: {result}") # Output: 3Sorting Algorithms
Basic Sorting Methods
🔹Bubble Sort - Compare adjacent elements
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Example
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers.copy())
print(f"Sorted: {sorted_numbers}") # [11, 12, 22, 25, 34, 64, 90]🔹Quick Sort - Divide and conquer
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = quick_sort(numbers)
print(f"Sorted: {sorted_numbers}") # [11, 12, 22, 25, 34, 64, 90]Understanding Time Complexity
Time complexity measures how algorithm performance changes with input size:
Big O Notation - Common Complexities
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)
Constant
Logarithmic
Linear
Linearithmic
Quadratic
Exponential
Time Complexity Examples
# O(1) - Constant time
def get_first_element(arr):
return arr[0] if arr else None
# O(n) - Linear time
def find_max(arr):
max_val = arr[0]
for num in arr: # Visits each element once
if num > max_val:
max_val = num
return max_val
# O(n²) - Quadratic time
def bubble_sort_example(arr):
n = len(arr)
for i in range(n): # Outer loop: n times
for j in range(n-1): # Inner loop: n times
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# O(log n) - Logarithmic time
def binary_search_example(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # Halves search space each time
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1