Lesson 1 of 5
Lists & Slicing
"Programs must be written for people to read, and only incidentally for machines to execute." — Harold Abelson & Gerald Jay Sussman, Structure and Interpretation of Computer Programs (1984)
In most languages, the list is something you reach for occasionally — a convenience layer over the real workhorse, the array. Python is the reverse. There is no array in the core language. The list is the array, and it is also the queue you build on, the stack, the return value of most functions, the thing JSON deserialises into, and the default answer to "I need a bunch of things". Python programs spend more of their life building, slicing, sorting and scanning lists than doing almost anything else.
That centrality is a design choice with a price. Because the list is the default, it is also the wrong tool an impressive amount of the time — and the mistakes are invisible, because a list always works, just slowly. Scanning a million items with in works. Inserting at the front in a loop works. It just takes orders of magnitude longer than the right structure would, and nothing tells you.
This chapter is about what a list actually is, how to build one idiomatically, and how to use the syntax Python gives you — slicing in particular, which is the most expressive and the least understood piece of list grammar. It ends with the uncomfortable part: recognising when the list is the wrong answer, because the closing chapter of Part II is entirely about choosing between the structures.
items[2] hands you a reference to whatever object lives at position 2. items[2:5] hands you a brand-new list containing copies of the references at positions 2, 3 and 4. And items[2:5] = [9, 9, 9, 9] edits the original list, changing its length. Three uses of one pair of brackets, three different relationships to the original data. What is a slice, exactly — and why does the same syntax both copy and mutate?
A dynamic array with Python's clothes on
Under the hood, a list is a contiguous block of memory holding pointers to objects — nothing more exotic than that. It is not a linked list of nodes scattered across memory; it is an array, which is why indexing is instant: the address of element k is the base address plus k times the pointer size, one multiplication away.
What Python adds to the raw array is growth. When a list runs out of room, CPython allocates a larger block, copies the pointers over, and frees the old one — and it overallocates, reserving extra slots so the next few appends need no reallocation at all. That is why appending a million items is not a million copies; it is a handful of geometric expansions, each roughly doubling the capacity. The result is that append is constant time on average — the famous amortised O(1) — while an insert in the middle is genuinely O(n), because every element after it must shift down.
Click Run to execute the code.
The id() staying constant across 10,000 appends is the whole story: the list is one object whose internal storage expands. If append created a new list each time, building a list of a million items would be impossibly slow — and the fact that it is not is the overallocation working.
Picture a long table at a wedding reception. Finding seat k is instant — you count along, every seat the same distance apart. That is indexing. Making everyone stand and shift along one place so a late guest can sit in the middle is slow, and the more people, the slower. That is inserting in the middle. And when the table runs out of room, the hall does not build a new one and move the party — it extends the table by a chunk at the end, so there is usually space before the next extension. That is overallocation, and it is why appending feels free.
Slicing: the copy, the step and the forgiving bounds
A slice is a stretch of the sequence, materialised as a copy. items[2:5] creates a new list containing the references from positions 2 up to but not including 5. Because it is a copy, mutating the slice never touches the original — and because the copy is shallow (Part I, Chapter 3), mutating objects inside the slice does reach the originals.
Slices differ from indexes in two ways that trip people up. First, bounds are forgiving: any slice of an existing list is legal, even one that starts past the end, and an empty slice is just an empty list — while an index out of range raises IndexError. Second, slices can write. Assigning to a slice replaces that stretch of the original, and because the replacement may be a different length, slice assignment grows or shrinks the list.
Click Run to execute the code.
Read the two behaviours together: items[2:5] gives you a new list (reads copy), while items[2:5] = ... mutates the original (writes edit). That asymmetry is the answer to the big question — a slice is not a thing, it is a grammar position. On the right of =, it names a stretch of the original to replace. Everywhere else, it constructs a new list.
The step is where slices get genuinely powerful and genuinely confusing. [::-1] is the idiomatic reverse-copy. [1::2] is every second element. And a negative step with confusingly-specified bounds is how working code accumulates three comments and a ticket. When the step is negative, the start defaults to the end and the stop to the beginning — which is why [::-1] reverses without naming either.
Building lists: +, +=, append, extend
Four ways to put things into a list, and the differences matter because three of them are quietly different operations. append adds one element — the element, whatever it is, so appending a list nests it. extend adds the elements of an iterable, one by one. + builds a brand-new list from two. += is extend wearing a different shirt, exactly as Part I promised: for lists, a += b mutates a in place rather than rebinding.
Click Run to execute the code.
The nested result of append([3, 4]) is usually a bug — the author wanted extend — and it stays silent until something later iterates the outer list expecting numbers and finds [3, 4] instead. The += result reconnects this chapter to Part I: it is a mutation, not a rebinding, so a function that does items += more changes the caller's list while items = items + more does not — the difference between a side effect and a return value, wearing the syntax of two characters.
Python has had lists since its very first release in 1991 — Guido van Rossum's original language shipped with them — but it took nearly a decade for them to become fast at building. Early CPython grew a list by exactly one slot per append, so appending N items meant reallocating and copying N times: the loop ran in quadratic time, and building a list of a million items was a grinding O(N²) exercise. The fix, introduced with Python 2.0 in 2000, was geometric overallocation — grow the array to a size proportional to the current length rather than the current length plus one — which makes appends amortised O(1) and is the reason the id() stayed constant in this chapter's first block. It is a textbook example of an invisible implementation detail shaping a language's idioms: build with append, then use is only good advice because overallocation made it cheap.
Searching, sorting and membership
Reading a list by index is instant; finding a value in it is not. x in items, items.index(x) and items.count(x) all scan the list from the start — O(n) — and for a list of a million elements, that is a million comparisons per call. If you find yourself writing if x in big_list: inside a loop, you have written an O(n²) program and it will feel like it.
Sorting is the part of list life with the most moving parts. items.sort() sorts in place and returns None; sorted(items) returns a new list and leaves yours alone. Both take a key= function — and crucially, key is called once per element up front, not once per comparison, which is why key=len is cheap even though the sort itself does many comparisons. Python's sort is stable: equal elements keep their original relative order, the property that lets you sort by one key and then another without the second sort destroying the first.
Click Run to execute the code.
The stable-sort behaviour is worth sitting with: it is the answer to "sort by name, then by age" in two passes — sort by age first, then by name, and the second sort preserves the first's order among equal names. That is exactly why obi stays before ema above: the sort by age sees them as ties and leaves them where the input put them.
When I am handed a codebase and told "it is slow somewhere", I do not reach for a profiler first. I read the loops, looking for five patterns: .insert(0, ...), .pop(0), in some_list inside a loop, .remove() inside a loop, and building one list by repeatedly concatenating it. Each one is a list doing work it was not built for, and each has an obvious replacement — a deque, a set, a comprehension, a list built once and reused. The profiler confirms; the grep finds. Lists are so fast at what they are good at that the performance problems in real code are almost never "the list is slow" and almost always "a list is doing a job some other structure exists for".
When a list is the wrong tool
Lists are the default for good reason, but the default is not always right. Three situations make a list quietly expensive, and the fix is usually a one-line change to another structure. Inserting or removing at the front of a large list is O(n): every element shifts by one, while a deque gives O(1) appends and pops at both ends. Membership in a large list is O(n) per check; a set makes it O(1) — the subject of two chapters from now. And the most surprising of all: deleting items from a list while iterating over it skips elements, because removing one shifts everything down and the loop's position does not adjust.
Click Run to execute the code.
That first result is the bug in its purest form. The loop removes the element at position 0; the list shifts left; the loop advances to position 1, which now holds the third 2; it removes that; the list is down to one element and the loop's position is past the end, so the middle 2 was never visited. Three identical values, two removals, one survivor, no error. The fix is to stop deleting while iterating: iterate a copy and mutate the original, or — almost always cleaner — build a new list.
Lists arrive from the outside world as JSON arrays, database rows and API responses, and the temptation is to process them in place. The safer discipline, once a list has crossed into your code from someone else's, is to treat it as read-only: iterate it, copy it, build from it — but do not mutate the object you were handed, because the caller who gave it to you may be holding the same reference. The practical rule is that a function should never append, extend, sort or delete on a list that was passed in unless it is documented as owning it. This is not ceremony; it is exactly what prevents two modules from silently corrupting each other's data, and it is the difference between a function that transforms input and one that quietly edits shared state.
Common Mistakes
- Reading a slice as a view.
items[2:5]is a new list. Mutating the slice leaves the original untouched; if you wanted the original changed, assign to the slice. - Using
appendwhere you meantextend.a.append([1, 2])nests the list instead of adding its elements, and the bug surfaces later as a broken "flat list" assumption. - Deleting or inserting while iterating. Elements shift, positions skip, and the loop silently visits the wrong items. Iterate a copy or build a new list.
- Discarding
sort()andreverse()return values. They returnNone.items = items.sort()destroys the list;items = sorted(items)is the correct new-list form. - Confusing out-of-range index with out-of-range slice.
items[10]raises;items[10:20]returns[]. The difference hides bugs when code "works" on slices that do not exist. - Using
inon a large list inside a loop. A linear scan per check becomes quadratic overall. Convert to a set when membership is the question. - Forgetting that slices are shallow copies. The outer list is new; the objects inside are shared, so mutating a contained list through a slice reaches the original.
insert(0, x)orpop(0)in a loop. Both are O(n) per call. Use adequewhen the front of a large collection is hot.- Building a grid with
[[0]] * 3. The repetition duplicates one reference, so a later mutation appears in every row. Build with a comprehension. - Mutating a list you received from another function. Unless the interface says you own it, copy first — the caller may still hold the reference.
Interview Corner
append and extend?append adds its argument as a single element, whatever that argument is — so a list becomes one nested element, and [1].append([2]) gives [1, [2]]. extend adds the elements of an iterable one at a time, so [1].extend([2]) gives [1, 2]. The one-sentence rule is that append adds the thing, extend adds the things inside it. The confusion bites when someone appends a list expecting it to flatten: the list is added as one item, code later iterates expecting numbers, and the failure appears far from the line that caused it. A related distinction worth mentioning is + versus += — + builds a brand-new list, while += extends in place like extend and does not rebind, which matters when the list came from a caller.remove in the loop ends up with one left, and no exception is raised. There are two standard fixes. Iterate over a copy and mutate the original: for x in list(items): items.remove(x). Or, usually cleaner, don't mutate at all — build a new list with a comprehension, kept = [x for x in items if not bad(x)]. I prefer building a new list whenever filtering is the actual intent, because it also avoids the aliasing problem of mutating a list someone else may hold. The same skipping happens with insert during iteration, so mutating a sequence while looping over it is a smell regardless of the operation.id in sessions scans from the start, so every request is O(n) in the number of active sessions, and at a few hundred thousand sessions that is a measurable per-request cost that grows with success. The minimal fix is a set, which makes membership O(1) on average — same elements, different access characteristics. But I would not stop at the swap, because the real question is the access pattern. If the service also needs to expire the oldest sessions, membership alone is not the whole requirement, and I would want a structure that supports both: a set for lookups plus a heap or deque ordered by expiry, or a purpose-built cache with TTL. I would also check what removes entries, since an unbounded set of session IDs is a slow memory leak, and whether the container is mutated from multiple threads. The general point is that the list was not slow in the abstract — it was slow at the one operation this service performs constantly, and the fix is to match the structure to the access pattern rather than micro-optimise the loop around it.Take the starter block and implement dedupe(seq), which removes duplicates while preserving first-seen order — the idiomatic approach tracks seen items in a set while building the result, and your assertions must prove order is preserved rather than merely that duplicates are gone. Then implement rotate(items, k), shifting a list right by k positions using slicing, and prove it handles k = 0 and a k larger than the list. Next, reproduce the remove-in-loop bug with a list of repeated values, confirm the survivor, then fix it both ways — iterating a copy and building a new list — and decide which you would ship. Finally, use bisect.insort to keep a leaderboard sorted as scores arrive, asserting after each insertion that the list still equals its own sorted().
Click Run to execute the code.
Summary
- A list is a dynamic array — a contiguous block of pointers — so indexing is O(1) and append is amortised O(1) thanks to geometric overallocation.
appendadds one element;extendadds an iterable's elements. Appending a list nests it, and the resulting unexpected inner list is a silent bug.+builds a new list;+=extends in place. The two-character difference is a rebind versus a mutation, which is why it matters inside functions.- A read slice is a copy; a write slice edits the original. The same brackets do different things depending on which side of
=they sit. - Slice bounds are forgiving — out-of-range slices return
[]— while out-of-range indexes raiseIndexError, which lets slice bugs hide. [::-1]reverses,[::2]steps, and zero-width slices insert — the three slice forms that cover most real needs.in,.index()and.count()are linear scans. Membership on a large list inside a loop is the classic accidental O(n²).sort()mutates and returnsNone;sorted()returns a copy.key=runs once per element, and the sort is stable.- Mutating a list while iterating skips elements. Iterate a copy or build a new list; never delete in a live loop.
- The front of a large list is a deque's job —
insert(0, …)andpop(0)are O(n), whileappendleftandpopleftare O(1).
In the next chapter, Dictionaries, we meet the structure Python is really built on — the hash table. It solves exactly the problem that makes lists slow, and it brings its own traps, starting with the difference between a missing key and a present-but-empty value.
The list chapter is where I watch students' relationship with Python change, because lists are the first place where "it works" and "it is right" visibly separate. The remove-in-loop demonstration reliably produces the same reaction — mild outrage that the language lets a loop silently skip work — and that reaction is worth keeping rather than smoothing over. The honest framing is that Python does not protect you from O(n) work or from mutating while iterating; it makes both easy and trusts you to notice. That is the real content of this chapter, and it matters more than any slice syntax: the data structures are tools with costs, the syntax makes cheap and expensive operations look identical, and the skill being built is reading code for what it is actually paying for.
Q&A · 0
Enrol to ask questions and join the discussion.
No questions yet — be the first to ask.