Arrays and lists
Most programs work with many values at once: the scores in a game, the songs in a playlist. A list keeps them in order, in memory slots that sit side by side. Step through nine lines of Python and see why reading an item by its index is instant, why indexes start at 0, how append finds room, and why inserting at the front makes every item move.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01letters = ["a", "b", "c", "d"]. What is letters[1]?
Indexes start at 0, so letters[0] is "a" and letters[1] is the second item, "b".
02With the same list, what is letters[-1]?
A negative index counts from the end: -1 is the last item. Python reads it as len(letters) - 1, which is index 3, "d".
03What does [10, 20, 30, 40, 50][1:3] give?
A slice starts at the first index and stops just before the second: indexes 1 and 2, so [20, 30].
04Why is reading nums[500000] from a list of a million items just as fast as reading nums[0]?
No searching is needed. One multiplication and one addition give the slot's address, whatever the index.
05A list holds a million items. Which of these is slowest?
Inserting at the front moves every item one slot to the right first, a million moves. append usually uses spare room, and indexing and len() are instant.
Glossary
- List
- Python's built-in way to keep several values in order, written with square brackets: [7, 3, 9, 5].
- Array
- A block of memory split into equal-sized slots that sit side by side. A Python list is built on one, and can grow.
- Index
- The position number of an item. Counting starts at 0; negative indexes count back from the end (-1 is the last).
- Slice
- A copy of part of a list, such as nums[1:3]: from the first index up to, but not including, the second.
- Reference
- What a list slot really holds in Python: the address of the item, which lives elsewhere in memory.
- Byte
- A small unit of memory: 8 bits. Memory addresses count bytes, so a slot of 8 bytes moves the address on by 8.
- Capacity
- How many slots a list has room for. It can be more than its length, so appends can use the spare room.
- O(1) and O(n)
- Ways to describe cost. O(1): the same time at any size. O(n): time grows with the number of items n.
Notes and sources
- The addresses 1000, 1008, ... are made up to keep the sums easy; real addresses are much larger numbers. The rule start + index × size is how any array finds a slot.
- In CPython each slot holds a reference (a C pointer), 8 bytes on a 64-bit computer. The items themselves are objects stored elsewhere in memory.
- The exact growth is an implementation detail. In CPython 3.14 the list [7, 3, 9, 5] has room for exactly 4, and the first append grows it to room for 8 (sys.getsizeof shows 88, then 120 bytes). Growing may copy the references to a new, bigger block.
- Amortised O(1) means that a single append may sometimes take longer (when the list must grow), but spread over many appends each one costs a small, fixed amount of time.
- In languages such as C, an array has a fixed number of slots chosen when it is made. A Python list is a growable array: it adds room by itself.
- Python FAQ: How are lists implemented in CPython?
- Python wiki: TimeComplexity (cost of list operations)
- Python tutorial: An informal introduction (lists, indexing, slicing)
- Python tutorial: More on lists (append, insert)
- Python library: Common sequence operations (negative indexes, slices, len)
- Python reference: The for statement
- Python library: struct format characters (P, the size of a pointer)
- CPython source: Objects/listobject.c (list_resize, the growth rule)
- Bryant and O'Hallaron, Computer Systems: A Programmer's Perspective, 3rd ed., §3.8 Array allocation and access
Quiz Unlocks after the last step.