cano(PY)code
← Previous: Python Operators All Modules Next: Python Tuples →
MOD-09 · Sequence #9 · Python Collections

Python Lists (Arrays)

Python lists are dynamic arrays of pointers stored contiguously in memory. They provide O(1) random index access and amortized O(1) append. Mastering list slicing, common methods, and list comprehensions is a core pillar of technical problem solving.

Live Interactive Code Snippet (Python 3.12 CPython WASM) Open in Practice Mode → 
fruits = ["apple", "banana", "cherry"]
fruits.append("orange")
squared = [x**2 for x in range(5)]
print(fruits, squared)

Core Principles & Mental Models

1. Memory Architecture of CPython Lists

Dynamic Array with Over-Allocation

  • Under the hood in CPython, a list is a PyListObject containing a pointer to a contiguous array of PyObject pointers.
  • Indexing `lst[i]` is instantaneous O(1) arithmetic pointer offset.
  • When appending beyond capacity, CPython reallocates the array with geometric growth (amortized O(1) append).
  • Inserting or deleting at the beginning (`lst.insert(0, val)` or `lst.pop(0)`) requires shifting all subsequent pointers, costing O(N) time.
numbers = [10, 20, 30]
numbers.append(40)       # O(1) amortized
first = numbers.pop(0)   # O(N) linear time - shifts remaining items!
print("Remaining:", numbers)
💡 Key Takeaway: Use collections.deque when you need fast O(1) pops and appends from both ends.

2. List Comprehensions

Declarative Syntax Faster than Manual Loops

  • Syntax: `[expression for item in iterable if condition]`.
  • List comprehensions run in specialized C-level bytecode, making them faster than building lists with `.append()` inside a standard for loop.
  • Avoid deeply nested comprehensions (more than 2 levels) to maintain code readability.
matrix = [[1, 2], [3, 4], [5, 6]]
flattened_evens = [x for row in matrix for x in row if x % 2 == 0]
print("Flattened evens:", flattened_evens)
💡 Key Takeaway: List comprehensions combine mapping and filtering into a single expressive, optimized statement.

Interactive Walkthrough Examples

Sorting with Key Functions (Intermediate)

Using `sort()` (in-place) vs `sorted()` (new list) with custom key extractors.

students = [
    {"name": "Alice", "score": 92},
    {"name": "Bob", "score": 78},
    {"name": "Charlie", "score": 95}
]
# Sort by score descending
ranked = sorted(students, key=lambda s: s["score"], reverse=True)
for rank, s in enumerate(ranked, 1):
    print(f"{rank}. {s['name']}: {s['score']}")

Explanation: sorted() uses Timsort (O(N log N) hybrid mergesort/insertionsort) and preserves the original list.

Common Misconceptions & Exam Traps

Common Pitfall: The 2D Aliased Grid Trap: `[[0] * cols] * rows`

`[row] * 3` creates three references pointing to the SAME row list in memory.

Buggy Code 
grid = [[0] * 3] * 3
grid[0][0] = 99
print("Grid:", grid)  # [[99, 0, 0], [99, 0, 0], [99, 0, 0]] - ALL rows modified!
Correct Solution 
grid = [[0 for _ in range(3)] for _ in range(3)]
grid[0][0] = 99
print("Independent grid:", grid)  # [[99, 0, 0], [0, 0, 0], [0, 0, 0]]

Exam Trap Note: This is the #1 most common trap in undergraduate exams when implementing game boards or matrices.

Conceptual Knowledge Self-Check Quiz

Q1: What is the time complexity of `list.pop(0)` in standard Python?

  1. O(1)
  2. O(log N)
  3. O(N)
  4. O(N^2)

Removing the first item requires shifting all N-1 subsequent pointers left in the contiguous memory buffer, taking O(N) time.

Algorithmic Practice Challenges

Idiomatic Best Practices

  • ✅ Use list comprehensions instead of map() and filter() with lambdas.
  • ✅ Never mutate a list while iterating over it with a for loop; iterate over a copy `for item in lst[:]:`.
← Python Operators Take Assessed Test → Python Tuples →

All 26 Curriculum Modules