List construction with conscells

There is no list

We have learned that Lisp expressions consist of atoms and lists, but in fact, there is no list object in the background. A list in Lisp is constructed with objects called conscells, or simply CONS.

Conscell is an object holding two pointers, the first points to an element of the list and the second points to the next conscell. That means Lisp lists are unidirectional linked lists.

For historical reasons, the pointers are called car and cdr .

For example, list with a sublist (a (b c) d), will be stored like this:

Proper list ends with a conscell, which has NIL (null pointer) in cdr.

Lisp allows us to construct list directly using CONS function.

>(cons 'a (cons 'b (cons 'c nil)))
(A B C)

The code above produces exactly the same list as when using LIST function, or simply quoted list expression:

>(list 'a 'b 'c)
(A B C)
 
>'(a b c)
(A B C)

The power and simplicity of Lisp originates from the fact that code is a list of lists and atoms, exactly the same structure connected with conscells, as is any user-defined data list. Lisp macros can manipulate the code using any of the functions that manipulate data lists.

Show more examples, cons, car, cdr, link to List Processing Functions. Show functionality of accessors and SETF shenanigans. Link to Cycles. Dotting. Show list with nil element, or (nil) sublist.