C Interfaces and Implementations: Techniques for Creating Reusable Software

Chapter 7. Lists

A list is a sequence of zero or more pointers. A list with zero pointers is an empty list. The number of pointers in a list is its length. Almost every nontrival application uses lists in some form. Lists so pervade programs that some languages provide them as built-in types; LISP, Scheme, and ML are the best known examples.

Lists are easy to implement, so programmers usually reimplement them for each application at hand, and there’s no widely accepted standard interface for lists, although most application-specific interfaces have many similarities. The List abstract data type described below provides many of the facilities found in most of these application-specific interfaces. Sequences, described in Chapter 11, are another ...