Introduction to Data Structures and Algorithms

📖 Introduction

When I first started programming, I focused entirely on making things work. My code ran, features shipped, and that seemed like enough. But as my projects grew—handling more data, serving more users, requiring more complex logic—I kept hitting walls. Response times degraded. Memory usage spiked. Solutions that worked for 100 items collapsed at 10,000.

That's when I truly understood why data structures and algorithms matter. They're not academic exercises or interview gatekeeping—they're the fundamental tools that separate code that works from code that scales. Every time I choose a list over a set, every time I decide between iteration and recursion, I'm making algorithmic decisions that ripple through the entire system.

This series represents what I wish I'd learned earlier: practical DSA knowledge that directly improves the code you write every day.

---

🎯 What Are Data Structures and Algorithms?

Data Structures

A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. Think of it as choosing the right container for your ingredients:

• Array: A row of numbered boxes—fast to access by position

• Linked List: A chain of connected nodes—easy to insert and remove

• Hash Table: A filing cabinet with labeled folders—instant lookup by name

• Tree: A hierarchical organization chart—efficient for sorted data

• Graph: A network of connections—models relationships

# Different structures for the same data
from collections import deque

# Array/List - ordered, indexed access
users_list = ["alice", "bob", "charlie"]

# Set - unordered, fast membership testing
users_set = {"alice", "bob", "charlie"}

# Dictionary - key-value mapping
users_dict = {"alice": 1, "bob": 2, "charlie": 3}

# Deque - efficient operations at both ends
users_deque = deque(["alice", "bob", "charlie"])

Algorithms

An algorithm is a step-by-step procedure for solving a problem. It's the recipe, not the ingredients. Common categories include:

• Searching: Finding elements (binary search, graph traversal)

• Sorting: Ordering elements (quicksort, mergesort)

• Traversal: Visiting all elements (BFS, DFS)

• Optimization: Finding best solutions (dynamic programming, greedy)

def linear_search(arr: list, target: int) -> int:
    """Find target by checking each element. O(n)"""
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1


def binary_search(arr: list, target: int) -> int:
    """Find target in sorted array by halving search space. O(log n)"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

---

📊 Why DSA Matters

1. Performance at Scale

The difference between O(n) and O(n²) seems small until you hit real data:

n	O(n)	O(n log n)	O(n²)
100	100	664	10,000
1,000	1,000	9,966	1,000,000
10,000	10,000	132,877	100,000,000
100,000	100,000	1,660,964	10,000,000,000

import time

def measure_time(func, *args):
    """Measure execution time of a function."""
    start = time.perf_counter()
    result = func(*args)
    elapsed = time.perf_counter() - start
    return result, elapsed


def find_duplicates_bruteforce(arr: list) -> list:
    """O(n²) - Check every pair."""
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates


def find_duplicates_hashset(arr: list) -> list:
    """O(n) - Use set for seen elements."""
    seen = set()
    duplicates = set()
    for val in arr:
        if val in seen:
            duplicates.add(val)
        seen.add(val)
    return list(duplicates)


# With 10,000 elements:
# Bruteforce: ~5 seconds
# Hashset: ~0.001 seconds

2. Resource Efficiency

Memory and CPU aren't free. In cloud environments, inefficient algorithms directly cost money:

def get_memory_usage():
    """Get current memory usage in MB."""
    import sys
    import gc
    gc.collect()
    # Simplified example
    return sys.getsizeof([]) / 1024 / 1024


# Storing 1 million integers
# List: ~8 MB
# Set: ~32 MB (hash overhead)
# Dict with values: ~48 MB

# Choose based on access patterns, not just convenience

3. Problem-Solving Framework

DSA provides a vocabulary and toolkit for tackling complex problems:

# Problem: Find if path exists between two nodes

# Without DSA knowledge: 
# "How do I even approach this?"

# With DSA knowledge:
# "This is graph traversal. I'll use BFS for shortest path
#  or DFS for existence check. Let me represent the graph
#  as an adjacency list for O(V+E) complexity."

from collections import deque

def path_exists(graph: dict, start: int, end: int) -> bool:
    """BFS to check if path exists between nodes."""
    if start == end:
        return True
    
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node == end:
            return True
        
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)
    
    return False

---

⏱️ Understanding Big O Notation

Big O notation describes how an algorithm's performance scales with input size. It's the language of algorithmic efficiency.

The Core Concept

Big O answers: "As input grows, how does the work grow?"

def constant_time(arr: list) -> int:
    """O(1) - Same time regardless of input size."""
    return arr[0] if arr else None


def linear_time(arr: list) -> int:
    """O(n) - Time grows linearly with input."""
    total = 0
    for num in arr:
        total += num
    return total


def quadratic_time(arr: list) -> list:
    """O(n²) - Time grows with square of input."""
    pairs = []
    for i in arr:
        for j in arr:
            pairs.append((i, j))
    return pairs


def logarithmic_time(arr: list, target: int) -> int:
    """O(log n) - Time grows logarithmically."""
    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

Common Complexity Classes

Visual Comparison

Operations
    ^
    |                                           O(n!)
    |                                      O(2ⁿ)
    |                                 O(n²)
    |                            
    |                       O(n log n)
    |                  O(n)
    |            O(log n)
    |     O(1)
    +-----------------------------------------> n

Practical Examples

# O(1) - Constant
def get_first(arr: list):
    return arr[0]

def dict_lookup(d: dict, key: str):
    return d.get(key)

# O(log n) - Logarithmic
def binary_search(arr: list, target: int) -> int:
    # Each step eliminates half the remaining elements
    pass

# O(n) - Linear
def find_max(arr: list) -> int:
    return max(arr)

def sum_all(arr: list) -> int:
    return sum(arr)

# O(n log n) - Linearithmic
def efficient_sort(arr: list) -> list:
    return sorted(arr)  # Timsort

# O(n²) - Quadratic
def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(2ⁿ) - Exponential
def fibonacci_naive(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

---

💾 Space Complexity

Space complexity measures memory usage as input grows.

Constant Space - O(1)

def find_max_inplace(arr: list) -> int:
    """O(1) space - only uses fixed variables."""
    if not arr:
        return None
    
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

Linear Space - O(n)

def duplicate_array(arr: list) -> list:
    """O(n) space - creates array proportional to input."""
    return [x for x in arr]


def get_prefix_sums(arr: list) -> list:
    """O(n) space - stores cumulative sums."""
    prefix = [0] * (len(arr) + 1)
    for i, num in enumerate(arr):
        prefix[i + 1] = prefix[i] + num
    return prefix

Recursive Space

def factorial(n: int) -> int:
    """
    O(n) space due to call stack.
    Each recursive call adds a frame to the stack.
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)


