A data structure organizes information so operations can use it. An algorithm supplies the steps that solve a problem using that information. Choosing a representation therefore means asking both what operations are needed and what they will cost as the data grows. section 1.0 section 1.1
Start with an abstract data type: specify legal values, available operations, and their effects. Then choose a data structure that implements those choices and analyze its performance. This keeps a convenient representation from quietly dictating the interface—or allowing states that should be impossible. section 2.2 section 1.2
A list, then a stack
An immutable linked list can be defined recursively: it is empty, or it holds a value and a tail list. In C#, Push(value) can return a new record whose tail is the existing list. Representing emptiness with null Value and Tail is concise but permits a purported nonempty list with an invalid tail. For an immutable stack, first specify Push, Peek, Pop, and IsEmpty; a separate empty-stack implementation can reject Peek and Pop while nonempty stacks retain their existing tails. section 1.2 section 2.2
Figure 2.1 Each variable in the example code references a particular immutable stack. Stacks with the same tail can refer to the same immutable object.
The diagram makes an important consequence visible: distinct immutable stacks can share the same tail rather than copy it. section 2.2
The operations may instead come from a search problem. A word list for autocomplete needs enumeration, membership testing, and prefix matches. An interface can state those requirements before comparing representations for search performance. This example concerns an existing word list; efficient updates after insertion or removal are outside its scope. section 5.1
