Example
List in scheme are nothing else than a series of pairs nested in each other in the cdr of a cons. And the last cdr of a proper list is the empty list '().
To create the list (1 2 3 4), we'd have something like this:
(cons 4 '())
> (4)
(cons 3 (cons 4 '()))
> (3 4)
(cons 2 (cons 3 (cons 4 '())))
> (2 3 4)
(cons 1 (cons 2 (cons 3 (cons 4 '()))))
> (1 2 3 4)
As you can see, a list in scheme is a linked list made out of pairs. For that reason, adding an object to the front of the list takes almost no time, but appending an element at the end of the list forces the interpreter to walk accross the whole list.
