Manipulation of Linked Information Structures and Associated Notations

Key Insight

Accessing and manipulating specific fields within a node is achieved through a clear notation: `F(L)`, where `F` is the field's name and `L` is a 'link variable' (also called a 'pointer variable') that holds the address of the desired node. For instance, `NEXT(NEWCARD)` refers to the `NEXT` field of the node pointed to by the `NEWCARD` link variable. All references to nodes within a program are made either directly via these link variables or constants, or indirectly through link fields embedded within other nodes, allowing for dynamic navigation of complex data arrangements.

Algorithms designed for managing linked information structures utilize this field notation to perform operations. For example, an algorithm to place a new card (`NEWCARD`) face up on top of a pile consists of three steps: first, setting `NEXT(NEWCARD)` to the current `TOP` link; second, updating `TOP` to `NEWCARD` to designate the new card as the top; and third, setting `TAG(TOP)` to 0 to mark the card as face up. Another algorithm to count cards in a pile initializes a counter `N` to 0 and a traversal link `X` to `TOP`, then iteratively increments `N` and updates `X` to `NEXT(X)` until `X` becomes `Λ`. It is critical to distinguish between symbolic names used as variables (e.g., `TOP`, `N`) and those used as field names (e.g., `TAG`, `NEXT`), as field names do not possess a value unless qualified by a non-null link.

At a lower machine level, specific notations are employed: `CONTENTS(address)` refers to the value stored at a given memory location, while `LOC(variable)` denotes the memory address of a variable. The ease and efficiency with which these operations can be carried out are the primary reasons for the importance of the 'linked memory' concept. While assembly language symbols typically stand for addresses, algorithmic notation uses them for values, a frequent point of confusion for beginners. Additionally, a single variable can represent an entire node, with its value being a sequence of fields, allowing for shorthand assignments of structured values, making these techniques an indispensable and accessible part of every programmer's repertoire, irrespective of the programming language used.