Editing Cons (section)

===Lists===
[[Image:Cons-cells.svg|thumb|left|350px|Cons cell diagram for the list (42 69 613), written with <code>cons</code>: <syntaxhighlight lang="lisp">(cons 42 (cons 69 (cons 613 nil)))</syntaxhighlight> and written with <code>list</code>: <syntaxhighlight lang="lisp">(list 42 69 613)</syntaxhighlight>]]
{{clear}}
In Lisp, lists are implemented on top of cons pairs. More specifically, any list structure in Lisp is either:

#An empty list {{lisp2|()}}, which is a special object usually called {{lisp2|nil}}.
#A cons cell whose {{lisp2|car}} is the first element of the list and whose {{lisp2|cdr}} is a [[list]] containing the rest of the elements.
This forms the basis of a simple, [[Linked list|singly linked list]] structure whose contents can be manipulated with {{lisp2|cons}}, {{lisp2|car}}, and {{lisp2|cdr}}. Note that {{lisp2|nil}} is the only list that is not also a cons pair. As an example, consider a list whose elements are 1, 2, and 3. Such a list can be created in three steps:

#Cons 3 onto {{lisp2|nil}}, the empty list
#Cons 2 onto the result
#Cons 1 onto the result

which is equivalent to the single expression:

 <syntaxhighlight lang="lisp">(cons 1 (cons 2 (cons 3 nil)))</syntaxhighlight>

or its shorthand:

 <syntaxhighlight lang="lisp">(list 1 2 3)</syntaxhighlight>

The resulting value is the list:

 (1 . (2 . (3 . nil)))

i.e.

  *--*--*--nil
  |  |  |
  1  2  3

which is generally abbreviated as:

 (1 2 3)

Thus, {{lisp2|cons}} can be used to add one element to the front of an existing linked list. For example, if ''x'' is the list we defined above, then {{lisp2|(cons 5 x)}} will produce the list:

 (5 1 2 3)

Another useful list procedure is [[Append#Lisp|append]], which [[Concatenation|concatenates]] two existing lists (i.e. combines two lists into a single list).