Data structures and algorithms in Python, with all topics and sub-topics
Singaraju SaitejaImagine you're organizing your room. Data Structures are like different ways you can organize your stuff (like drawers, shelves, boxes). Algorithms are the step-by-step instructions you follow to do things with your stuff (like finding a specific book, putting away laundry, or cleaning).
Why are DSA important?
Efficiency: They help you write code that runs faster and uses less memory.
Organization: They make your code easier to understand and maintain.
Problem Solving: They give you tools to solve complex problems in a structured way.
Let's break it down into topics and subtopics:
I. Data Structures (Ways to Organize Data)
Basic Data Structures (Building Blocks)
a) Lists (Arrays in other languages):
Simple Explanation: Like a numbered list or a train of connected carriages. You store items in a specific order, and each item has a position (index).
Python Example:
my_list = ["apple", "banana", "cherry"] print(my_list[0]) # Output: apple (accessing item at index 0) my_list.append("date") # Adding an item at the end print(my_list) # Output: ['apple', 'banana', 'cherry', 'date']content_copy download
Use code with caution.Python
Subtopics:
Accessing Elements: Getting an item using its index (like my_list[index]).
Adding/Removing Elements: append(), insert(), remove(), pop().
Searching: Checking if an item is in the list (in keyword, index()).
Slicing: Getting a part of the list (my_list[start:end]).
b) Tuples:
Simple Explanation: Like a list, but you can't change it after you create it (immutable). Think of it like a fixed set of coordinates (x, y).
Python Example:
my_tuple = ("red", "green", "blue") print(my_tuple[1]) # Output: green # my_tuple[0] = "yellow" # This would cause an error (tuples are immutable)content_copy download
Use code with caution.Python
Subtopics:
Immutability: Cannot be modified after creation.
Use Cases: Representing fixed data, returning multiple values from a function.
c) Dictionaries (Hash Maps or Hash Tables in other languages):
Simple Explanation: Like a real-world dictionary. You look up a "word" (key) to find its "definition" (value). Keys must be unique.
Python Example:
my_dict = {"name": "Alice", "age": 30, "city": "New York"} print(my_dict["name"]) # Output: Alice (accessing value using key "name") my_dict["job"] = "Engineer" # Adding a new key-value pair print(my_dict) # Output: {'name': 'Alice', 'age': 30, 'city': 'New York', 'job': 'Engineer'}content_copy download
Use code with caution.Python
Subtopics:
Keys and Values: Understanding key-value pairs.
Accessing Values: Using keys to get values (my_dict[key]).
Adding/Updating/Deleting Entries: my_dict[key] = value, del my_dict[key].
Checking if Key Exists: in keyword ("name" in my_dict).
d) Sets:
Simple Explanation: Like a collection of unique items. Order doesn't matter, and duplicates are automatically removed. Think of a bag of marbles where each marble is unique.
Python Example:
my_set = {"apple", "banana", "apple", "orange"} # Note: "apple" is repeated print(my_set) # Output: {'orange', 'banana', 'apple'} (duplicates removed, order may vary) my_set.add("grape") # Adding an item print(my_set) # Output: {'orange', 'banana', 'apple', 'grape'}content_copy download
Use code with caution.Python
Subtopics:
Uniqueness: Only stores distinct elements.
No Order: Elements are not stored in a specific order.
Set Operations: Union, intersection, difference (like in math sets).
Abstract Data Structures (Building upon Basics)
a) Stacks:
Simple Explanation: Like a stack of plates. You can only add or remove plates from the top. LIFO (Last-In, First-Out).
Analogy: Undo/Redo functionality in applications. The last action you did is the first one you undo.
Python Example (using a list):
stack = [] stack.append("plate 1") # Push onto stack stack.append("plate 2") stack.append("plate 3") print(stack) # Output: ['plate 1', 'plate 2', 'plate 3'] top_plate = stack.pop() # Pop from stack (removes and returns the last item) print(top_plate) # Output: plate 3 print(stack) # Output: ['plate 1', 'plate 2']content_copy download
Use code with caution.Python
Subtopics:
Push: Adding an element to the top.
Pop: Removing and returning the element from the top.
Peek (Top): Looking at the top element without removing it.
IsEmpty: Checking if the stack is empty.
b) Queues:
Simple Explanation: Like a line at a ticket counter. The first person in line is the first one served. FIFO (First-In, First-Out).
Analogy: Waiting in line at a store, printing jobs in a printer queue.
Python Example (using collections.deque for efficiency):
from collections import deque queue = deque() queue.append("person A") # Enqueue (add to the back) queue.append("person B") queue.append("person C") print(queue) # Output: deque(['person A', 'person B', 'person C']) first_person = queue.popleft() # Dequeue (remove and return from the front) print(first_person) # Output: person A print(queue) # Output: deque(['person B', 'person C'])content_copy download
Use code with caution.Python
Subtopics:
Enqueue: Adding an element to the back (rear).
Dequeue: Removing and returning the element from the front.
Peek (Front): Looking at the front element without removing it.
IsEmpty: Checking if the queue is empty.
c) Linked Lists:
Simple Explanation: Like a chain of paperclips. Each paperclip (node) holds a piece of data and points to the next paperclip in the chain. Not stored in contiguous memory like lists.
Analogy: A treasure hunt where each clue leads you to the next location.
Conceptual Python Example (implementation is more involved, but concept is key):
# Imagine nodes like this: node1 = {"data": "apple", "next": node2} node2 = {"data": "banana", "next": node3} node3 = {"data": "cherry", "next": None} # Last node points to None # Traversing the list: current_node = node1 while current_node: print(current_node["data"]) current_node = current_node["next"]content_copy download
Use code with caution.Python
Subtopics:
Nodes: Each element in the list, containing data and a pointer (reference) to the next node.
Head: The first node of the list.
Tail: The last node (points to None).
Singly Linked List: Each node points to the next one.
Doubly Linked List: Each node points to both the next and the previous node. (Allows traversal in both directions).
Operations: Insertion, deletion, traversal, searching.
d) Trees (Specifically Binary Trees):
Simple Explanation: Like a real tree, but upside down! It has a root at the top, branches (nodes), and leaves at the bottom. Binary Tree: Each node has at most two children (left and right child).
Analogy: Family tree, organizational chart, file system structure.
Conceptual Python Example (again, implementation is more involved):
# Imagine tree nodes: root = {"data": "A", "left": node_B, "right": node_C} node_B = {"data": "B", "left": node_D, "right": node_E} node_C = {"data": "C", "left": None, "right": node_F} # ... and so on ... # Tree Traversal (e.g., Pre-order - Root, Left, Right): def preorder_traversal(node): if node: print(node["data"]) # Process root preorder_traversal(node["left"]) # Process left subtree preorder_traversal(node["right"]) # Process right subtree # preorder_traversal(root)content_copy download
Use code with caution.Python
Subtopics:
Root: The topmost node.
Node: Each element in the tree.
Edge: Connection between nodes.
Parent, Child, Sibling: Relationships between nodes.
Leaf Node: A node with no children.
Binary Search Tree (BST): A special type of binary tree where nodes are ordered in a specific way to allow for efficient searching. (Left child's value is less than parent, right child's value is greater).
Tree Traversals: Pre-order, In-order, Post-order (ways to visit all nodes in a tree).
e) Graphs:
Simple Explanation: Like a network of friends, cities connected by roads, or web pages linked together. Consists of vertices (nodes) and edges (connections). No hierarchical structure like trees.
Analogy: Social network, map of cities, website links.
Conceptual Python Example (using dictionaries to represent adjacency):
graph = { "A": ["B", "C"], # Node A is connected to B and C "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"] } # Example: Finding neighbors of node "B" print(graph["B"]) # Output: ['A', 'D', 'E']content_copy download
Use code with caution.Python
Subtopics:
Vertices (Nodes): The entities in the graph.
Edges: Connections between vertices.
Directed Graph: Edges have direction (like one-way streets).
Undirected Graph: Edges have no direction (like two-way streets).
Weighted Graph: Edges have weights/costs associated with them (like distances between cities).
Graph Traversal: Breadth-First Search (BFS), Depth-First Search (DFS) (ways to explore all vertices in a graph).
Shortest Path Algorithms: Dijkstra's algorithm (finding the shortest path between two vertices in a weighted graph).
II. Algorithms (Step-by-Step Instructions)
Searching Algorithms: Finding a specific item in a data structure.
a) Linear Search (Sequential Search):
Simple Explanation: Check each item in the list one by one until you find the target or reach the end.
Analogy: Looking for a specific book on a shelf by checking each book from left to right.
Python Example:
def linear_search(my_list, target): for index, item in enumerate(my_list): if item == target: return index # Found at this index return -1 # Not found numbers = [10, 5, 20, 15, 8] target_number = 15 index = linear_search(numbers, target_number) if index != -1: print(f"Found {target_number} at index {index}") # Output: Found 15 at index 3 else: print(f"{target_number} not found in the list")content_copy download
Use code with caution.Python
b) Binary Search:
Simple Explanation: Efficiently search in a sorted list. Repeatedly divides the search interval in half. If the middle element is the target, you're done. If the target is smaller, search the left half; if larger, search the right half.
Analogy: Looking for a word in a dictionary. You open to the middle, and based on whether your word comes before or after, you narrow your search to the left or right half.
Python Example (requires list to be sorted first):
def binary_search(my_list, target): low = 0 high = len(my_list) - 1 while low <= high: mid = (low + high) // 2 # Integer division if my_list[mid] == target: return mid # Found at index mid elif my_list[mid] < target: low = mid + 1 # Search in right half else: # my_list[mid] > target high = mid - 1 # Search in left half return -1 # Not found sorted_numbers = [5, 8, 10, 15, 20] # List MUST be sorted for binary search target_number = 8 index = binary_search(sorted_numbers, target_number) if index != -1: print(f"Found {target_number} at index {index}") # Output: Found 8 at index 1 else: print(f"{target_number} not found in the list")content_copy download
Use code with caution.Python
Sorting Algorithms: Arranging items in a specific order (e.g., ascending or descending).
a) Bubble Sort:
Simple Explanation: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Larger elements "bubble" to the end. (Not very efficient for large lists, but easy to understand).
Analogy: Sorting playing cards in your hand by repeatedly comparing and swapping adjacent cards.
Python Example:
def bubble_sort(my_list): n = len(my_list) for i in range(n): # Outer loop for passes for j in range(0, n - i - 1): # Inner loop for comparisons if my_list[j] > my_list[j + 1]: # Swap if elements are in wrong order my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j] return my_list numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = bubble_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]content_copy download
Use code with caution.Python
b) Selection Sort:
Simple Explanation: Repeatedly finds the minimum element from the unsorted part of the list and places it at the beginning.
Analogy: Sorting a deck of cards by finding the smallest card, putting it in the first position, then finding the next smallest from the remaining cards, and so on.
Python Example:
def selection_sort(my_list): n = len(my_list) for i in range(n): min_index = i # Assume current index is minimum for j in range(i + 1, n): # Find minimum in the unsorted part if my_list[j] < my_list[min_index]: min_index = j # Swap the found minimum element with the first element of unsorted part my_list[i], my_list[min_index] = my_list[min_index], my_list[i] return my_list numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = selection_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]content_copy download
Use code with caution.Python
c) Insertion Sort:
Simple Explanation: Builds the sorted list one item at a time. It iterates through the list and inserts each element into its correct position in the already sorted part of the list.
Analogy: Sorting playing cards as you pick them up one by one. You insert each new card into its correct position within the cards you already have sorted in your hand.
Python Example:
def insertion_sort(my_list): for i in range(1, len(my_list)): # Start from the second element key = my_list[i] # Element to be inserted j = i - 1 while j >= 0 and key < my_list[j]: # Shift elements to the right to make space my_list[j + 1] = my_list[j] j -= 1 my_list[j + 1] = key # Insert the key in its correct position return my_list numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = insertion_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]content_copy download
Use code with caution.Python
d) Merge Sort:
Simple Explanation: A "divide and conquer" algorithm. Recursively divides the list into smaller sublists until each sublist contains only one element (which is considered sorted). Then, it repeatedly merges the sublists to produce new sorted sublists until there is only one sorted list remaining. Efficient for larger lists.
Analogy: Sorting a deck of cards by splitting it in half, sorting each half, and then merging the two sorted halves.
Python Example (Recursive):
def merge_sort(my_list): if len(my_list) <= 1: return my_list # Base case: already sorted if 0 or 1 element mid = len(my_list) // 2 left_half = my_list[:mid] right_half = my_list[mid:] left_half = merge_sort(left_half) # Recursively sort left half right_half = merge_sort(right_half) # Recursively sort right half return merge(left_half, right_half) # Merge the sorted halves def merge(left, right): # Helper function to merge two sorted lists merged = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) # Add any remaining elements from left merged.extend(right[j:]) # Add any remaining elements from right return merged numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = merge_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]content_copy download
Use code with caution.Python
e) Quick Sort:
Simple Explanation: Another "divide and conquer" algorithm. Chooses a "pivot" element from the list. Partitions the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The sub-lists are then recursively sorted. Efficient on average.
Analogy: Sorting papers on a desk by picking one paper as a pivot, putting all papers smaller than it to the left, all papers larger to the right, and then recursively sorting the left and right piles.
Python Example (Recursive, using list comprehensions for clarity):
def quick_sort(my_list): if len(my_list) <= 1: return my_list # Base case: already sorted pivot = my_list[len(my_list) // 2] # Choose middle element as pivot lesser_than_pivot = [x for x in my_list if x < pivot] equal_to_pivot = [x for x in my_list if x == pivot] greater_than_pivot = [x for x in my_list if x > pivot] return quick_sort(lesser_than_pivot) + equal_to_pivot + quick_sort(greater_than_pivot) numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = quick_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]content_copy download
Use code with caution.Python
Recursion: A technique where a function calls itself to solve smaller parts of a problem.
Simple Explanation: Breaking a problem down into smaller, self-similar subproblems. You need a base case (stopping condition) to prevent infinite recursion.
Analogy: Russian nesting dolls (Matryoshka dolls). Each doll contains a smaller version of itself until you reach the smallest doll.
Python Example (Factorial Calculation):
def factorial_recursive(n): if n == 0: # Base case: factorial of 0 is 1 return 1 else: return n * factorial_recursive(n - 1) # Recursive call print(factorial_recursive(5)) # Output: 120 (5! = 5*4*3*2*1)content_copy download
Use code with caution.Python
Divide and Conquer: An algorithmic paradigm that recursively breaks down a problem into subproblems, solves subproblems, and then combines the solutions to solve the original problem. (Merge Sort and Quick Sort are examples).
Simple Explanation: Divide the problem, conquer (solve) the smaller parts, and combine the results.
Analogy: Building a large structure with smaller, pre-fabricated components.
Greedy Algorithms: Make the locally optimal choice at each step in the hope of finding a global optimum.
Simple Explanation: Always choose the best option available right now, without looking ahead. Doesn't always guarantee the best overall solution, but often works well and is simpler.
Analogy: Making change with coins. You always choose the largest denomination coin that is less than or equal to the remaining amount.
Python Example (Simple Coin Change - might not be optimal in all cases):
def greedy_coin_change(coins, amount): coins.sort(reverse=True) # Sort coins in descending order num_coins = 0 coins_used = [] for coin in coins: while amount >= coin: amount -= coin num_coins += 1 coins_used.append(coin) if amount == 0: return num_coins, coins_used else: return -1, [] # No solution found (greedy might fail in some cases) coin_denominations = [25, 10, 5, 1] target_amount = 49 count, used_coins = greedy_coin_change(coin_denominations, target_amount) if count != -1: print(f"Greedy algorithm used {count} coins: {used_coins}") # Output: Greedy algorithm used 7 coins: [25, 10, 10, 1, 1, 1, 1] (Example output) else: print("Greedy algorithm failed to find a solution.")content_copy download
Use code with caution.Python
Dynamic Programming: An optimization technique that solves problems by breaking them down into overlapping subproblems and storing the solutions to these subproblems to avoid recomputing them.
Simple Explanation: Solve each subproblem only once and store its result. Use the stored result when you encounter the same subproblem again. Good for problems with overlapping subproblems and optimal substructure (optimal solution is composed of optimal solutions to subproblems).
Analogy: Calculating Fibonacci numbers efficiently. Instead of recalculating Fibonacci(3) multiple times, you calculate it once and store the result to reuse it.
Python Example (Fibonacci using Memoization - a form of dynamic programming):
def fibonacci_dynamic(n, memo={}): # memo is a dictionary to store results if n in memo: return memo[n] # Return stored result if already computed if n <= 1: return n else: result = fibonacci_dynamic(n - 1, memo) + fibonacci_dynamic(n - 2, memo) memo[n] = result # Store the result before returning return result print(fibonacci_dynamic(10)) # Output: 55 (Calculates efficiently using memoization)content_copy download
Use code with caution.Python
Putting it all together:
Data Structures are containers to hold data in an organized way.
Algorithms are procedures to manipulate and process data within these structures.
You choose the right data structure based on how you need to access and manipulate the data.
You choose the right algorithm based on the task you need to perform and the efficiency you require.
Learning Path:
Start with Basic Data Structures: Lists, tuples, dictionaries, sets. Understand how they work and when to use each.
Learn Basic Algorithms: Linear search, binary search, bubble sort, selection sort, insertion sort. Understand their time complexity (how efficient they are).
Move to Abstract Data Structures: Stacks, queues, linked lists, trees, graphs. Understand their properties and common operations.
Explore More Algorithms: Merge sort, quick sort, recursion, divide and conquer, greedy algorithms, dynamic programming, graph algorithms (BFS, DFS, Dijkstra's).
Practice, Practice, Practice: Solve coding problems on platforms like LeetCode, HackerRank, Codewars. Implement data structures and algorithms yourself.
This is a broad overview. Each topic can be explored in much greater depth. But hopefully, this gives you a good starting point and a clear roadmap for learning Data Structures and Algorithms in Python! Good luck!
Subscribe to my newsletter
Read articles from Singaraju Saiteja directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Singaraju Saiteja
Singaraju Saiteja
I am an aspiring mobile developer, with current skill being in flutter.