1.4.2 - Linked lists and pointer operations

Nodes hold data and the next location

A singly linked list is a sequence of nodes, each storing data and a next pointer identifying the next node. A head pointer identifies the first node. The final node's next pointer is NULL, a distinguished value meaning that there is no next node. NULL is not a node containing zero. An empty list has head = NULL.

Pointers can be object references or, in an array-based representation, array indices. Here the integer -1 represents NULL; it is never a valid node index. Storage index is different from logical list position: if head is 4, and links are 4 → 1 → 6 → NULL, the first, second and third nodes occupy storage indices 4, 1 and 6.

[DIAGRAM: Three linked nodes follow their next fields rather than consecutive storage indices; asset_slug: linked-pointer-order; caption: The head and next fields give logical order A, B, C even though the storage indices are 4, 1 and 6.]

The complete array representation for this example is below. Blank data belongs to unused slots. The free-list head freeHead = 0 starts a separate chain 0 → 2 → 3 → 5 → NULL of slots available for allocation. The active list has head = 4.

The same next array can link unused slots because no slot belongs to both chains. To create an empty list over a pool of four nodes, set head to -1, freeHead to 0, and link unused nodes 0 → 1 → 2 → 3 → -1. Data can initially be blank. If the fixed pool is exhausted, freeHead is -1 and allocation must fail; an abstract linked list can grow dynamically, but this implementation has a finite capacity. Object-based implementations allocate a node object instead, subject to available memory.

Follow links until the end or a match

Traversal starts at head and repeatedly follows the current node's next link. Incrementing the storage index would visit unrelated or unused slots. Check for NULL before accessing data: in Python, array[-1] normally reads the last element, so forgetting the sentinel check can produce a plausible but wrong result rather than an immediate bounds error.

This Python function models the two arrays in the table. It returns the active data values in list order. Its input contract is a valid acyclic chain ending in -1, with every other link a valid index. The ungraded sandbox lets you change the entry point or a valid link; the assessed traces below remain static.

The successive current values are 4, 1, 6, -1; the output list is ["A", "B", "C"]. On an empty list the loop executes zero times and returns []. A cycle such as 6 → 4 would never reach -1; it violates the contract and would prevent this loop from terminating. The ordinary traversal does not diagnose corrupt links automatically.

Starting the sandbox call at 1 gives B,C; starting at -1 gives an empty result. With entry point 4, redirecting next_link[4] to 6 gives A,C. That last experiment changes reachability only: complete deletion from a fixed pool must also release B's slot to the free chain, as the deletion part will show.

The work at each visited node can change while the traversal stays the same. For numeric nodes, start a total at zero, add data[current] once per visit, then follow the next link. A chain holding 8, -3 and 5 totals 10; an empty chain totals zero. Counting nodes instead increments a counter by one per visit. Return an aggregate after the loop, otherwise only the first node may be processed.

Searching is traversal with a decision at each node. To find the first occurrence of a target, compare data[current] before advancing. Return the current storage index on a match; reaching NULL first means not found. With the table above, finding B visits 4 then 1 and returns 1; finding D visits 4, 1, 6 and returns -1. A match at head needs no advance, and an empty list immediately reports not found. If removal needs the preceding node, remember previous while searching rather than attempting to infer it by subtracting one from the current storage index.