When we closed the previous module we left a promise hanging in the air: there is "another bet" different from the array's, a structure that gives up memory contiguity precisely to make insertions and deletions cheap where the array falls short. That bet is the linked list, and this entire module is devoted to it and its variants. But before writing a single class we need to step back and do the same thing we did with the stack in lesson 01-01: separate the what (the list ADT, a contract of operations) from the how (a contiguous array or scattered nodes). In this lesson we define that contract, understand the fundamental piece of the new bet — the node with its next reference — and put the costs of both implementations side by side, so we can decide with sound judgment which one fits each corner of TaskFlow.

1. The list ADT: one contract, two implementations
2. The array's bet: contiguity (a strategic recap)
3. The other bet: scattered nodes and references
4. Anatomy of a node in Python
5. Cost comparison table: dynamic array vs linked list
6. Which one fits TaskFlow?

In lesson 01-01 we saw that an Abstract Data Type (ADT) defines what operations a structure offers without committing to how they are implemented inside: our ListStack and DictStack classes fulfilled the same contract with completely different interiors. With lists, exactly the same thing happens.

The list ADT is an ordered sequence of elements where each element occupies a position, and it offers at least these operations:

• Insert an element (at the front, at the back, or at an intermediate position).
• Remove an element (by position or by value).
• Find an element (is it there? at what position?).
• Traverse the sequence from start to end, visiting each element in order.
• Read the element at a given position and know the length of the sequence.

Notice that the contract says not a word about memory, slots, or references. And that is deliberate, because there are (at least) two radically different ways to fulfill it:

An important terminology warning: in Python, the word list names implementation A. It is a somewhat unfortunate name, because in the data structures literature "list" usually refers to the ADT, and "linked list" to implementation B. In this course we will say Python's list or dynamic array for A, and linked list for B.

We are not going to repeat lesson 01-05, but we will condense it into what matters for the comparison. The array bets everything on contiguity:

