Python Lists: A Definitive Guide

Performance: What Every Operation Costs

Python lists are implemented as dynamic arrays — a contiguous block of memory holding references to objects. This gives fast random access by index but makes some operations expensive. Knowing the cost of each operation prevents the most common performance mistakes.

copy# Performance implications — demonstrated with collections.deque
from collections import deque
import time

N = 100_000

# Building a list by prepending to front — O(n) per insert = O(n^2) total
start = time.perf_counter()
lst = []
for i in range(N):
    lst.insert(0, i)    # shifts all existing elements right every time
list_prepend = time.perf_counter() - start

# deque — O(1) appendleft, the right tool for front insertions
start = time.perf_counter()
dq = deque()
for i in range(N):
    dq.appendleft(i)
deque_prepend = time.perf_counter() - start

print(f"Prepending {N:,} items:")
print(f"  list.insert(0, x) : {list_prepend:.4f}s")
print(f"  deque.appendleft  : {deque_prepend:.4f}s")
print(f"  deque is ~{list_prepend / deque_prepend:.0f}x faster for front insertions")

# Membership test: list O(n) vs set O(1)
import random
data    = list(range(N))
data_set = set(data)
targets = [random.randint(0, N*2) for _ in range(1000)]

start = time.perf_counter()
results_list = [t in data for t in targets]
list_time = time.perf_counter() - start

start = time.perf_counter()
results_set = [t in data_set for t in targets]
set_time = time.perf_counter() - start

print(f"\nMembership test (1,000 lookups in {N:,} items):")
print(f"  list : {list_time:.4f}s")
print(f"  set  : {set_time:.4f}s")

Copying Lists — Shallow vs Deep

When you assign one list to another variable, you get a second name pointing at the same object — not a copy. Making an actual copy requires one of three approaches, and the choice between them depends on whether your list contains nested mutable objects.

copyimport copy

original = [[1, 2], [3, 4], [5, 6]]

# Assignment — NOT a copy
alias = original
alias[0].append(99)
print(f"alias assignment  : original={original}")   # original mutated

# Shallow copy — new list, same inner objects
original2 = [[1, 2], [3, 4], [5, 6]]
shallow = original2.copy()        # or original2[:]  or list(original2)

shallow[0].append(99)             # mutates the shared inner list
shallow.append([7, 8])            # only affects shallow

print(f"\nAfter shallow[0].append(99) and shallow.append([7,8]):")
print(f"  original2 : {original2}")   # inner list [1,2] changed
print(f"  shallow   : {shallow}")

# Deep copy — new list AND new inner objects
original3 = [[1, 2], [3, 4], [5, 6]]
deep = copy.deepcopy(original3)

deep[0].append(99)                # only affects deep

print(f"\nAfter deep[0].append(99):")
print(f"  original3 : {original3}")   # untouched
print(f"  deep      : {deep}")

# Three ways to shallow copy — all equivalent
lst = [10, 20, 30]
c1  = lst.copy()
c2  = lst[:]
c3  = list(lst)
print(f"\nThree shallow copies equal: {c1 == c2 == c3}")
print(f"All different objects     : {c1 is not c2 is not c3 is not lst}")

Iterating — Patterns and Pitfalls

Python gives you several ways to iterate over a list. Each pattern is suited to different needs, and there is one rule that applies to all of them: never modify the list you are iterating over.

copyproducts = ["Widget A", "Widget B", "Gadget X", "Gadget Y", "Doohickey"]

# Plain iteration — when you only need the value
print("Plain for loop:")
for p in products:
    print(f"  {p}")

# enumerate() — when you need index AND value
print("\nenumerate():")
for i, p in enumerate(products):
    print(f"  [{i}] {p}")

# enumerate() with a start index
print("\nenumerate(start=1):")
for i, p in enumerate(products, start=1):
    print(f"  {i}. {p}")

# zip() — iterate two lists in parallel
prices = [4.99, 12.50, 89.00, 34.75, 2.25]
print("\nzip() — parallel lists:")
for name, price in zip(products, prices):
    print(f"  {name:<12}  ${price:.2f}")

# PITFALL: modifying a list while iterating skips elements
nums = [1, 2, 3, 4, 5, 6]
print(f"\nBefore removal: {nums}")

# Wrong — skips elements because indices shift after removal
for n in nums[:]:   # iterate over a copy instead
    if n % 2 == 0:
        nums.remove(n)
print(f"After removing evens (copy iteration): {nums}")

# Better: build a new list
nums2   = [1, 2, 3, 4, 5, 6]
odds    = [n for n in nums2 if n % 2 != 0]
print(f"Comprehension filter (original unchanged): {odds}")

List Comprehensions

A list comprehension is a concise way to build a new list from an existing iterable, with an optional filter. The syntax is [expression for item in iterable if condition]. Comprehensions are not just shorter — they run faster than equivalent for loops because the iteration is handled in C internally.

copy# Basic transformation
squares = [x ** 2 for x in range(1, 8)]
print(f"squares     : {squares}")

# With filter
evens = [x for x in range(20) if x % 2 == 0]
print(f"evens 0-18  : {evens}")

# Combined transform + filter
even_squares = [x**2 for x in range(10) if x % 2 == 0]
print(f"even squares: {even_squares}")

