Computer Science: Data Structures & Algorithms
Understanding how to organize data and solve problems efficiently.
1. Why Data Structures & Algorithms Matter
Choosing the right data structure and algorithm affects a program’s speed and memory usage.
This is measured using Big O notation, which describes how runtime/memory grows as input size
increases.
Notation Name Example
O(1) Constant Accessing an array element by index
O(log n) Logarithmic Binary search
O(n) Linear Looping through a list once
O(n log n) Linearithmic Efficient sorting (merge sort)
O(n²) Quadratic Nested loops (bubble sort)
2. Core Data Structures
Arrays / Lists
Ordered, indexed collections. Fast access O(1), but insertion/deletion in the middle is O(n).
Linked Lists
Nodes connected via pointers. Efficient insertion/deletion O(1) at known position, but no random
access (O(n) to find an element).
Stacks (LIFO – Last In, First Out)
Used for undo functionality, expression evaluation, backtracking.
stack = []
[Link](1) # push
[Link](2)
[Link]() # removes 2
Queues (FIFO – First In, First Out)
Used for task scheduling, breadth-first search.
from collections import deque
queue = deque()
[Link](1) # enqueue
[Link]() # dequeue
Hash Tables / Dictionaries
Key-value storage with average O(1) lookup, insertion, and deletion.
student_grades = {"Alice": 90, "Bob": 85}
Trees
Hierarchical structures. A Binary Search Tree (BST) keeps left children smaller and right children
larger than the parent, enabling O(log n) search on balanced trees.
Graphs
Nodes (vertices) connected by edges — model networks, maps, social connections. Traversed via
BFS (breadth-first search) or DFS (depth-first search).
3. Key Algorithms
Searching
Linear Search: O(n) — check each element.
Binary Search: O(log n) — repeatedly halve a sorted list.
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 -1
Sorting
Bubble Sort: O(n²) — simple but slow, repeatedly swaps adjacent out-of-order elements.
Merge Sort: O(n log n) — divide and conquer, splits array and merges sorted halves.
Quick Sort: O(n log n) average — picks a pivot and partitions around it.
Recursion
A function calling itself to solve smaller sub-problems.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
4. Problem-Solving Approach
1. Understand the problem and constraints.
2. Plan: consider brute force first, then optimize.
3. Choose the right data structure based on access patterns needed.
4. Implement and test with edge cases (empty input, duplicates, large input).
5. Analyze time and space complexity.
5. Practice Problem
Given a list of numbers, find two numbers that sum to a target value (Two Sum problem):
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
This runs in O(n) time using a hash table, compared to O(n²) with nested loops.
Summary
Choosing appropriate data structures (arrays, linked lists, stacks, queues, trees, graphs, hash
tables) and efficient algorithms (searching, sorting, recursion) is central to writing performant
software.