Module 6: Core Data Structures

A list is an ordered, mutable, indexable sequence — it can hold mixed types, and it can grow or shrink freely after creation: nums = [10, 20, 30].

Because lists are mutable, methods like append() (add an item to the end), insert(), remove(), and pop() all change the same list object in place rather than building a new one.

Slicing — nums[1:3] — pulls out a sub-list without touching the original.

CPython List Architecture & Time Complexity

Under the hood, a Python list is implemented as a dynamic array of pointers to objects in C. It over-allocates memory slots so that append() achieves amortized O(1) time complexity. However, inserting or deleting from index 0 requires shifting all remaining elements, taking O(n) time.

List Insertion Shifting & Two Pointers

Because Python lists are dynamic arrays of memory pointers under the hood, calling list.insert(i, item) requires physically shifting all elements after i one position right, costing O(n) time. Appending to the end is O(1) amortized.

# Two-pointer pair sum on a sorted list
def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        curr = nums[left] + nums[right]
        if curr == target:
            return (nums[left], nums[right])
        elif curr < target:
            left += 1
        else:
            right -= 1
    return None

A tuple looks similar to a list but is immutable — once created, its elements can never be added to, removed, or reassigned: point = (3, 4).

Because they're immutable, tuples are also hashable, which means (unlike lists) they're allowed to be used as dictionary keys or stored inside sets.

Using a tuple instead of a list is also a signal to anyone reading your code: "this sequence is meant to stay fixed forever."

Tuple Packing & Sequence Unpacking

# Packing and Unpacking
coordinates = 12.9716, 77.5946 # Tuple packing (parentheses optional)
lat, lon = coordinates         # Unpacking into variables

# Swapping values in one elegant line:
a, b = 10, 20
a, b = b, a # Swaps seamlessly without a temp variable!

A set is an unordered collection of guaranteed-unique elements — any duplicates you try to insert are automatically discarded.

Sets are heavily optimized for fast membership testing (checking whether x in my_set in O(1) average time), and they directly support the mathematical operations you'd expect from set algebra: union (|), intersection (&), difference (-), and symmetric difference (^).

# Set Algebra Operations
set_a = {1, 2, 3, 4}
set_b = {3, 4, 5, 6}

print(set_a | set_b) # Union: {1, 2, 3, 4, 5, 6}
print(set_a & set_b) # Intersection: {3, 4}
print(set_a - set_b) # Difference: {1, 2}
print(set_a ^ set_b) # Symmetric Difference: {1, 2, 5, 6}

A dictionary stores key-value pairs, where each key must be unique and of an immutable/hashable type (typically a string, number, or tuple): ages = {"Amit": 21}.

Much like Java's HashMap, dictionaries use hashing internally, giving average O(1) — constant-time — lookup, insertion, and deletion, regardless of how large the dictionary grows.

Since Python 3.7, dictionaries also officially guarantee that they preserve insertion order, something earlier versions of the language did not promise.

Safe Key Access with .get()

Accessing a non-existent key with bracket notation (d["missing"]) raises a KeyError. The pythonic way to access optional keys is using .get(key, default):

user = {"name": "Asha"}
print(user.get("role", "Member")) # Output: "Member" (No KeyError!)