Indexing and slicing
Indices count from 0, and negative indices count from the end: lst[-1] is the last element, lst[-2] the second-last.
A slice takes [start:stop:step], where start is inclusive, stop is exclusive, and any part may be omitted. With lst = [10, 20, 30, 40, 50]:
lst[1:4] → [20, 30, 40] # stop is excluded
lst[:3] → [10, 20, 30]
lst[::2] → [10, 30, 50] # every second element
lst[::-1] → [50, 40, 30, 20, 10] # reversed
The exclusive stop is deliberate: it makes lst[:k] + lst[k:] reconstruct the original for any k, and it makes the length of a slice simply stop − start. Every slice returns a new list, so slicing an n-element list costs O(n) time and O(n) memory — slicing in a loop is a common accidental quadratic.
What each operation costs
lst[i] # O(1) direct address
lst.append(x) # O(1) amortised
lst.pop() # O(1) from the end
lst.insert(0, x) # O(n) shifts everything
lst.pop(0) # O(n) shifts everything
x in lst # O(n) linear scan
lst[a:b] # O(b−a) copies
Amortised O(1) for append means individual appends are occasionally expensive. When the underlying array fills, Python allocates a larger one and copies everything across — O(n) for that one call. Because the array grows by a proportion rather than a fixed amount, those resizes become rarer as the list grows, and the average over many appends is constant.
Why append is amortised O(1)
The list holds more capacity than its length. When it fills, Python allocates a larger block — growing by roughly an eighth of the current size — and copies everything across.
That resize is O(n). Spread across the many appends that fit in the new capacity, the average cost per append is constant. That is what amortised means: individual operations can be expensive, the sequence is cheap.
The practical consequence is that appending in a loop is fine, and it is worth knowing that a list comprehension is faster still because the append happens in C rather than through the interpreter:
squares = [x * x for x in range(1000)] # fastest
squares = list(map(lambda x: x*x, range(1000)))
squares = []
for x in range(1000):
squares.append(x * x) # slowest of the three
If you know the final size and need a fixed-length list, [None] * n allocates once.
Copying, and the aliasing trap
A list holds references, so copying has two levels.
a = [1, 2, 3]
b = a # NOT a copy - another name for the same list
b.append(4)
print(a) # [1, 2, 3, 4]
c = a.copy() # shallow copy - a new list, same objects inside
c = a[:] # same thing
c = list(a) # same thing
Shallow means the new list is separate, and the objects it points to are shared:
grid = [[0, 0], [0, 0]]
flat = grid.copy()
flat[0].append(9)
print(grid) # [[0, 0, 9], [0, 0]] - the inner lists are shared
Use copy.deepcopy() when the nested objects must be independent.
The same aliasing produces the most notorious Python gotcha:
board = [[0] * 3] * 3 # three references to ONE row
board[0][0] = 1
print(board) # [[1,0,0], [1,0,0], [1,0,0]]
board = [[0] * 3 for _ in range(3)] # three separate rows - correct
[x] * n repeats the reference n times. For immutable values that is harmless; for mutable ones it is a bug.
Exploration guide
- Watch the exclusive stop. Set Start to 1 and Stop to 4, then press Run Expression. Three elements come back, not four — index 4 is the boundary, not a member.
- Reverse with a negative step. Set Step to −1 and leave start and stop empty. The whole list comes back reversed, and it is a copy: the original is untouched.
- Index from the end. Set Index (i) to −1 and run. You get the last element without needing to know the length — the idiom that replaces lst[len(lst)−1].
- Compare a front insert with an append. Use Select Method to insert at index 0, then to append. Both look instant here, but only one avoids shifting every element — the difference shows up at a hundred thousand elements, not five.
What trips people up
- Using pop(0) as a queue. Every removal shifts the whole list, so a queue built this way is O(n²). Use collections.deque, which is O(1) at both ends.
- The mutable default argument. def f(items=[]) creates the list once, at definition time, and every call shares it. Use None as the default and build the list inside.
- Assuming assignment copies. b = a binds another name to the same list; mutating b changes a. Use a[:] or list(a) for a shallow copy.
- Removing items while iterating. Deleting during a for loop shifts the remaining elements and the loop skips items. Iterate over a copy, or build a new list with a comprehension.
- Multiplying to build a grid. [[0]*3]*3 makes three references to the same row. Use a comprehension: [[0]*3 for _ in range(3)].
What to remember
A Python list is a contiguous dynamic array, so indexing is O(1), appending is amortised O(1), and anything touching the front is O(n) because every later element must shift. Slices are always copies, negative indices count from the end, and the stop bound is exclusive. Most list performance bugs are one of two things: treating the front like the back, or slicing inside a loop.
Sorting, and the in-place trap
items = [3, 1, 2]
items.sort() # sorts IN PLACE, returns None
new = sorted(items) # returns a NEW sorted list
items = items.sort() # BUG - items is now None
That last line is the classic mistake, and it follows a Python convention: methods that mutate return None, precisely so this error fails loudly rather than silently.
The key parameter is where the useful power is:
words.sort(key=len) # by length
people.sort(key=lambda p: (p.surname, p.first)) # by surname, then first name
items.sort(key=lambda x: -x.score) # descending by score
Sorting by a tuple gives multi-key sorting in one pass. And because Timsort is stable, sorting by one key and then another also works — the second sort preserves the first's order within ties, which is how "sort by department, then by name within department" is done as two sorts.
Choosing the right structure
| Need | Use |
|---|
| Indexed access, ordered items | list |
| Add/remove at both ends | collections.deque |
| Membership testing | set — O(1) instead of O(n) |
| Key-value lookup | dict |
| Fixed record, hashable | tuple |
| Counting | collections.Counter |
| Grouping | collections.defaultdict(list) |
| Numeric arrays, maths | numpy.ndarray |
| Sorted order maintained | bisect.insort, or sortedcontainers |
The membership row is the one that most often matters:
# O(n^2) - 'in' scans the list for every item
for x in items:
if x in other_list: ...
# O(n) - build a set once
other = set(other_list)
for x in items:
if x in other: ...
That transformation is the most common real-world optimisation in Python, and it usually shortens the code as well.
Memory
A Python list of a million integers uses considerably more memory than a million integers' worth of data: the list holds a million pointers (8 bytes each), and each small integer is itself an object with a header.
Two alternatives when that matters:
numpy.ndarray stores raw values contiguously — a million 64-bit integers is 8MB, against roughly 40MB for a list. It also enables vectorised operations that run in C.
Generators avoid materialising the list at all:
total = sum(x * x for x in range(10_000_000)) # no list built
For a large intermediate that is consumed once, a generator expression is both faster and dramatically lighter.
The costs behind the operations you use every day
A Python list is a dynamic array, and almost every surprising thing about its performance follows from that one fact. Measuring the operations side by side turns a table of complexities into something you can predict from.
Questions people ask
Is a Python list a linked list? No — it is a dynamic array of pointers, contiguous, with O(1) indexing.
Why is insert(0, x) slow? Every existing element shifts one position right. Use deque.appendleft.
Why does list.sort() return None? By convention, mutating methods return None, so x = x.sort() fails visibly.
What is the difference between list and tuple? Tuples are immutable and can be dictionary keys; lists are mutable and cannot.
How do I remove duplicates? list(set(items)) loses order; list(dict.fromkeys(items)) preserves it.
When should I use NumPy instead? For numeric data of uniform type, especially with arithmetic across the whole array — far less memory and far faster.
Recap in one screen
- A list is a contiguous array of pointers with spare capacity, which is why indexing and appending are O(1).
- Operations at the front are O(n) because everything shifts — use
deque there. - Assignment shares the list;
copy() is shallow; [x]*n repeats a reference. sort() mutates and returns None; sorted() returns a new list; both are stable.- Replacing
in list with in set is the most common Python speed-up available.