(lispref.info)List Type


Next: Array Type Prev: Sequence Type Up: Programming Types

List Type
---------

   A "list" is a series of cons cells, linked together.  A "cons cell"
is an object comprising two pointers named the CAR and the CDR.  Each
of them can point to any Lisp object, but when the cons cell is part of
a list, the CDR points either to another cons cell or to the empty
list.  Note: Lists, for functions that work on lists.

   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, any object inside the parentheses is made into 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 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 both
humans and computers, the box illustrations can only be understood by
humans.)  The following represents the three-element list `(rose violet
buttercup)':

         ___ ___      ___ ___      ___ ___
        |___|___|--> |___|___|--> |___|___|--> nil
          |            |            |
          |            |            |
           --> rose     --> violet   --> buttercup

   In the 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

* Dotted Pair Notation
An alternative syntax for lists.
* Association List Type
A specially constructed list.

automatically generated by info2www