This page is a full mini-course on DSA in Python. It covers core data structures, time complexity, sorting, searching, trees, graphs, and more – with diagrams and code examples.
You will learn:
Lists, stacks, queues, hash tables, trees, graphs.
Searching, sorting, BFS, DFS, recursion basics.
Big-O time & space analysis for each operation.
A data structure is a way to organize and store data so it can be used efficiently.
Examples:
An algorithm is a step-by-step procedure to solve a problem.
Examples:
Big-O describes how running time grows as input size (n) grows.
It ignores constant factors and focuses on the growth trend.
Example: accessing arr[i] or a key in a dictionary.
Example: binary search in a sorted list.
Example: scanning a list once in a loop.
Example: nested loops (basic bubble sort).
# O(1): constant
def get_first(arr):
return arr[0]
# O(n): linear
def print_all(arr):
for x in arr:
print(x)
# O(n^2): quadratic
def print_pairs(arr):
for i in range(len(arr)):
for j in range(len(arr)):
print(arr[i], arr[j])Python has several built-in data structures that are widely used: lists, tuples, sets, and dictionaries.
Lists are ordered, mutable collections. Internally they behave like dynamic arrays. They automatically resize as you add or remove elements.
arr = [10, 20, 30]
arr.append(40) # [10, 20, 30, 40]
arr.insert(1, 15) # [10, 15, 20, 30, 40]
arr.remove(20) # [10, 15, 30, 40]
x = arr[2] # 30Access: O(1), Append: O(1) amortized, Insert / Remove in middle: O(n). Are used for: dynamic collections, stacks, queues.
Tuples – like lists but immutable. They cannot be changed after creation.
point = (3, 5)
x, y = pointSets – unordered collection of unique values. They automatically remove duplicates.
nums = {1, 2, 2, 3}
print(nums) # {1, 2, 3}Dictionaries – hash tables: key → value mapping. They provide fast access to values based on unique keys.
user = {"name": "Alex", "age": 25}
print(user["name"]) # "Alex"
user["country"] = "LT"Dict / Set average lookup, insert, delete: O(1). Used for fast key-based access.
Last In, First Out – like a stack of plates.
# Using list as a stack
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
stack.pop() # 30
stack.pop() # 20push / pop: O(1). Used for: undo history, function call stack.
First In, First Out – like a line in a store.
from collections import deque
q = deque()
q.append(10) # enqueue
q.append(20)
q.append(30)
q.popleft() # 10 (dequeue)
q.popleft() # 20
enqueue / dequeue with deque: O(1). Used for: task scheduling, BFS traversal.(Breadth-First Search (BFS) traversal is a graph or tree traversal algorithm that explores nodes level by level, starting from a source node and visiting all its neighbors before moving to the next depth.)
A linked list is a chain of nodes; each node stores data and a pointer to the next node. It allows efficient insertion and deletion from any position.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_front(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_nodeInsert at head: O(1), search by value: O(n).
A tree is a hierarchical structure with nodes connected by edges. Each node can have multiple children, except in binary trees where each node has at most two children.
A binary tree node has at most two children: left and right.
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = NoneFor each node: left < node < right. This makes searching efficient.
Average search / insert / delete: O(log n) Worst case (skewed): O(n).
def insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return rootA graph is a set of nodes (vertices) connected by edges. Graphs are used for: social networks, maps, recommendation systems, routing, and more.
An adjacency list uses a dictionary where each key is a node and the value is a list of connected nodes.
graph = {
1: [2, 3],
2: [1, 4],
3: [1],
4: [2]
}BFS explores a graph level by level (uses a queue).
from collections import deque
def bfs(graph, start):
visited = set()
q = deque([start])
while q:
node = q.popleft()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
q.append(neighbor)
return visitedDFS explores as far as possible along one branch (uses recursion or a stack).
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
return visitedSorting is a classic algorithm topic. Here are the core ones:
Simple but slow for large inputs.
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]Efficient divide-and-conquer sort used in real systems.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultFast in practice, uses partitioning.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)Common searching algorithms include linear and binary search:
Scan each element until you find the target.
def linear_search(arr, target):
for i, value in enumerate(arr):
if value == target:
return i
return -1Binary search works only on sorted arrays.
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Space complexity measures how much extra memory an algorithm uses as input size grows. It is important for large datasets and memory-constrained environments.
Common space complexities:
def example(arr):
x = 10 # O(1) extra space
temp = arr[:] # O(n) extra space (copy of array)
return tempIn this DSA guide, you learned:
To deepen your understanding, practice implementing these structures and algorithms from scratch. Solve coding challenges on platforms like LeetCode, HackerRank, or CodeSignal. Study advanced topics like balanced trees, graph algorithms, and dynamic programming.