A cons cell is an object comprising two pointers named the CAR and the CDR. Each of them can point to any Lisp object.
A list is a series of cons cells, linked together so that the CDR of each cons cell points either to another cons cell or to the empty list. See section Lists, for functions that work on lists. Because most cons cells are used as part of lists, the phrase list structure has come to refer to any structure made out of cons cells.
The names CAR and CDR have only historical meaning now. The
original Lisp implementation ran on an IBM 704 computer which
divided words into two parts, called the "address" part and the
"decrement"; CAR was an instruction to extract the contents of
the address part of a register, and CDR an instruction to extract
the contents of the decrement. By contrast, "cons cells" are named
for the function cons that creates them, which in turn is named
for its purpose, the construction of cells.
Because cons cells are so central to Lisp, we also have a word for "an object which is not a cons cell". These objects are called atoms.
The read syntax and printed representation for lists are identical, and consist of a left parenthesis, an arbitrary number of elements, and a right parenthesis.
Upon reading, each object inside the parentheses becomes an element
of the list. That is, a cons cell is made for each element. The
CAR of the cons cell points to the element, and its CDR points
to the next cons cell of the list, which holds the next element in the
list. The CDR of the last cons cell is set to point to nil.
A list can be illustrated by a diagram in which the cons cells are
shown as pairs of boxes. (The Lisp reader cannot read such an
illustration; unlike the textual notation, which can be understood by
both humans and computers, the box illustrations can be understood only
by humans.) The following represents the three-element list (rose
violet buttercup):
___ ___ ___ ___ ___ ___
|___|___|--> |___|___|--> |___|___|--> nil
| | |
| | |
--> rose --> violet --> buttercup
In this diagram, each box represents a slot that can refer to any Lisp object. Each pair of boxes represents a cons cell. Each arrow is a reference to a Lisp object, either an atom or another cons cell.
In this example, the first box, the CAR of the first cons cell,
refers to or "contains" rose (a symbol). The second box, the
CDR of the first cons cell, refers to the next pair of boxes, the
second cons cell. The CAR of the second cons cell refers to
violet and the CDR refers to the third cons cell. The
CDR of the third (and last) cons cell refers to nil.
Here is another diagram of the same list, (rose violet
buttercup), sketched in a different manner:
--------------- ---------------- ------------------- | car | cdr | | car | cdr | | car | cdr | | rose | o-------->| violet | o-------->| buttercup | nil | | | | | | | | | | --------------- ---------------- -------------------
A list with no elements in it is the empty list; it is identical
to the symbol nil. In other words, nil is both a symbol
and a list.
Here are examples of lists written in Lisp syntax:
(A 2 "A") ; A list of three elements.
() ; A list of no elements (the empty list).
nil ; A list of no elements (the empty list).
("A ()") ; A list of one element: the string "A ()".
(A ()) ; A list of two elements: A and the empty list.
(A nil) ; Equivalent to the previous.
((A B C)) ; A list of one element
; (which is a list of three elements).
Here is the list (A ()), or equivalently (A nil),
depicted with boxes and arrows:
___ ___ ___ ___
|___|___|--> |___|___|--> nil
| |
| |
--> A --> nil
Go to the first, previous, next, last section, table of contents.