Back to Study Material Python

DSA with Python

Python is an excellent language for learning data structures and algorithms because its syntax is concise, its built-in types (list, dict, set, deque) dire...

DSA with Python

Why Python for DSA?

Python is an excellent language for learning data structures and algorithms because its syntax is concise, its built-in types (list, dict, set, deque) directly correspond to fundamental data structures, and the standard library provides efficient implementations of many algorithms. Implementing a stack in Python requires only a list with append() and pop(). A queue uses deque with append() and popleft(). This directness lets you focus on algorithmic thinking rather than language mechanics.

Implementing a Stack

A stack follows Last-In-First-Out (LIFO) order. Implement with a list: stack = []; stack.append(1); stack.append(2); top = stack.pop() gives 2. Both append() and pop() from the right end of a list are O(1) amortised. Check the top without removing: stack[-1]. Check if empty: not stack. Stacks are used for function call tracking, expression parsing, undo operations, and depth-first search.

Implementing a Queue

A queue follows First-In-First-Out (FIFO) order. Use deque for O(1) performance: from collections import deque; q = deque(); q.append(1); q.append(2); front = q.popleft() gives 1. Avoid using list.pop(0) as a queue because it is O(n). The queue module also provides thread-safe Queue, SimpleQueue, and LifoQueue classes for concurrent programming. For algorithm problems, deque is the standard choice.

Binary Search Implementation

Binary search finds an element in a sorted list in O(log n) time. def binary_search(arr, target): lo, hi = 0, len(arr)-1; while lo <= hi: mid = (lo + hi) // 2; if arr[mid] == target: return mid; elif arr[mid] < target: lo = mid + 1; else: hi = mid - 1; return -1. The bisect module provides built-in binary search: bisect.bisect_left(arr, target) returns the insertion point. Always confirm the list is sorted before applying binary search.

Recursion for Trees and Graphs

Trees and graphs are most naturally traversed with recursion or explicit stacks/queues. Recursive in-order traversal of a binary search tree: def inorder(node): if node: inorder(node.left); print(node.val); inorder(node.right). The recursion mirrors the tree's structure directly. For graphs, recursive DFS: def dfs(node, visited): visited.add(node); for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, visited). Python's 1000-frame recursion limit can be a constraint for deep trees; iterative DFS with an explicit stack avoids this.

Exam Tip

For algorithm interviews in Python, know the time complexity of core operations: list append O(1) amortised, list insert at index O(n), list search O(n), dict get/set O(1) average, set membership O(1) average, heapq push/pop O(log n). Common interview trap: using a list as a queue with pop(0) gives O(n^2) for n dequeue operations. Always use deque for queues. Being able to state complexities without hesitation shows algorithmic maturity beyond just writing correct code.