Each element in a list is given its own cons cell and stored in the car of
that cell. The list object is then constructed by making the cdr of a cell
contain the cons cell of the next element (and hence the whole tail of the
list). The cdr of the cell containing the last element in the list is
nil. A list of zero elements is represented by the symbol nil.
The read syntax of a list is an opening parenthesis, followed by the read syntax of zero or more space-separated objects, followed by a closing parenthesis. Alternatively, lists can be constructed `manually' using dotted-pair notation.
All of the following examples result in the same list of five elements: the numbers from zero to four.
(0 1 2 3 4) (0 . (1 . (2 . (3 . (4 . nil))))) (0 1 2 . (3 4))
An easy way to visualise lists and how they are constructed is to see each cons cell in the list as a separate box with pointers to its car and cdr,
+-----+-----+
| o | o----> cdr
+--|--+-----+
|
--> car
Complex box-diagrams can now be drawn to represent lists. For example the
following diagram represents the list (1 2 3 4).
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| o | o----> | o | o----> | o | o----> | o | o----> nil
+--|--+-----+ +--|--+-----+ +--|--+-----+ +--|--+-----+
| | | |
--> 1 --> 2 --> 3 --> 4
A more complex example, the list ((1 2) (foo bar)) can be drawn as,
+-----+-----+ +-----+-----+
| o | o---------------------------> | o | o----> nil
+--|--+-----+ +--|--+-----+
| |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| o | o----> | o | o----> nil | o | o----> | o | o----> nil
+--|--+-----+ +--|--+-----+ +--|--+-----+ +--|--+-----+
| | | |
--> 1 --> 2 --> foo --> bar
Sometimes when manipulating complex list structures it is very helpful to make a diagram of what it is that's being manipulated.
Go to the first, previous, next, last section, table of contents.