Fundamental Concepts of Information Structures and Data Representation

Key Insight

Computer programs fundamentally operate on tables of information that are not mere numerical values but possess important structural relationships between data elements. These structures range from simple linear lists (with properties like first, last, preceding, following elements, and total count) to complex two-dimensional or n-dimensional arrays, hierarchical tree structures, or intricate multilinked configurations, similar to those found in a human brain. A thorough understanding of these structural relationships and the techniques for their representation and manipulation within a computer is essential for effective programming.

The basic building blocks of these information structures are called 'nodes,' which may also be referred to as 'records,' 'entities,' or 'elements.' Each node typically occupies one or more consecutive words in computer memory and is internally organized into distinct, named parts known as 'fields.' An 'address,' 'link,' 'pointer,' or 'reference' serves as the memory location of a node's first word, often taken as an absolute memory location for simplicity. A special 'null link,' denoted by the Greek letter Lambda (Λ), signifies a link to no node, and it is commonly represented by the value 0 in computer programs, assuming location 0 is not used for actual nodes.

The contents of any field within a node can represent various data types, including numbers, alphabetic characters, or crucially, other links, which enable the construction of complex interconnections. For example, a node representing a playing card might contain fields like TAG (e.g., 1 for face down, 0 for face up), SUIT (1-4 for clubs, diamonds, hearts, spades), RANK (1-13 for ace to king), NEXT (a link to the card below it in a pile), and TITLE (a five-character name). The concept of introducing links to other data elements is extremely important in computer programming, as these links are the key to efficiently representing and navigating complex structures, forming the basis of the 'linked memory' paradigm.