Python Lists

Python Lists: Dynamic Arrays, Slicing, & Comprehensions

Lists in Python are mutable, ordered sequences of variable-length object references. Implemented as dynamic arrays under the hood, lists allow fast index lookup ($O(1)$) and dynamic resizing.

Dynamic Array Architecture in Memory

flowchart TD
    subgraph List Object Header
        size["PyListObject (size=3, allocated=6)"]
    end
    subgraph Pointer Array in Memory
        p0["ptr [0]"] --> obj0["str: 'apple'"]
        p1["ptr [1]"] --> obj1["int: 100"]
        p2["ptr [2]"] --> obj2["dict: {'a': 1}"]
    end
    size --> Pointer Array in Memory

List Operation Complexities

• Index Lookup (list[i]): $O(1)$
• Append (list.append(x)): Amortized $O(1)$
• Insert / Pop middle (list.insert(0, x)): $O(N)$
• Search (x in list): $O(N)$

Practical Code Example

from typing import List

def manage_inventory() -> None:
    # Initialization & List Comprehension
    raw_prices: List[float] = [12.50, 45.00, 8.99, 99.95, 3.20]
    
    # Filter prices > 10 and apply 10% discount
    discounted: List[float] = [round(p * 0.9, 2) for p in raw_prices if p > 10.0]
    print("Discounted Prices (> $10):", discounted)

    # In-place Modification vs Sorting
    items: List[str] = ["server", "database", "cache", "load_balancer"]
    items.sort()  # In-place sort O(N log N)
    print("Sorted Items:", items)

    # Pop and Remove
    removed_item = items.pop(0)
    print(f"Popped item '{removed_item}', remaining: {items}")

if __name__ == "__main__":
    manage_inventory()

Best Practices & Gotchas

• Prefer List Comprehensions over map()/filter(): List comprehensions are generally more readable and faster in Python.
• Do Not Modify Lists While Iterating: Modifying a list while looping over it causes index misalignment bugs. Iterate over a copy (for item in items.copy():) or use a comprehension.
• Use collections.deque for Queues: Popping from the beginning of a standard list (list.pop(0)) takes $O(N)$ time. Use collections.deque for $O(1)$ FIFO operations.

Self-Check Challenge

Write a list comprehension that takes a list of integers [1, 2, 3, 4, 5, 6, 7, 8] and returns a list containing the squares of only the even numbers.