Linear Lists and Basic Data Structure Design Principles

Key Insight

Data inherently contains more structural information than is typically represented directly in a computer. For example, a 'playing card' node might only link to the card beneath it, omitting ways to find cards above or its pile. Most intrinsic features, like card designs or molecular details, are deliberately suppressed. The critical decision of how much structure to represent and its accessibility depends entirely on the operations intended for the data. This emphasizes that computer representations must balance the data's desired function with its intrinsic properties, a fundamental aspect of general design problems.

This functional emphasis extends to computer hardware, specifically memory classification. Computer memory is categorized by its intended use: 'random access memory' (e.g., MIX's main memory) allows high-speed access to any location; 'read-only memory' stores constant information; 'secondary bulk memory' (e.g., MIX's disk units) stores large quantities but has slower access; and 'associative memory' ('content-addressed memory') addresses information by its value rather than its location. Although all are 'memory' units, their specific purposes profoundly influence their design and cost, highlighting how function drives design.

A linear list is formally defined as a sequence of n ≥ 0 nodes X[1], ..., X[n], whose essential structural properties relate only to the relative positions of items in a line. Key characteristics are X[1] being the first node (if n > 0), X[n] being the last, and for 1 < k < n, X[k] is preceded by X[k-1] and followed by X[k+1]. Common operations include accessing/modifying the kth node, inserting/deleting a node at the kth position, combining/splitting lists, copying, determining size, sorting, and searching. Cases for k=1 and k=n are particularly important due to potentially easier access. Designing a single, universally efficient representation for all these operations is challenging, leading to distinctions between linear list types based on their most frequent operations.