The previous lesson left two questions pending: why does accessing items[i] cost O(1), and what hidden reorganization makes append only O(1) amortized? To answer them we need to go down a level: understand how a computer's memory is physically organized and what an array is — the most elementary structure of all and the foundation on which almost every other one is built. By the end you will know exactly what Python's list does under the hood, which TaskFlow operations an array handles well... and which it doesn't, which will open the door to module 2.

1. Memory as a row of numbered slots
2. Static arrays: contiguity and O(1) access
3. The price of contiguity: inserting and removing in the middle
4. Dynamic arrays and amortized resizing
5. Python's list under the hood (and a mention of array and NumPy)
6. TaskFlow: when an array is enough and when it falls short

You can picture a computer's RAM as a gigantic row of equally sized slots, numbered consecutively. Each slot's number is its memory address, and the processor can read or write any slot just by knowing its address, no matter how "far away" it is: going to slot 4 and to slot 40,000,000 costs the same. That is why this memory is called RAM: Random Access Memory — direct access.

Two key ideas from this model:

• Every piece of data lives at some address. When you write x = 42 in Python, somewhere in that row the 42 gets stored, and x is the human way of referring to its address. Python hides the addresses from you (in C you handle them manually, with pointers), but you can peek with id(x), which returns an identifier based on the object's address.
• Accessing by address is O(1). It is a hardware operation: the processor computes the address and goes there. No searching, no scanning.

On top of this model there is a fundamental decision that splits two worlds: storing the data contiguously (in consecutive slots) or scattered (each piece wherever there is room, connected by references). Arrays bet on contiguity; the linked lists of module 2 will bet on scattering. This entire lesson revolves around the consequences of that bet.

A static array is a block of contiguous slots reserved all at once, with a fixed size, where every slot occupies the same amount of space. It is the native structure of languages like C or Java.

Contiguity carries an enormous prize. If the array starts at address 1000 and each element occupies 8 bytes, where is the element at index i? There's no need to search for it: it is computed.

One multiplication and one addition, whether i is 3 or 3 million: that is why access by index is O(1). This formula is the answer to the first pending question from lesson 01-04, and it is one of the most important ideas in the course: the array doesn't search for element i, it computes where it must be.

Let's simulate a static array in Python to feel its limits (Python doesn't have them natively, so we impose the restrictions ourselves):

Points in the code worth attention:

• [None] * capacity reserves all the slots at creation time: that is what "static" means. The memory is committed even if it goes unused.
• add is O(1)... until the array fills up. Then there is nothing to be done: OverflowError. A static array does not grow.
• We distinguish _capacity (reserved slots) from _used (slots holding real data). This distinction seems minor now, but it is the key to the dynamic arrays section.

An extra advantage of contiguity worth knowing: modern processors read memory in blocks (cache), so traversing contiguous data is even faster in practice than traversing scattered data: when reading element 0, the next ones come along "for free" in the same block.

Everything contiguity gives away on access, it charges back on modifications. Think of a fully occupied row of seats at a movie theater: if someone wants to sit in the middle, everyone on one side has to shift over one seat.

Inserting at position i in an array requires shifting every element from i to the end one slot to the right:

Removing position i is the inverse move: the later elements shift left so no gap remains (contiguity admits no holes).

The cost, in the vocabulary of the previous lesson:

Notice the asymmetry that defines the array: splendid at reading and modifying by position, expensive at reorganizing. Inserting at the front is the most painful case: every element moves.

The static array has an obvious practical problem: you have to guess the size in advance. How many tasks will a TaskFlow user have? 100? 100,000? Falling short is fatal (OverflowError) and overshooting wastes memory.

The dynamic array resolves the dilemma with an elegant strategy:

1. Start with a static array of some capacity.
2. Keep count of used slots versus total capacity (our _used and _capacity).
3. When an append finds the array full: reserve a new, larger array (typically double or thereabouts), copy all the elements into the new one, and release the old one.

The copy step costs O(n), and here appears the answer to the second pending question from lesson 01-04. Why is append O(1) amortized and not O(n)? Because of the policy of doubling the capacity: after copying n elements, n free slots remain — meaning the next n appends are guaranteed O(1). The O(n) cost of the copy, spread across those n cheap appends, comes out to O(1) extra per operation.

Let's count it with numbers so it doesn't stay abstract: starting from capacity 1, performing 8 appends triggers copies of 1, 2, and 4 elements (when filling capacities 1, 2, and 4): 7 copies in total for 8 insertions — less than one copy per append. With 1,024 appends, the copies add up to 1,023: still ~1 per operation. The average does not grow with n: that is O(1) amortized, exactly the definition we gave in the previous lesson.

The honest counterpart: one particular append (the one that triggers the copy) can indeed be slow, and the dynamic array keeps spare slots reserved (extra memory of up to double what is used). Flexibility in exchange for occasional spikes and some memory: another one of those trade-offs you already know how to recognize.

The big reveal of this lesson: Python's list is exactly that, a dynamic array. It is not a "linked list" despite its name (that will be precisely the topic of module 2, and the naming mix-up is a classic trap). Now the entire cost table we gave in lesson 01-04 has a physical explanation:

A technical nuance worth knowing: since a list can mix types and Python objects have different sizes, the array's slots don't hold the objects themselves but references (addresses) to them, all of the same size; that is why the access formula keeps working. And CPython's growth policy isn't exactly doubling, but growing ~1.125× plus some headroom; the amortized analysis holds for any proportional growth.

We can even observe the resizing from the outside with sys.getsizeof, which gives the bytes the object occupies:

Typical output (varies with the Python version):