# Call stack for factorial(5):
# factorial(5) -> waiting
#   factorial(4) -> waiting
#     factorial(3) -> waiting
#       factorial(2) -> waiting
#         factorial(1) -> returns 1

Space-Time Tradeoffs

Often, you can trade memory for speed:

# Time: O(n²), Space: O(1)
def two_sum_brute(arr: list, target: int) -> tuple:
    """Check all pairs."""
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return (i, j)
    return None


# Time: O(n), Space: O(n)
def two_sum_hash(arr: list, target: int) -> tuple:
    """Use hash map to store seen values."""
    seen = {}  # value -> index
    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

---

🐍 Python Memory Model

Understanding Python's memory model helps make better DSA decisions.

Object References

# Python variables are references to objects
a = [1, 2, 3]
b = a  # b references the same list
b.append(4)
print(a)  # [1, 2, 3, 4] - a is also modified!

# Create a copy for independence
c = a.copy()  # or a[:] or list(a)
c.append(5)
print(a)  # [1, 2, 3, 4] - a unchanged

Mutability

# Mutable: can change in place
my_list = [1, 2, 3]
my_list[0] = 10  # Modifies existing list

my_dict = {"a": 1}
my_dict["b"] = 2  # Adds to existing dict

# Immutable: creates new objects
my_str = "hello"
my_str = my_str + " world"  # Creates new string

my_tuple = (1, 2, 3)
# my_tuple[0] = 10  # TypeError!

Container Sizes

import sys

# Approximate sizes (bytes) for different containers
print(f"Empty list: {sys.getsizeof([])}")           # ~56
print(f"Empty dict: {sys.getsizeof({})}")           # ~64
print(f"Empty set: {sys.getsizeof(set())}")         # ~216
print(f"Empty tuple: {sys.getsizeof(())}")          # ~40
print(f"Empty string: {sys.getsizeof('')}")         # ~49

# Lists grow dynamically with over-allocation
lst = []
for i in range(10):
    lst.append(i)
    print(f"Length {len(lst)}: {sys.getsizeof(lst)} bytes")

When to Use What

