List Pattern

All programming languages provide a feature to collect data in some sort of container one way or another. In A++ collections are implemented as lists and dictionaries.

Lists are implemented as linked lists of pairs. A pair is composed of a head and a tail. The head points to a data item and the tail points to the next pair in the list.

The tail in the last pair of the list points to a special element called `nil' or `null'. It is the programmer's responsibility to make sure that a list is terminated with the element `nil'.

In order to work with pairs and lists the following abstractions are needed as a minimum:

• cons the constructor of a pair
• car the selector of the head of a pair
• cdr the selector of the tail of a pair
• nullp a predicate to check, whether the list is empty
• pairp a predicate to check, whether the object is a pair

The section lists:basics presents these abstractions and many more that can be used in the list context.

A head of a pair may be anything, i.e also a reference of another pair. This way it is possible to construct lists of lists, providing the power to build a tree or any other network structure.

Georg P. Loczewski 2004-03-05

Impressum und Datenschutz