W3cubDocs

Lists and Cons Cells

Lists in Lisp are not a primitive data type; they are built up from cons cells (see Cons Cell Type). A cons cell is a data object that represents an ordered pair. That is, it has two slots, and each slot holds, or refers to, some Lisp object. One slot is known as the CAR, and the other is known as the CDR. (These names are traditional; see Cons Cell Type.) CDR is pronounced “could-er”.

We say that “the CAR of this cons cell is” whatever object its CAR slot currently holds, and likewise for the CDR.

A list is a series of cons cells chained together, so that each cell refers to the next one. There is one cons cell for each element of the list. By convention, the CARs of the cons cells hold the elements of the list, and the CDRs are used to chain the list (this asymmetry between CAR and CDR is entirely a matter of convention; at the level of cons cells, the CAR and CDR slots have similar properties). Hence, the CDR slot of each cons cell in a list refers to the following cons cell.

Also by convention, the CDR of the last cons cell in a list is nil. We call such a nil-terminated structure a proper list³. In Emacs Lisp, the symbol nil is both a symbol and a list with no elements. For convenience, the symbol nil is considered to have nil as its CDR (and also as its CAR).

Hence, the CDR of a proper list is always a proper list. The CDR of a nonempty proper list is a proper list containing all the elements except the first.

If the CDR of a list’s last cons cell is some value other than nil, we call the structure a dotted list, since its printed representation would use dotted pair notation (see Dotted Pair Notation). There is one other possibility: some cons cell’s CDR could point to one of the previous cons cells in the list. We call that structure a circular list.

For some purposes, it does not matter whether a list is proper, circular or dotted. If a program doesn’t look far enough down the list to see the CDR of the final cons cell, it won’t care. However, some functions that operate on lists demand proper lists and signal errors if given a dotted list. Most functions that try to find the end of a list enter infinite loops if given a circular list.

Because most cons cells are used as part of lists, we refer to any structure made out of cons cells as a list structure.