---

E.2.3.1 In General

A List is a Sequence of Cons Cells

A list is a combination or sequence of zero or more elements called cons cells (a primitive object). A list can hold elements of any type, and its length can be easily changed by adding or removing elements.

Finding the Nth element requires looking through N cons cells, so elements farther from the beginning of the list take longer to access. But it is easy to add elements to the list, and remove elements.

Two important differences between lists and vectors is that:

• two or more lists can share part of their structure;
• you can insert or delete elements in a list without copying the whole list.

Lists are Constructed from Cons Cells

Lists are built up from cons cells. A “list” is a series of cons cells, linked together so that the CDR slot of each cons cell holds either the next cons cell or the empty list. The empty list is actually the symbol ‘nil’. 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.