GNU Info
(librep.info)List Structure
List Structure
..............
Each element in a list is given its own cons cell and stored in the
car of that cell. The list is then constructed by having the cdr of a
cell point to the cons cell containing the next element (and hence the
entire rest of the list). The cdr of the cell containing the last
element in the list is `()'. A list of zero elements is represented by
`()'.
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 . ())))))
(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----> ()
+--|--+-----+ +--|--+-----+ +--|--+-----+ +--|--+-----+
| | | |
--> 1 --> 2 --> 3 --> 4
A more complex example, the list `((1 2) (foo bar))' can be drawn as,
+-----+-----+ +-----+-----+
| o | o---------------------------> | o | o----> ()
+--|--+-----+ +--|--+-----+
| |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| o | o----> | o | o----> () | o | o----> | o | o----> ()
+--|--+-----+ +--|--+-----+ +--|--+-----+ +--|--+-----+
| | | |
--> 1 --> 2 --> foo --> bar
automatically generated by info2www version 1.2.2.9