|$ curl https://forge-ai.dev/api/markdown?path=docs/python/lists
$cat docs/python-—-lists-deep-dive.md
updated Recently·18 min read·published
Python — Lists Deep Dive
◆Python◆Beginner to Intermediate
Introduction
Lists are Python's most versatile sequence type. They are ordered, mutable, and can hold elements of mixed types. Under the hood, lists are dynamic arrays that provide O(1) amortized append and O(n) insert/delete in the middle. This guide covers everything from basic creation to advanced patterns, performance characteristics, and common pitfalls.
Creation
Python provides multiple ways to create lists. Choosing the right one depends on whether you know the elements upfront, are converting from another iterable, or need a computed sequence.
Literal Syntax
creation_literal.py
Python
| 1 | # Empty list |
| 2 | empty = [] |
| 3 | print(empty) # [] |
| 4 | |
| 5 | # Homogeneous |
| 6 | nums = [1, 2, 3, 4, 5] |
| 7 | |
| 8 | # Heterogeneous |
| 9 | mixed = [1, "hello", 3.14, True, None] |
| 10 | |
| 11 | # Nested |
| 12 | matrix = [[1, 2], [3, 4, 5]] |
| 13 | print(matrix[0][1]) # 2 |
| 14 | |
| 15 | # Repeated elements |
| 16 | zeros = [0] * 5 # [0, 0, 0, 0, 0] |
| 17 | pattern = [1, 2] * 3 # [1, 2, 1, 2, 1, 2] |
The list() Constructor
creation_list_constructor.py
Python
| 1 | # From any iterable |
| 2 | print(list("abc")) # ['a', 'b', 'c'] |
| 3 | print(list((1, 2, 3))) # [1, 2, 3] (tuple -> list) |
| 4 | print(list({4, 5, 6})) # [4, 5, 6] (set -> list, order not guaranteed) |
| 5 | print(list({"a": 1, "b": 2})) # ['a', 'b'] (dict -> keys) |
| 6 | |
| 7 | # Create an empty list |
| 8 | empty = list() |
| 9 | print(empty) # [] |
range()
creation_range.py
Python
| 1 | # range(start, stop, step) — lazy, memory efficient |
| 2 | r = range(5) # range(0, 5) |
| 3 | print(list(r)) # [0, 1, 2, 3, 4] |
| 4 | |
| 5 | print(list(range(2, 8))) # [2, 3, 4, 5, 6, 7] |
| 6 | print(list(range(0, 10, 2))) # [0, 2, 4, 6, 8] |
| 7 | print(list(range(10, 0, -2))) # [10, 8, 6, 4, 2] |
| 8 | |
| 9 | # range is not a list — it's a lightweight sequence |
| 10 | print(type(r)) # <class 'range'> |
| 11 | print(len(r)) # 5 |
| 12 | print(3 in r) # True |
| 13 | print(r[2]) # 2 (indexing supported) |
str.split()
creation_split.py
Python
| 1 | # Split a string into a list of substrings |
| 2 | text = "one two three four" |
| 3 | words = text.split() |
| 4 | print(words) # ['one', 'two', 'three', 'four'] |
| 5 | |
| 6 | # Custom delimiter |
| 7 | csv = "a,b,c,d" |
| 8 | print(csv.split(",")) # ['a', 'b', 'c', 'd'] |
| 9 | |
| 10 | # Limit splits |
| 11 | print(csv.split(",", 2)) # ['a', 'b', 'c,d'] |
| 12 | |
| 13 | # Split on whitespace (handles multiple spaces) |
| 14 | messy = "one two\tthree\nfour" |
| 15 | print(messy.split()) # ['one', 'two', 'three', 'four'] |
| 16 | |
| 17 | # splitlines — split on newlines |
| 18 | block = "line1\nline2\nline3" |
| 19 | print(block.splitlines()) # ['line1', 'line2', 'line3'] |
List Comprehension
creation_comprehension.py
Python
| 1 | # Quick creation computed from an iterable |
| 2 | squares = [x**2 for x in range(10)] |
| 3 | print(squares) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] |
| 4 | |
| 5 | # Filtered |
| 6 | evens = [x for x in range(20) if x % 2 == 0] |
Indexing
Python uses zero-based indexing. Negative indices count from the end of the list, making it easy to access the last elements without computing the length.
indexing.py
Python
| 1 | nums = [10, 20, 30, 40, 50] |
| 2 | |
| 3 | # Positive indexing (0-based) |
| 4 | print(nums[0]) # 10 (first element) |
| 5 | print(nums[1]) # 20 |
| 6 | print(nums[4]) # 50 (last element) |
| 7 | |
| 8 | # Negative indexing (from the end) |
| 9 | print(nums[-1]) # 50 (last element) |
| 10 | print(nums[-2]) # 40 |
| 11 | print(nums[-5]) # 10 (first element) |
| 12 | |
| 13 | # IndexError for out-of-range |
| 14 | # nums[5] # IndexError: list index out of range |
| 15 | # nums[-6] # IndexError: list index out of range |
| 16 | |
| 17 | # Assignment by index |
| 18 | nums[0] = 100 |
| 19 | print(nums) # [100, 20, 30, 40, 50] |
| 20 | |
| 21 | # Nested indexing |
| 22 | matrix = [[1, 2], [3, 4]] |
| 23 | print(matrix[0][1]) # 2 |
| Expression | Result | Explanation |
|---|---|---|
| nums[0] | 10 | First element |
| nums[-1] | 50 | Last element |
| nums[-2] | 40 | Second from last |
Slicing
Slicing extracts sublists using the [start:stop:step] syntax. The start index is inclusive, stop is exclusive. Omitting start defaults to 0, omitting stop defaults to the list length. Slicing never raises IndexError — out-of-range indices are silently clamped.
slicing.py
Python
| 1 | nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
| 2 | |
| 3 | # Basic slicing [start:stop] |
| 4 | print(nums[2:6]) # [2, 3, 4, 5] |
| 5 | print(nums[:4]) # [0, 1, 2, 3] (start = 0) |
| 6 | print(nums[6:]) # [6, 7, 8, 9] (stop = end) |
| 7 | print(nums[:]) # full shallow copy |
| 8 | |
| 9 | # Step [start:stop:step] |
| 10 | print(nums[::2]) # [0, 2, 4, 6, 8] (every 2nd) |
| 11 | print(nums[1::2]) # [1, 3, 5, 7, 9] (every 2nd from index 1) |
| 12 | print(nums[2:8:3]) # [2, 5] (step 3 from 2 to 7) |
| 13 | |
| 14 | # Negative indices in slices |
| 15 | print(nums[-5:-2]) # [5, 6, 7] (from -5 to -3) |
| 16 | print(nums[-3:]) # [7, 8, 9] (last 3) |
| 17 | print(nums[:-3]) # [0, 1, 2, 3, 4, 5, 6] (all but last 3) |
| 18 | |
| 19 | # Reverse with negative step |
| 20 | print(nums[::-1]) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] |
| 21 | |
| 22 | # Negative step with bounds |
| 23 | print(nums[8:2:-2]) # [8, 6, 4] (step -2 from 8 down to 3) |
| 24 | |
| 25 | # Slice assignment — replace a slice in-place |
| 26 | nums[3:6] = [30, 40, 50] |
| 27 | print(nums) # [0, 1, 2, 30, 40, 50, 6, 7, 8, 9] |
| 28 | |
| 29 | # Insert with empty slice |
| 30 | nums[3:3] = [99] # insert at index 3 |
| 31 | print(nums) # [0, 1, 2, 99, 30, 40, 50, 6, 7, 8, 9] |
| 32 | |
| 33 | # Delete with slice assignment |
| 34 | nums[3:4] = [] # remove index 3 |
| 35 | print(nums) # back to [0, 1, 2, 30, 40, 50, 6, 7, 8, 9] |
| 36 | |
| 37 | # Clear entire list |
| 38 | nums[:] = [] # nums now empty |
ℹ
info
Slice assignments let you replace, insert, or delete elements without creating a new list. This is efficient because it operates in-place on the underlying array.
Methods
Python lists expose a rich set of methods for adding, removing, finding, and rearranging elements. Most methods operate in-place and return None (a common source of bugs for beginners expecting a new list back).
Adding Elements
methods_add.py
Python
| 1 | nums = [1, 2, 3] |
| 2 | |
| 3 | # append(x) — add to end, O(1) amortized |
| 4 | nums.append(4) |
| 5 | print(nums) # [1, 2, 3, 4] |
| 6 | |
| 7 | # extend(iterable) — merge another iterable, O(k) |
| 8 | nums.extend([5, 6, 7]) |
| 9 | print(nums) # [1, 2, 3, 4, 5, 6, 7] |
| 10 | |
| 11 | # insert(i, x) — insert at position, O(n) |
| 12 | nums.insert(0, 0) # insert at front |
| 13 | print(nums) # [0, 1, 2, 3, 4, 5, 6, 7] |
| 14 | |
| 15 | nums.insert(4, 99) # insert at index 4 |
| 16 | print(nums) # [0, 1, 2, 99, 3, 4, 5, 6, 7] |
| 17 | |
| 18 | # insert beyond end appends |
| 19 | nums.insert(100, 100) |
| 20 | print(nums) # ... 100 at the end |
| 21 | |
| 22 | # WARNING: append vs extend difference |
| 23 | nums.append([8, 9]) # adds as single element! |
| 24 | print(nums) # [..., [8, 9]] (not what you want usually) |
| 25 | nums.pop() # undo |
| 26 | |
| 27 | nums.extend([8, 9]) # adds each element |
| 28 | print(nums) # [..., 8, 9] |
✓
best practice
Use extend() to merge lists. Using append() in a loop is fine (amortized O(1)). Avoid insert(0, x) on large lists — it's O(n) and shifts every element.
Removing Elements
methods_remove.py
Python
| 1 | nums = [1, 2, 3, 2, 4, 2, 5] |
| 2 | |
| 3 | # remove(x) — remove first occurrence of x, O(n) |
| 4 | nums.remove(2) # removes the first 2 |
| 5 | print(nums) # [1, 3, 2, 4, 2, 5] |
| 6 | |
| 7 | # ValueError if not found |
| 8 | # nums.remove(99) # ValueError: list.remove(x): x not in list |
| 9 | |
| 10 | # pop(i) — remove & return element at index i, O(n) for non-end |
| 11 | last = nums.pop() # remove & return last element |
| 12 | print(last) # 5 |
| 13 | print(nums) # [1, 3, 2, 4, 2] |
| 14 | |
| 15 | first = nums.pop(0) # remove & return index 0 — O(n) |
| 16 | print(first) # 1 |
| 17 | print(nums) # [3, 2, 4, 2] |
| 18 | |
| 19 | # clear() — remove all elements, O(n) |
| 20 | nums.clear() |
| 21 | print(nums) # [] |
| 22 | |
| 23 | # clear via slice assignment |
| 24 | nums[:] = [] # equivalent to clear |
Finding Elements
methods_find.py
Python
| 1 | nums = [10, 20, 30, 20, 40, 20, 50] |
| 2 | |
| 3 | # index(x) — index of first occurrence, O(n) |
| 4 | print(nums.index(20)) # 1 |
| 5 | print(nums.index(20, 2)) # 3 (search from index 2 onward) |
| 6 | print(nums.index(20, 4, 6)) # 5 (search between indices 4-5) |
| 7 | |
| 8 | # ValueError if not found |
| 9 | # nums.index(99) # ValueError: 99 is not in list |
| 10 | |
| 11 | # count(x) — how many times x appears, O(n) |
| 12 | print(nums.count(20)) # 3 |
| 13 | print(nums.count(99)) # 0 (not found, no error) |
| 14 | |
| 15 | # in / not in — membership test, O(n) |
| 16 | print(20 in nums) # True |
| 17 | print(99 in nums) # False |
| 18 | print(99 not in nums) # True |
Ordering & Reversal
methods_order.py
Python
| 1 | nums = [3, 1, 4, 1, 5, 9, 2, 6] |
| 2 | |
| 3 | # sort() — ascending in-place, O(n log n) Timsort |
| 4 | nums.sort() |
| 5 | print(nums) # [1, 1, 2, 3, 4, 5, 6, 9] |
| 6 | |
| 7 | # sort(reverse=True) — descending in-place |
| 8 | nums.sort(reverse=True) |
| 9 | print(nums) # [9, 6, 5, 4, 3, 2, 1, 1] |
| 10 | |
| 11 | # sort with key function |
| 12 | words = ["banana", "apple", "cherry", "date"] |
| 13 | words.sort(key=len) # sort by length |
| 14 | print(words) # ['date', 'apple', 'banana', 'cherry'] |
| 15 | |
| 16 | words.sort(key=lambda w: w[-1]) # sort by last character |
| 17 | print(words) # ['banana', 'apple', 'date', 'cherry'] |
| 18 | |
| 19 | # reverse() — reverse in-place, O(n) |
| 20 | nums.reverse() |
| 21 | print(nums) # back to [1, 1, 2, 3, 4, 5, 6, 9] |
| 22 | |
| 23 | # sorted() — returns a NEW sorted list (does not modify original) |
| 24 | original = [3, 1, 4, 1, 5] |
| 25 | new_list = sorted(original) |
| 26 | print(original) # [3, 1, 4, 1, 5] (unchanged) |
| 27 | print(new_list) # [1, 1, 3, 4, 5] |
| 28 | |
| 29 | # reversed() — returns an iterator over reversed elements |
| 30 | print(list(reversed(original))) # [5, 1, 4, 1, 3] |
Copying
methods_copy.py
Python
| 1 | # copy() — shallow copy |
| 2 | original = [1, 2, 3] |
| 3 | shallow = original.copy() |
| 4 | shallow[0] = 99 |
| 5 | print(original) # [1, 2, 3] (original unaffected) |
| 6 | print(shallow) # [99, 2, 3] |
| 7 | |
| 8 | # Equivalent shallow copies |
| 9 | copy1 = original[:] |
| 10 | copy2 = list(original) |
| 11 | import copy |
| 12 | copy3 = copy.copy(original) |
| 13 | |
| 14 | # Deep copy for nested structures |
| 15 | nested = [[1, 2], [3, 4]] |
| 16 | shallow_copy = nested.copy() |
| 17 | shallow_copy[0][0] = 99 |
| 18 | print(nested) # [[99, 2], [3, 4]] — modified! (shared reference) |
| 19 | |
| 20 | deep_copy = copy.deepcopy(nested) |
| 21 | deep_copy[0][0] = 999 |
| 22 | print(nested) # [[99, 2], [3, 4]] — unchanged |
| 23 | print(deep_copy) # [[999, 2], [3, 4]] |
⚠
warning
copy(), [:], and list() all perform shallow copies. For nested lists containing mutable objects, use copy.deepcopy() to avoid unintended shared references.
List as Stack / Queue
Python lists can serve as stacks (LIFO) and queues (FIFO), though list is far better suited for stack operations. For efficient queue operations, use collections.deque.
Stack (LIFO) — O(1) per operation
stack.py
Python
| 1 | # Stack: append() for push, pop() for pop (both O(1)) |
| 2 | stack = [] |
| 3 | stack.append(1) |
| 4 | stack.append(2) |
| 5 | stack.append(3) |
| 6 | print(stack) # [1, 2, 3] |
| 7 | |
| 8 | top = stack.pop() |
| 9 | print(top) # 3 |
| 10 | print(stack) # [1, 2] |
| 11 | |
| 12 | top = stack.pop() |
| 13 | print(top) # 2 |
| 14 | |
| 15 | print(len(stack) == 0) # False — one element remains |
| 16 | print(not stack) # False — stack is not empty |
| 17 | |
| 18 | # Peek at top without popping |
| 19 | if stack: |
| 20 | print(stack[-1]) # 1 |
Queue (FIFO) — list is inefficient
queue.py
Python
| 1 | # BAD: list.pop(0) is O(n) — shifts all elements |
| 2 | queue = [] |
| 3 | queue.append(1) |
| 4 | queue.append(2) |
| 5 | queue.append(3) |
| 6 | first = queue.pop(0) # O(n) — don't do this for large queues! |
| 7 | print(first) # 1 |
| 8 | |
| 9 | # GOOD: use collections.deque for O(1) popleft |
| 10 | from collections import deque |
| 11 | |
| 12 | dq = deque() |
| 13 | dq.append(1) # enqueue right |
| 14 | dq.append(2) |
| 15 | dq.append(3) |
| 16 | |
| 17 | first = dq.popleft() # O(1) dequeue left |
| 18 | print(first) # 1 |
| 19 | print(dq) # deque([2, 3]) |
| 20 | |
| 21 | # deque also supports appendleft / pop for symmetry |
| 22 | dq.appendleft(0) # O(1) push left |
| 23 | print(dq) # deque([0, 2, 3]) |
| 24 | last = dq.pop() # O(1) pop right |
| 25 | print(last) # 3 |
| 26 | |
| 27 | # deque as bounded queue (drops oldest when full) |
| 28 | bounded = deque(maxlen=3) |
| 29 | for i in range(5): |
| 30 | bounded.append(i) |
| 31 | print(list(bounded)) |
| 32 | # [0] |
| 33 | # [0, 1] |
| 34 | # [0, 1, 2] |
| 35 | # [1, 2, 3] (0 dropped) |
| 36 | # [2, 3, 4] (1 dropped) |
✓
best practice
Use list as a stack (append/pop). For queues, prefer collections.deque — it provides O(1) appends and pops from both ends. Never use list.pop(0) on large lists.
Copying — Shallow vs Deep
Understanding the difference between shallow and deep copies is critical when working with nested lists. A shallow copy creates a new list but the elements themselves are still references to the same objects. A deep copy recursively copies all nested objects.
copying.py
Python
| 1 | import copy |
| 2 | |
| 3 | # Shallow copy — references shared |
| 4 | nested = [[1, 2], [3, 4], [5, 6]] |
| 5 | |
| 6 | # All of these create shallow copies: |
| 7 | shallow1 = nested.copy() |
| 8 | shallow2 = nested[:] |
| 9 | shallow3 = list(nested) |
| 10 | shallow4 = copy.copy(nested) |
| 11 | |
| 12 | shallow1[0][0] = 99 |
| 13 | print(nested) # [[99, 2], [3, 4], [5, 6]] — unexpected mutation! |
| 14 | |
| 15 | # Deep copy — fully independent |
| 16 | deep = copy.deepcopy(nested) |
| 17 | deep[0][0] = 999 |
| 18 | print(nested) # [[99, 2], [3, 4], [5, 6]] — unaffected |
| 19 | print(deep) # [[999, 2], [3, 4], [5, 6]] |
| 20 | |
| 21 | # Shallow copy with flat list is fine |
| 22 | flat = [1, 2, 3] |
| 23 | c = flat.copy() |
| 24 | c[0] = 99 |
| 25 | print(flat) # [1, 2, 3] — fine, ints are immutable |
| 26 | |
| 27 | # Deep copy also handles cycles, custom objects |
| 28 | class Point: |
| 29 | def __init__(self, x, y): |
| 30 | self.x, self.y = x, y |
| 31 | def __repr__(self): |
| 32 | return f"Point({self.x}, {self.y})" |
| 33 | |
| 34 | pts = [Point(1, 2), Point(3, 4)] |
| 35 | pts_copy = copy.deepcopy(pts) |
| 36 | pts_copy[0].x = 99 |
| 37 | print(pts) # [Point(1, 2), Point(3, 4)] — unaffected |
ℹ
info
Rule of thumb: if your list only contains immutable elements (int, float, str, bool, tuple), a shallow copy is sufficient. If it contains mutable objects (other lists, dicts, custom objects), you likely need a deep copy.
List Comprehensions
List comprehensions provide a concise way to create lists by transforming and filtering elements from an iterable. They are more Pythonic and faster than equivalent for loops with append().
Basic Syntax
comprehension_basic.py
Python
| 1 | # [expression for item in iterable] |
| 2 | squares = [x**2 for x in range(10)] |
| 3 | print(squares) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] |
| 4 | |
| 5 | # Equivalent for loop — more verbose |
| 6 | squares_loop = [] |
| 7 | for x in range(10): |
| 8 | squares_loop.append(x**2) |
With Condition
comprehension_condition.py
Python
| 1 | # [expression for item in iterable if condition] |
| 2 | evens = [x for x in range(20) if x % 2 == 0] |
| 3 | print(evens) # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] |
| 4 | |
| 5 | # Odd numbers, squared |
| 6 | odd_squares = [x**2 for x in range(10) if x % 2 != 0] |
| 7 | print(odd_squares) # [1, 9, 25, 49, 81] |
| 8 | |
| 9 | # Filter with function call |
| 10 | texts = ["hello", "", "world", "", "python"] |
| 11 | non_empty = [t for t in texts if t] |
| 12 | print(non_empty) # ['hello', 'world', 'python'] |
| 13 | |
| 14 | # Filter with multiple conditions |
| 15 | nums = [x for x in range(50) if x % 3 == 0 if x % 5 == 0] |
| 16 | print(nums) # [0, 15, 30, 45] — divisible by both 3 and 5 |
Nested Comprehensions
comprehension_nested.py
Python
| 1 | # Flatten a matrix (row-major) |
| 2 | matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] |
| 3 | flat = [x for row in matrix for x in row] |
| 4 | print(flat) # [1, 2, 3, 4, 5, 6, 7, 8, 9] |
| 5 | |
| 6 | # Read nested for comprehension as: |
| 7 | # for row in matrix: |
| 8 | # for x in row: |
| 9 | # result.append(x) |
| 10 | |
| 11 | # Transpose a matrix |
| 12 | transposed = [[row[i] for row in matrix] for i in range(3)] |
| 13 | print(transposed) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]] |
| 14 | |
| 15 | # Cartesian product |
| 16 | colors = ["red", "green"] |
| 17 | sizes = ["S", "M", "L"] |
| 18 | products = [(c, s) for c in colors for s in sizes] |
| 19 | print(products) |
| 20 | # [('red', 'S'), ('red', 'M'), ('red', 'L'), |
| 21 | # ('green', 'S'), ('green', 'M'), ('green', 'L')] |
With if-else (Ternary)
comprehension_ifelse.py
Python
| 1 | # if-else goes BEFORE the for (acts as a ternary on the value) |
| 2 | evens_odds = ["even" if x % 2 == 0 else "odd" for x in range(6)] |
| 3 | print(evens_odds) # ['even', 'odd', 'even', 'odd', 'even', 'odd'] |
| 4 | |
| 5 | # Compare: if-only AFTER the for (filters) |
| 6 | filtered = [x for x in range(6) if x % 2 == 0] |
| 7 | print(filtered) # [0, 2, 4] |
| 8 | |
| 9 | # Complex transformation with ternary |
| 10 | nums = [-5, 3, -2, 8, -1] |
| 11 | absolute = [n if n >= 0 else -n for n in nums] |
| 12 | print(absolute) # [5, 3, 2, 8, 1] |
| 13 | |
| 14 | # Multiple conditionals |
| 15 | labels = [ |
| 16 | "positive" if x > 0 |
| 17 | else "negative" if x < 0 |
| 18 | else "zero" |
| 19 | for x in range(-2, 3) |
| 20 | ] |
| 21 | print(labels) # ['negative', 'negative', 'zero', 'positive', 'positive'] |
ℹ
info
The if after the for filters elements. The if-else before the for transforms each element. Mixing them up is a common mistake.
Sorting
Python offers two sorting approaches: the list.sort() method (in-place) and the sorted() built-in function (returns a new list). Both use Timsort — a stable, adaptive, O(n log n) algorithm derived from merge sort and insertion sort.
sorting.py
Python
| 1 | # list.sort() — modifies original, returns None |
| 2 | nums = [4, 2, 9, 1, 5] |
| 3 | result = nums.sort() |
| 4 | print(nums) # [1, 2, 4, 5, 9] |
| 5 | print(result) # None (common pitfall!) |
| 6 | |
| 7 | # sorted() — returns new sorted list |
| 8 | original = [4, 2, 9, 1, 5] |
| 9 | new = sorted(original) |
| 10 | print(original) # [4, 2, 9, 1, 5] (unchanged) |
| 11 | print(new) # [1, 2, 4, 5, 9] |
| 12 | |
| 13 | # Reverse order |
| 14 | nums.sort(reverse=True) |
| 15 | print(nums) # [9, 5, 4, 2, 1] |
| 16 | |
| 17 | # sorted with reverse |
| 18 | print(sorted(original, reverse=True)) # [9, 5, 4, 2, 1] |
| 19 | |
| 20 | # Sorting with key functions |
| 21 | words = ["banana", "apple", "cherry", "date"] |
| 22 | |
| 23 | # Sort by length |
| 24 | words.sort(key=len) |
| 25 | print(words) # ['date', 'apple', 'banana', 'cherry'] |
| 26 | |
| 27 | # Sort by last character |
| 28 | words.sort(key=lambda w: w[-1]) |
| 29 | print(words) # ['banana', 'apple', 'date', 'cherry'] |
| 30 | |
| 31 | # Sort by multiple criteria: (primary, secondary) |
| 32 | data = [("Alice", 30), ("Bob", 25), ("Alice", 20)] |
| 33 | data.sort(key=lambda x: (x[0], x[1])) |
| 34 | print(data) # [('Alice', 20), ('Alice', 30), ('Bob', 25)] |
| 35 | |
| 36 | # Sort with str.lower for case-insensitive |
| 37 | mixed = ["Banana", "apple", "Cherry", "date"] |
| 38 | mixed.sort(key=str.lower) |
| 39 | print(mixed) # ['apple', 'Banana', 'Cherry', 'date'] |
| 40 | |
| 41 | # operator.itemgetter for cleaner multi-key sorts |
| 42 | from operator import itemgetter |
| 43 | data.sort(key=itemgetter(0, 1)) # same as lambda above |
| 44 | |
| 45 | # Sorting is stable — equal elements keep original order |
| 46 | pairs = [(1, "b"), (2, "a"), (1, "a")] |
| 47 | pairs.sort(key=lambda x: x[0]) # sort only by first element |
| 48 | print(pairs) # [(1, 'b'), (1, 'a'), (2, 'a')] |
| 49 | # The two (1, x) elements maintain their relative order |
✓
best practice
Use sorted() when you need to preserve the original list. Use list.sort() when memory matters and you don't need the original order. Timsort is stable — use this for multi-pass sorts (sort by secondary criterion first, then primary).
Searching
Python provides several ways to search lists, from simple membership tests to the efficient binary search via the bisect module.
Membership: in
search_in.py
Python
| 1 | nums = [10, 20, 30, 40, 50] |
| 2 | |
| 3 | # Linear search — O(n) |
| 4 | print(30 in nums) # True |
| 5 | print(99 in nums) # False |
| 6 | print(99 not in nums) # True |
| 7 | |
| 8 | # Works with any hashable/equatable type |
| 9 | words = ["hello", "world"] |
| 10 | print("hello" in words) # True |
| 11 | |
| 12 | # Membership on large lists is slow — O(n) |
| 13 | # Use a set for O(1) membership checks |
Finding Position: index()
search_index.py
Python
| 1 | nums = [10, 20, 30, 20, 40, 20, 50] |
| 2 | |
| 3 | # First occurrence — O(n) |
| 4 | print(nums.index(20)) # 1 |
| 5 | |
| 6 | # With start argument |
| 7 | print(nums.index(20, 2)) # 3 (search from index 2) |
| 8 | |
| 9 | # With start and stop |
| 10 | print(nums.index(20, 4, 6)) # 5 (search indices 4-5) |
| 11 | |
| 12 | # ValueError if not found — handle gracefully |
| 13 | try: |
| 14 | nums.index(99) |
| 15 | except ValueError: |
| 16 | print("Not found") |
| 17 | |
| 18 | # Safe pattern: check first, then index |
| 19 | if 99 in nums: |
| 20 | print(nums.index(99)) |
Binary Search: bisect
search_bisect.py
Python
| 1 | import bisect |
| 2 | |
| 3 | # bisect works on sorted lists — O(log n) |
| 4 | |
| 5 | nums = [1, 3, 5, 7, 9, 11, 13] |
| 6 | |
| 7 | # bisect_left — insertion point to keep list sorted |
| 8 | # (return first index where x could be inserted) |
| 9 | print(bisect.bisect_left(nums, 6)) # 3 (between 5 and 7) |
| 10 | print(bisect.bisect_left(nums, 5)) # 2 (before existing 5) |
| 11 | |
| 12 | # bisect_right — insertion point after existing matches |
| 13 | print(bisect.bisect_right(nums, 5)) # 3 (after existing 5) |
| 14 | |
| 15 | # bisect (alias for bisect_right) |
| 16 | print(bisect.bisect(nums, 8)) # 4 (between 7 and 9) |
| 17 | |
| 18 | # insort — insert while maintaining sort order |
| 19 | bisect.insort(nums, 6) |
| 20 | print(nums) # [1, 3, 5, 6, 7, 9, 11, 13] |
| 21 | |
| 22 | # insort_left — insert before existing matches |
| 23 | bisect.insort_left(nums, 6) |
| 24 | print(nums) # [1, 3, 5, 6, 6, 7, 9, 11, 13] |
| 25 | |
| 26 | # Practical: find closest value |
| 27 | def find_closest(sorted_list, target): |
| 28 | idx = bisect.bisect_left(sorted_list, target) |
| 29 | if idx == 0: |
| 30 | return sorted_list[0] |
| 31 | if idx == len(sorted_list): |
| 32 | return sorted_list[-1] |
| 33 | before = sorted_list[idx - 1] |
| 34 | after = sorted_list[idx] |
| 35 | return before if (target - before) < (after - target) else after |
| 36 | |
| 37 | grades = [60, 70, 80, 90, 100] |
| 38 | print(find_closest(grades, 73)) # 70 |
| 39 | print(find_closest(grades, 76)) # 80 |
| 40 | print(find_closest(grades, 101)) # 100 |
ℹ
info
Use in for simple membership. Use bisect for binary search on sorted lists — it's O(log n) vs O(n) for linear search. The bisect module also provides insort for inserting into sorted lists efficiently.
Memory & Performance
Python lists are implemented as dynamic arrays (not linked lists). The list stores pointers to PyObject elements in a contiguous block of memory. Understanding the underlying data structure helps explain the performance characteristics.
Dynamic Array Internals
performance_memory.py
Python
| 1 | # Lists overallocate to make appends amortized O(1) |
| 2 | import sys |
| 3 | |
| 4 | nums = [] |
| 5 | prev = 0 |
| 6 | for i in range(10): |
| 7 | nums.append(i) |
| 8 | current = sys.getsizeof(nums) |
| 9 | if current != prev: |
| 10 | print(f"Length {i+1}: {sys.getsizeof(nums)} bytes (capacity increased)") |
| 11 | prev = current |
| 12 | |
| 13 | # Typical output (CPython): |
| 14 | # Length 1: 72 bytes (initial capacity ~4) |
| 15 | # Length 5: 104 bytes (capacity ~8) |
| 16 | # Length 9: 168 bytes (capacity ~16) |
| 17 | # Lists grow by ~12.5% when full |
| 18 | |
| 19 | # Memory per element |
| 20 | nested = [list(range(100)) for _ in range(100)] |
| 21 | print(f"Outer list: {sys.getsizeof(nested)} bytes") |
| 22 | print(f"Inner list: {sys.getsizeof(nested[0])} bytes") |
| 23 | # The outer list stores pointers to the inner lists |
Time Complexity Reference
| Operation | Average | Notes |
|---|---|---|
| lst[i] | O(1) | Direct pointer arithmetic |
| lst.append(x) | O(1)* | Amortized; O(n) when resize needed |
| lst.pop() | O(1) | From end only |
| lst.pop(0) | O(n) | Shifts all elements left |
| lst.insert(0, x) | O(n) | Shifts all elements right |
| lst.remove(x) | O(n) | Find + shift |
| x in lst | O(n) | Linear search |
| lst.sort() | O(n log n) | Timsort |
| lst.extend(t) | O(k) | k = length of iterable |
| lst[i:j] | O(k) | k = slice length |
Performance Tips
performance_tips.py
Python
| 1 | # 1. Pre-allocate when size is known |
| 2 | # BAD: repeated appends |
| 3 | result = [] |
| 4 | for i in range(1000): |
| 5 | result.append(i**2) |
| 6 | |
| 7 | # GOOD: pre-allocate |
| 8 | result = [None] * 1000 |
| 9 | for i in range(1000): |
| 10 | result[i] = i**2 |
| 11 | |
| 12 | # 2. Use list comprehensions instead of loops |
| 13 | # BAD |
| 14 | squares = [] |
| 15 | for x in range(100): |
| 16 | squares.append(x**2) |
| 17 | |
| 18 | # GOOD (2x faster) |
| 19 | squares = [x**2 for x in range(100)] |
| 20 | |
| 21 | # 3. Avoid modifying list while iterating (see pitfalls) |
| 22 | # BAD: modifying during iteration gives wrong results |
| 23 | nums = [1, 2, 3, 4, 5] |
| 24 | for x in nums: |
| 25 | if x % 2 == 0: |
| 26 | nums.remove(x) |
| 27 | print(nums) # Incorrect result |
| 28 | |
| 29 | # GOOD: build a new list |
| 30 | nums = [x for x in nums if x % 2 != 0] |
| 31 | |
| 32 | # 4. Use deque for efficient FIFO |
| 33 | from collections import deque |
| 34 | queue = deque() |
| 35 | queue.append(1) # O(1) |
| 36 | queue.popleft() # O(1) — vs list.pop(0) which is O(n) |
| 37 | |
| 38 | # 5. Membership: set is O(1), list is O(n) |
| 39 | # If you do many membership checks, convert to set once |
| 40 | items = [1, 2, 3, 4, 5] |
| 41 | item_set = set(items) |
| 42 | for _ in range(1000): |
| 43 | if 3 in item_set: # O(1) per check |
| 44 | pass |
Common Pitfalls
Lists seem simple but have several gotchas that trip up even experienced developers. Here are the most common pitfalls and how to avoid them.
Modifying While Iterating
pitfalls_modify_while_iter.py
Python
| 1 | # PITFALL: Removing elements while iterating with for |
| 2 | nums = [1, 2, 3, 4, 5, 6] |
| 3 | for x in nums: |
| 4 | if x % 2 == 0: |
| 5 | nums.remove(x) |
| 6 | print(nums) # [1, 3, 5] — wrong! 4 and 6 are still there |
| 7 | # Explanation: when you remove at index i, elements shift left, |
| 8 | # the iterator moves to i+1, skipping the element that moved into i |
| 9 | |
| 10 | # PITFALL: Same problem with insert |
| 11 | words = ["a", "b", "c"] |
| 12 | for w in words: |
| 13 | if w == "b": |
| 14 | words.insert(0, "z") |
| 15 | print(words) # Infinite loop or unexpected result |
| 16 | |
| 17 | # SOLUTION 1: Iterate over a copy |
| 18 | for x in nums[:]: # iterate over a copy |
| 19 | if x % 2 == 0: |
| 20 | nums.remove(x) |
| 21 | |
| 22 | # SOLUTION 2: Build a new list (most Pythonic) |
| 23 | nums = [1, 2, 3, 4, 5, 6] |
| 24 | nums = [x for x in nums if x % 2 != 0] |
| 25 | print(nums) # [1, 3, 5] |
| 26 | |
| 27 | # SOLUTION 3: Iterate in reverse |
| 28 | for i in range(len(nums) - 1, -1, -1): |
| 29 | if nums[i] % 2 == 0: |
| 30 | nums.pop(i) |
| 31 | |
| 32 | # PITFALL: Modifying dict/list while iterating with enumerate |
| 33 | # If you must modify while iterating, track indices separately |
Mutable Default Arguments
pitfalls_default_args.py
Python
| 1 | # PITFALL: Mutable default arguments are shared across calls! |
| 2 | def add_item(item, target=[]): # BAD: list is created once |
| 3 | target.append(item) |
| 4 | return target |
| 5 | |
| 6 | print(add_item(1)) # [1] |
| 7 | print(add_item(2)) # [1, 2] — unexpected! previous call's state persists |
| 8 | print(add_item(3)) # [1, 2, 3] |
| 9 | |
| 10 | # FIX: use None and create a new list each time |
| 11 | def add_item(item, target=None): |
| 12 | if target is None: |
| 13 | target = [] |
| 14 | target.append(item) |
| 15 | return target |
| 16 | |
| 17 | print(add_item(1)) # [1] |
| 18 | print(add_item(2)) # [2] — correct, fresh list each call |
Accidental Reference vs Copy
pitfalls_references.py
Python
| 1 | # PITFALL: = does not copy — it creates a reference |
| 2 | original = [1, 2, 3] |
| 3 | alias = original |
| 4 | alias[0] = 99 |
| 5 | print(original) # [99, 2, 3] — modified through alias! |
| 6 | |
| 7 | # FIX: use copy() for a shallow copy |
| 8 | original = [1, 2, 3] |
| 9 | copy = original.copy() |
| 10 | copy[0] = 99 |
| 11 | print(original) # [1, 2, 3] — safe |
| 12 | |
| 13 | # PITFALL: Repeating mutable objects |
| 14 | # This creates a list with 3 references to the SAME inner list |
| 15 | matrix = [[0] * 3] * 3 |
| 16 | print(matrix) # [[0, 0, 0], [0, 0, 0], [0, 0, 0]] |
| 17 | matrix[0][0] = 1 |
| 18 | print(matrix) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] — all rows change! |
| 19 | |
| 20 | # FIX: use list comprehension for independent inner lists |
| 21 | matrix = [[0] * 3 for _ in range(3)] |
| 22 | matrix[0][0] = 1 |
| 23 | print(matrix) # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] — correct |
Sorting Return Value Confusion
pitfalls_sort.py
Python
| 1 | # PITFALL: list.sort() returns None, not the sorted list |
| 2 | nums = [3, 1, 4, 1, 5] |
| 3 | result = nums.sort() |
| 4 | print(result) # None — NOT [1, 1, 3, 4, 5] |
| 5 | |
| 6 | # Usually leads to TypeError when chaining: |
| 7 | # sorted_list = nums.sort() # result is None, not a list |
| 8 | |
| 9 | # FIX: use sorted() when you want a return value |
| 10 | nums = [3, 1, 4, 1, 5] |
| 11 | sorted_nums = sorted(nums) |
| 12 | print(sorted_nums) # [1, 1, 3, 4, 5] |
| 13 | |
| 14 | # Or use .sort() and ignore the return |
| 15 | nums.sort() # modifies in-place, returns None |
Shared References in Nested Structures
pitfalls_shared.py
Python
| 1 | # PITFALL: append in a loop with same object |
| 2 | row = [0] * 3 |
| 3 | matrix = [] |
| 4 | for _ in range(3): |
| 5 | matrix.append(row) # appends the SAME list each time |
| 6 | matrix[0][0] = 1 |
| 7 | print(matrix) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] |
| 8 | |
| 9 | # FIX: create a new list each iteration |
| 10 | matrix = [] |
| 11 | for _ in range(3): |
| 12 | matrix.append([0] * 3) # new list each time |
| 13 | matrix[0][0] = 1 |
| 14 | print(matrix) # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] |
| 15 | |
| 16 | # FIX with comprehension |
| 17 | matrix = [[0] * 3 for _ in range(3)] |
⚠
warning
The most common list pitfalls all stem from forgetting that lists are mutable and that = creates a reference, not a copy. Always use .copy() or [:] when you need an independent shallow copy, and copy.deepcopy() for nested structures.
$Blueprint — Engineering Documentation·Section ID: PYTHON-LISTS·Revision: 1.0