Arrays (Lists) Basics

Prev Next

When interviewers say "array," a Python developer's honest answer is: "I'll use a list." Unlike Java's int[], a Python list has no fixed size declared up front — it grows and shrinks as needed. Under the hood, CPython still implements it as a contiguous array of pointers with spare capacity, which is exactly why it behaves like the "array" data structure interviews expect, complexity and all, while still feeling flexible to use.

Indexing Is O(1)

Because a list stores pointers to its elements contiguously, reading or writing by index is a direct offset calculation — no scanning involved, regardless of list length.

scores = [88, 92, 76, 99]
print(scores[2])   # 76 - direct lookup
scores[2] = 80   # direct overwrite

Time complexity: O(1) for both the read and the write — one pointer arithmetic step regardless of list size. Space complexity: O(1) — no additional memory used beyond the list itself.

Append Is Amortized O(1), Insert-at-Front Is O(n)

list.append() writes into pre-allocated spare capacity most of the time. When that spare capacity runs out, CPython allocates a larger underlying buffer (typically growing by roughly 1.125×) and copies every existing element over — an O(n) event, but one that happens rarely enough that the average cost per append, across many appends, works out to O(1). This is what "amortized" means: not every single call is O(1), but the running average is.

numbers = [1, 2, 3]
numbers.append(4)       # amortized O(1) - usually just writes into spare capacity
numbers.insert(0, 0)   # O(n) - every existing element shifts right by one slot

Time complexity: append is amortized O(1); insert(0, x) is O(n) because every one of the n existing elements must move over to make room at index 0. Space complexity: O(1) extra for append (ignoring the rare reallocation); O(1) extra for insert (the shift happens in place).

If you need frequent insertions and removals at both ends, reach for collections.deque instead of a plain list — it gives O(1) operations at both the front and back, at the cost of O(n) random-access indexing in the middle. We'll use it again in the Queue lesson.

2D Lists (List of Lists)

Python has no native multidimensional array type for plain lists — a "2D array" is simply a list where each element is itself a list. The one classic pitfall: never build one with [[0] * cols] * rows — that repeats the same inner list object by reference, so mutating one row mutates every row.

# Wrong: all 3 rows are the SAME list object
grid_buggy = [[0] * 3] * 3

# Correct: a fresh list is built for every row
grid = [[0] * 3 for _ in range(3)]
grid[1][2] = 5  # only row 1 changes

Time complexity: O(rows · cols) to build the grid — every cell is initialized once. Space complexity: O(rows · cols) — that many integers are stored, one per cell.

Worked Example: Reversing a List In Place with Two Pointers

Python already provides list.reverse() and slicing (items[::-1]), but interviewers usually want to see you derive the two-pointer technique by hand — it's the foundation for a large family of array problems (palindrome checks, partitioning, sorting variants).

def reverse_in_place(items):
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1
    return items

Time complexity: O(n) — the two pointers meet in the middle after roughly n/2 swaps, and each swap is O(1). Space complexity: O(1) — the list is reversed in place, using only the two index variables as extra memory.

When the array Module Matters

A plain Python list stores pointers to arbitrary objects, which is flexible but memory-heavy for large numeric datasets. The built-in array module gives you a genuinely fixed-type, packed array (all elements the same primitive type, like C's int[]), which uses far less memory for millions of numbers. It's rarely needed for interview problems — but if you're asked "how would you reduce memory usage for a huge list of integers," this is the honest answer, alongside libraries like NumPy for numerical workloads.

import array
packed = array.array('i', [1, 2, 3])  # 'i' = signed int, fixed-type storage

Time complexity: O(n) to build from an existing sequence of n elements — each element is copied into the packed buffer once. Space complexity: O(n) but with a much smaller constant factor than a plain list of ints, since no per-element object overhead or pointer indirection is stored.

Next: Strings look like a sequence type too, but Python's immutability rule changes the complexity story completely — see Strings Basics.

Prev Next