Need	Best Structure	Why
Ordered sequence, index access	list	O(1) index, O(1) amortized append
Fast membership testing	set	O(1) average lookup
Key-value mapping	dict	O(1) average access
Queue (FIFO)	collections.deque	O(1) both ends
Immutable sequence	tuple	Hashable, less memory
Priority queue	heapq	O(log n) push/pop

---

🧮 Analyzing Your First Algorithm

Let's analyze a real problem step by step.

Problem: Find Missing Number

Given an array of n-1 integers in range [1, n], find the missing number.

# Approach 1: Sorting
def find_missing_sort(nums: list) -> int:
    """
    Sort and find gap.
    Time: O(n log n) - sorting
    Space: O(1) or O(n) depending on sort
    """
    nums.sort()
    for i, num in enumerate(nums):
        if num != i + 1:
            return i + 1
    return len(nums) + 1


# Approach 2: Hash Set
def find_missing_set(nums: list) -> int:
    """
    Use set for O(1) lookup.
    Time: O(n)
    Space: O(n)
    """
    num_set = set(nums)
    n = len(nums) + 1
    for i in range(1, n + 1):
        if i not in num_set:
            return i
    return -1


# Approach 3: Math (Optimal)
def find_missing_math(nums: list) -> int:
    """
    Sum formula: expected - actual = missing.
    Time: O(n)
    Space: O(1)
    """
    n = len(nums) + 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum


# Approach 4: XOR (Bit Manipulation)
def find_missing_xor(nums: list) -> int:
    """
    XOR all indices and values.
    Time: O(n)
    Space: O(1)
    """
    n = len(nums) + 1
    xor_result = 0
    
    for i in range(1, n + 1):
        xor_result ^= i
    
    for num in nums:
        xor_result ^= num
    
    return xor_result

Analysis Summary

Approach	Time	Space	Notes
Sort	O(n log n)	O(1)*	Simple but slower
Hash Set	O(n)	O(n)	Fast but uses memory
Math	O(n)	O(1)	Optimal, may overflow
XOR	O(n)	O(1)	Optimal, no overflow

---

📝 Practice Exercises

Exercise 1: Analyze Complexity

Determine the time and space complexity:

def mystery1(n: int) -> int:
    total = 0
    for i in range(n):
        for j in range(n):
            total += 1
    return total

def mystery2(n: int) -> int:
    if n <= 1:
        return 1
    return mystery2(n // 2) + 1

def mystery3(arr: list) -> list:
    result = []
    for item in arr:
        if item not in result:
            result.append(item)
    return result

Solutions

1. mystery1: Time O(n²), Space O(1)

2. mystery2: Time O(log n), Space O(log n) - call stack

3. mystery3: Time O(n²) - in on list is O(n), Space O(n)

Exercise 2: Optimize This

def find_common_elements(list1: list, list2: list) -> list:
    """Find elements present in both lists."""
    common = []
    for item in list1:
        if item in list2 and item not in common:
            common.append(item)
    return common

# Current complexity: O(n * m) where n, m are list lengths
# Can you make it O(n + m)?

Solution

def find_common_elements_optimized(list1: list, list2: list) -> list:
    """O(n + m) using sets."""
    set1 = set(list1)
    set2 = set(list2)
    return list(set1 & set2)

Exercise 3: Space-Time Tradeoff

# Problem: Check if string has all unique characters

# Version 1: O(1) space - but what's the time?
def is_unique_v1(s: str) -> bool:
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] == s[j]:
                return False
    return True

# Write Version 2: O(n) time, O(n) space

Solution

def is_unique_v2(s: str) -> bool:
    """O(n) time, O(n) space using set."""
    seen = set()
    for char in s:
        if char in seen:
            return False
        seen.add(char)
    return True

# Or simply:
def is_unique_v3(s: str) -> bool:
    return len(s) == len(set(s))

---

🔑 Key Takeaways

1. Data structures organize data; algorithms process it

2. Big O describes growth rate, not exact time

3. Space-time tradeoffs are fundamental—optimize for your constraints

4. Python's built-ins are well-optimized—understand when to use them

5. Analysis skills improve with practice—always ask "how does this scale?"

---

🚀 What's Next?

In the next article, we'll dive deeper into complexity analysis:

• Best, worst, and average case analysis

• Amortized complexity

• Practical benchmarking techniques

• Common complexity patterns

Next: Article 2 - Complexity Analysis Deep Dive

---

📚 References

• Cormen, T. H., et al. "Introduction to Algorithms" (CLRS)

• Python Time Complexity: Python Wiki

• Big O Cheat Sheet: bigocheatsheet.com