# String processing
words    = ["  hello ", "WORLD", "  Python  ", "code"]
cleaned  = [w.strip().lower() for w in words]
print(f"\ncleaned     : {cleaned}")

# Nested comprehension — flatten a 2D list
matrix  = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat    = [val for row in matrix for val in row]
print(f"flat matrix : {flat}")

# Conditional expression (ternary) inside comprehension
scores  = [45, 88, 72, 55, 91, 60]
grades  = ["pass" if s >= 60 else "fail" for s in scores]
print(f"\nscores : {scores}")
print(f"grades : {grades}")

# Comprehension vs for loop — demonstrating speed difference
import time

N = 500_000

start = time.perf_counter()
result_loop = []
for i in range(N):
    result_loop.append(i * 2)
loop_time = time.perf_counter() - start

start = time.perf_counter()
result_comp = [i * 2 for i in range(N)]
comp_time = time.perf_counter() - start

print(f"\nBuilding {N:,} items:")
print(f"  for loop      : {loop_time:.4f}s")
print(f"  comprehension : {comp_time:.4f}s")
print(f"  speedup       : {loop_time / comp_time:.1f}x")

Sorting — sort() vs sorted(), keys, and stability

Python provides two sorting tools. list.sort() sorts the list in place and returns None. sorted(iterable) returns a new sorted list and works on any iterable. Both use Timsort — a stable, adaptive algorithm that runs in O(n log n) worst case.

copy# sort() — in-place, returns None
nums = [5, 2, 8, 1, 9, 3]
nums.sort()
print(f"sort() ascending  : {nums}")

nums.sort(reverse=True)
print(f"sort() descending : {nums}")

# sorted() — returns new list, original unchanged
original = [5, 2, 8, 1, 9, 3]
result   = sorted(original)
print(f"\nsorted() result   : {result}")
print(f"original unchanged: {original}")

# TRAP: sort() returns None — don't assign it
wrong = nums.sort()   # wrong is None!
print(f"\nwrong = nums.sort() -> {wrong}")   # None

# Sorting with key= — transform each element for comparison
words = ["banana", "fig", "apple", "elderberry", "cherry", "date"]

by_length  = sorted(words, key=len)
by_last    = sorted(words, key=lambda w: w[-1])
by_length_then_alpha = sorted(words, key=lambda w: (len(w), w))

print(f"\nby length                   : {by_length}")
print(f"by last character           : {by_last}")
print(f"by length then alphabetical : {by_length_then_alpha}")

# Sorting complex objects
employees = [
    {"name": "Alice",   "dept": "Engineering", "salary": 95000},
    {"name": "Bob",     "dept": "Marketing",   "salary": 72000},
    {"name": "Carol",   "dept": "Engineering", "salary": 88000},
    {"name": "David",   "dept": "Marketing",   "salary": 79000},
    {"name": "Eve",     "dept": "Engineering", "salary": 88000},
]

# Sort by salary descending, then name ascending
employees.sort(key=lambda e: (-e["salary"], e["name"]))
print("\nEmployees by salary desc, name asc:")
for e in employees:
    print(f"  {e['name']:<8}  {e['dept']:<15}  ${e['salary']:,}")

# Stability: equal keys preserve original order
# Carol and Eve both have salary=88000 — after sort, Carol appears before Eve
# because C comes before E alphabetically (our secondary key ensures this)

copy# 3x4 grid of zeros — built correctly with comprehension
ROWS, COLS = 3, 4
grid = [[0] * COLS for _ in range(ROWS)]

# Set some values
grid[0][0] = 1
grid[1][2] = 7
grid[2][3] = 9

print("Grid:")
for row in grid:
    print(f"  {row}")

# Access element by [row][col]
print(f"\ngrid[1][2] = {grid[1][2]}")

# Transpose — rows become columns
transposed = [[grid[r][c] for r in range(ROWS)] for c in range(COLS)]
print(f"\nTransposed ({COLS}x{ROWS}):")
for row in transposed:
    print(f"  {row}")

# Flattening with comprehension vs sum()
nested = [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
flat_comp = [x for sublist in nested for x in sublist]
flat_sum  = sum(nested, [])   # works but O(n^2) for large inputs — avoid

print(f"\nflattened (comprehension) : {flat_comp}")
print(f"flattened (sum trick)     : {flat_sum}")

# Real-world pattern: list of dicts acting as a table
inventory = [
    {"sku": "W001", "name": "Widget A",  "stock": 37, "price": 4.99},
    {"sku": "W002", "name": "Widget B",  "stock": 27, "price": 12.50},
    {"sku": "G001", "name": "Gadget X",  "stock": 12, "price": 97.90},
    {"sku": "G002", "name": "Gadget Y",  "stock": 18, "price": 34.75},
    {"sku": "D001", "name": "Doohickey", "stock":  2, "price":  2.25},
]

# Filter and project — like SELECT WHERE in SQL
cheap_in_stock = [
    {"sku": item["sku"], "name": item["name"]}
    for item in inventory
    if item["price"] < 20 and item["stock"] > 0
]
print(f"\nCheap items in stock:")
for item in cheap_in_stock:
    print(f"  {item['sku']}  {item['name']}")