The size doesn't grow with every append, but in jumps: each jump is a reservation of extra capacity, and between jumps the appends request no memory. It is amortized resizing seen live.

Two relatives of list worth knowing, as a mention only:

• array.array (a standard library module): a homogeneous dynamic array that stores the numbers themselves (not references), saving a fair amount of memory when you have millions of values of the same type.
• NumPy (numpy.ndarray): the standard library of numerical computing; homogeneous, compact arrays with enormously fast vectorized operations. If TaskFlow ever computed statistics over millions of time records, NumPy would be the tool. It falls outside this course, but you should know it exists and that under the hood it is... a contiguous array, like everything in this lesson.

Let's close by applying the criterion to our project. TaskFlow's board, array (list) version:

For these three uses — adding at the end, listing in order, accessing by position — the list is the right choice, and no structure in the course will beat it at them. Its status as Python's default first option is well earned.

But look what happens with two other real TaskFlow use cases:

With 50 tasks, none of this matters. But imagine the global activity feed of a corporate TaskFlow with hundreds of thousands of entries where the norm is inserting at the front and deleting from the middle: every operation would shift hundreds of thousands of references. The diagnosis, in the vocabulary you now command:

What if there were a structure where inserting or removing in the middle shifted nothing, because the elements don't live contiguously but linked to one another, each wherever it landed in memory? There is: it's the linked list, the other great bet — scattering instead of contiguity — and the topic of module 2. As is only fair, it will have its own costs: losing contiguity means losing the magic O(1) access formula. There is no free lunch; there are informed choices.

• Believing Python's list is a linked list. The name misleads: it is a dynamic array. This misunderstanding leads to assuming that inserting at the front is cheap, when it is O(n). In module 2 the comparison will become crystal clear.
• Using items.insert(0, x) or items.pop(0) inside loops. It is Python's most common accidental O(n²): n operations of O(n). If you routinely need to add and remove at the front, there is a structure designed for it (collections.deque, which we will study in module 4).
• Panicking over the resize spike. An occasional append costing O(n) is almost never a real problem: the amortized O(1) is what counts in practice. Only in systems with strict latency constraints do the spikes matter.
• Ignoring the reserve memory. A dynamic array can hold up to twice as many slots as it uses. With millions of numeric elements, array.array or NumPy drastically cut consumption compared to list.
• Tip: faced with any new structure, always ask "is it contiguous or scattered inside?". The answer will tell you, without reading documentation, which operations will be cheap (access if contiguous; reorganization if scattered) and which expensive.

An array of 8-byte integers starts at address 5000. (a) At what address is the element at index 12? (b) If an element sits at address 5096, what is its index? (c) Explain in one sentence why this formula stops working if the elements occupied different sizes.

Starting from the array [10, 20, 30, 40, 50] (capacity 8, 5 slots used), state how many elements shift in each operation and the array's final state after applying them in order: (a) insert(0, 5); (b) append(60); (c) remove the element at index 2; (d) insert(3, 35).

Write a program that uses timeit to compare building a list of 50,000 elements in two ways: (a) with append (adding at the end) and (b) with insert(0, x) (adding at the front). Before running it, predict which will be slower and why, and check whether the difference grows when moving to 100,000 elements.

Solution 1:

• (a) 5000 + 12 × 8 = 5096.
• (b) (5096 − 5000) / 8 = 12: the same element as in the previous part, computed in reverse.
• (c) The formula multiplies the index by a fixed size; with variable sizes you cannot compute where element i starts without scanning and adding up the sizes of all the previous ones (which is why Python's list stores fixed-size references to the objects, not the objects themselves).

Solution 2:

• (a) insert(0, 5): all 5 elements shift → [5, 10, 20, 30, 40, 50].
• (b) append(60): 0 shift (there is a free slot, capacity 8) → [5, 10, 20, 30, 40, 50, 60].
• (c) remove index 2 (the value 20): the 4 later elements shift left → [5, 10, 30, 40, 50, 60].
• (d) insert(3, 35): the 3 elements from index 3 onward shift → [5, 10, 30, 35, 40, 50, 60].

Moral of the exercise: the cost of each operation depends on how many elements remain to the right of the modification point; that is why the worst case is always the front.

Solution 3:

Prediction: version (b) will be much slower, because each insert(0, x) shifts every element already present: the total cost is 0 + 1 + 2 + ... + (n−1) ≈ n²/2 shifts, i.e., O(n²); version (a) is n appends of O(1) amortized, i.e., O(n) total.

Typical result: with 50,000 elements, append takes milliseconds and insert(0, ...) on the order of seconds; doubling to 100,000, append doubles (linear) but insert(0, ...) quadruples (quadratic), confirming the prediction. It is the physics of the array — the shifts — showing up exactly as the theory announces.

You have reached the bottom of the matter: memory is a row of numbered, directly addressable slots, and the array — contiguous data, equal slots — exploits that organization to offer O(1) access by index through a simple formula, paying for it with O(n) shifts when inserting or removing in the middle. Dynamic arrays add automatic growth with proportional resizing, whose spread-out cost yields the famous O(1) amortized append; and Python's list is exactly that, with array.array and NumPy as compact variants for massive numeric data. For TaskFlow, the array is perfect as a board that grows at the end and is read in order, and falls short when insertions and deletions at the front or in the middle abound.

This closes module 1: you now know what a data structure is, why choosing it well matters, which families exist, how to measure their efficiency with Big O, and on what physical foundation everything is built. In module 2 we start building for real: the linked list, the first structure we will craft from scratch, which gives up contiguity precisely to make cheap the operations where the array falters — and which we will turn into TaskFlow's definitive task board.