Lists and Cons Cells
====================

   Lists in Lisp are not a primitive data type; they are built up from
"cons cells".  A cons cell is a data object that represents an ordered
pair.  It records two Lisp objects, one labeled as the CAR, and the
other labeled as the CDR.  These names are traditional; see *Note Cons
Cell Type::.  CDR is pronounced "could-er."

   A list is a series of cons cells chained together, one cons cell per
element of the list.  By convention, the CARs of the cons cells are the
elements of the list, and the CDRs are used to chain the list: the CDR
of each cons cell is the following cons cell.  The CDR of the last cons
cell is `nil'.  This asymmetry between the CAR and the CDR is entirely
a matter of convention; at the level of cons cells, the CAR and CDR
slots have the same characteristics.

   Because most cons cells are used as part of lists, the phrase "list
structure" has come to mean any structure made out of cons cells.

   The symbol `nil' is considered a list as well as a symbol; it is the
list with no elements.  For convenience, the symbol `nil' is considered
to have `nil' as its CDR (and also as its CAR).

   The CDR of any nonempty list L is a list containing all the elements
of L except the first.