• It wins: O(1) access by index thanks to the formula base + i × size; very fast traversals (contiguous memory is friendly to the processor's cache); append in O(1) amortized.
• It loses: inserting or removing at the front or in the middle forces it to shift all the later elements, an O(n) cost that we measured with timeit and that turned quadratic when repeated in a loop (the insert(0) trap we saw at the close of module 1).

The question left floating is: what if we could insert an element in the middle of the sequence without touching the others? To achieve that, we have to abandon the idea that position in memory encodes position in the sequence.

The linked list flips the bet. Instead of demanding that elements live in consecutive slots, it lets each one live wherever it wants in memory. But then a problem arises: if the elements are scattered, how do we know which one comes after which? The array's formula no longer works, because there is no contiguity to exploit.

The solution is for each element to carry the address of the next one with it. That package — the data plus the reference to the next — is what we call a node:

Three key observations about this diagram:

• The list only needs to "grab hold of" the first node (we will call it the head). Starting from it, the arrows let you reach all the others.
• The last node points to None: it is the signal that "the sequence ends here".
• The arrows are the sequence. If in memory the node for task 3 physically sat before the one for task 1, it would make no difference whatsoever: the logical order is defined by the references, not by the addresses.

And here is the master move. To insert a new task between task 1 and task 2, nothing has to shift: it is enough to rewire two arrows.

It makes no difference whether the list has 3 elements or 3 million: the rewiring itself is two assignments, an O(1) cost. That is the essence of the "cheap insertions and deletions" promise. (Careful: getting to the insertion point may have its own cost; we will analyze it rigorously in the next lesson. We don't want to oversell this without the fine print.)

In Python we don't handle memory addresses by hand: we handle references, which is exactly what happens every time you assign an object to a variable. A node is simply an object with two attributes:

A detailed explanation for anyone seeing this for the first time:

• self.data stores the element itself. Since Python works with references, anything can live here: a number, a string, or — in our case — the task-as-dict we fixed in module 1.
• self.next stores another reference, this time to another Node object (or None if it is the last one). There is no magic: it is the same assignment mechanics you use every day, put to work chaining objects together.

We can chain three TaskFlow tasks by hand, with no container class yet:

Output:

The while loop above is the most important move of the whole module: advancing through a linked list means reassigning current = current.next until you run into None. Everything we build in the coming lessons — inserting, removing, finding — is a variation on this move.

Chaining nodes by hand is instructive but impractical. In 02-02 we will encapsulate all this mechanics in a LinkedList class with the ADT's operations; today, understanding the piece is enough.

This table is the module's map. The array column we proved in 01-05; the linked list column is, for now, a preview that lesson 02-02 will prove operation by operation (and verify with timeit, as our habits demand):

* The "trick" is for the list to also keep a reference to the last node (the tail); we will see it in 02-02.

Important readings from the table:

• There is no absolute winner. Each structure wins exactly where the other loses: it is a trade-off, the daily bread of data structures.
• The linked list loses the array's superpower: there is no longer a formula that reaches element i in one jump. Asking for "element 500,000" means taking 500,000 hops.
• Finding by value is O(n) in both: neither of the two solves the "find the task with id 42" problem we posed in 01-02. For that we will still need the index by id arriving in module 5.
• The linked list pays a memory overhead: every data item carries an extra arrow. Scattering is not free.

Let's bring the table down to earth with our application's real scenarios:

The conclusion for TaskFlow is nuanced, like almost everything in engineering: as long as the board only grew at the back and was read in order, Python's list was unbeatable. But a team's real board does not work like that: urgencies enter at the front, tasks get dispatched from the front, and things are reordered through the middle constantly. That usage pattern — many insertions and deletions in awkward positions — is exactly the terrain where the linked list shines, and that is why we choose it as the foundation of the definitive board.

• Confusing Python's list with a linked list. It is the number one terminology mistake. Python's list is a dynamic array (lesson 01-05); if an interviewer asks you to "implement a linked list", answering my_list = [] is answering a different question.
• Believing the linked list is "better" than the array. It isn't; it is better for certain operations and worse for others. Whoever memorizes "linked list = fast" without the cost table ends up choosing badly. Keep this lesson's table next to the list/dict/set cost table from 01-04.
• Forgetting that next can be None. Writing current.next.data without first checking that current.next is not None triggers the classic AttributeError: 'NoneType' object has no attribute 'data'. Get used to asking yourself on every line, starting now: "what if there is no node here anymore?".
• Losing the head of the list. If you reassign the variable pointing to the first node (head = head.next by accident), the previous node becomes unreachable and Python's garbage collector removes it. The head is the single thread the whole structure hangs from: treat it with respect.
• Tip: when in doubt about a reference rewiring, draw the nodes and arrows on paper before writing code. It is the technique even veteran engineers use, and in the coming lessons we will practice it with mermaid diagrams at every step.

Exercise 1 — The contract and its implementations. Without looking at the table, classify these four statements as belonging to the list ADT, the dynamic array, or the linked list: (a) "insert an element at position i"; (b) "the elements occupy contiguous memory slots"; (c) "each element stores a reference to the next one"; (d) "traverse the elements in order". Justify each answer in one line.

Exercise 2 — Chaining and traversing by hand. Using only this lesson's Node class (no container class), build a chain with these four TaskFlow tasks: "Review design" (id 10), "Fix login bug" (id 11), "Deploy release" (id 12), and "Close sprint" (id 13), all with priority 2 and status "pending". Then write: (a) a loop that prints id - title for each task; (b) a loop that counts how many nodes there are, without using len on any auxiliary structure.

Exercise 3 — Rewiring without shifting. Starting from the chain of exercise 2, insert the task "Production hotfix" (id 14, priority 1) between "Fix login bug" and "Deploy release", without creating any new chain: just by creating one node and reassigning the necessary references. How many next assignments did you need? Would that number depend on the chain having a million nodes?

Solution 1:

• (a) List ADT: it describes an operation of the contract, without saying how it is achieved inside.
• (b) Dynamic array: contiguity is the implementation decision that yields O(1) access by formula.
• (c) Linked list: the reference to the next is the implementation decision that makes scattering possible.
• (d) List ADT: traversing is part of the contract; both implementations offer it (with different interiors).

Solution 2:

Notice that both parts use the same traversal pattern; only what we do when visiting each node changes. That pattern is the heart of the class we will build in 02-02. And yes: chains like head.next.next.next = ... are horrible — which is exactly why we need to encapsulate this in a class.

Solution 3:

2 assignments of next were enough, and that number would be identical with a million nodes: the rewiring itself is O(1). Look at the order of the two lines: if we did bug_node.next = new_node first, we would lose the reference to "Deploy release" and the rest of the chain would be left dangling. This detail — the order of the rewiring — will take center stage in the next lesson.

We have separated the contract from its implementers: the list ADT is an ordered sequence with insert, remove, find, and traverse operations, and both the dynamic array and the linked list implement it with opposite bets — contiguity with O(1) access by formula versus scattered nodes joined by next references, where inserting means rewiring two arrows instead of shifting half of memory. The cost table made it clear that there is no absolute winner, and the usage pattern of the TaskFlow board (urgencies at the front, reorderings through the middle) tipped the balance toward the linked list. But so far we have only chained nodes by hand, with that awkward head.next.next. In the next lesson we will do things properly: we will build the complete LinkedList class — insert, remove, find, traverse, __len__, __str__ —, analyze the Big O of every operation, and put the creature in front of timeit to confirm that the promise of cheap insertions holds exactly where the array fell down: inserting at the front.