A list is recursively composed of a head and a tail, which is a (possibly empty) list itself
The building blocks of lists are the cons cells
Every such cell is allocated by an activation of the cons function
An illustration list construction and list selection. We first construct a list (d c b a) and we bind it to the variable lst. Next we select the first element, the tail of lst, the second element, and the second tail of lst.
The constructor function cons takes an element e and a list f and constructs a new list. As illustrated above cons makes exactly one new cons cell, and no kind of list copying is involved at all.
The selector car returns the first element of the list. A better name of car would be head .
The selector cdr returns the list consisting of all but the first element in the list. A better name of cdr would be tail .
A proper list is always terminated by the empty list
In Scheme the empty list is denoted '(). When we in this context talk about the termination of the list we mean the value we get by following the cdr references to the end of the list structure.