Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 ยท Lists and Data Structures

Conses and Lists

Understand how Lisp lists are built from cons cells, how car, cdr and cons work, what dotted pairs are, and how shared structure and destructive changes behave.

The name Lisp comes from LISt Processing, and the list is still the workhorse data structure. But a Lisp list is not an array: it is a chain of small two-slot objects called cons cells. Understanding cons cells explains car, cdr, dotted pairs, why append copies, why push is fast, and why changing one list can unexpectedly change another. This lesson builds that model from the ground up.

The cons cell

A cons cell holds two references: the car (first slot) and the cdr (second slot). The function cons makes one:

LISP
(cons 1 2)      ; => (1 . 2)      a "dotted pair"
(car (cons 1 2)) ; => 1
(cdr (cons 1 2)) ; => 2

A list is a chain of cons cells where each cdr points to the next cell, and the last cdr is NIL (the empty list).

LISP
(cons 1 (cons 2 (cons 3 nil)))   ; => (1 2 3)
(list 1 2 3)                      ; => (1 2 3)   same structure, easier to type
'(1 2 3)                          ; => (1 2 3)   a quoted literal
flowchart LR
    L["list"] --> C1
    subgraph C1["cons"]
      A1["car: 1"] --- D1["cdr"]
    end
    D1 --> C2
    subgraph C2["cons"]
      A2["car: 2"] --- D2["cdr"]
    end
    D2 --> C3
    subgraph C3["cons"]
      A3["car: 3"] --- D3["cdr: NIL"]
    end

The list (1 2 3) is three cons cells. Each cdr points to the rest of the list.

The printer writes a chain ending in NIL without dots. If the last cdr is not NIL, it prints a dot: (1 2 . 3) is two cells where the last cdr is the number 3.

Taking lists apart

LISP
(car '(a b c))     ; => A         the first element
(cdr '(a b c))     ; => (B C)     the REST of the list
(first '(a b c))   ; => A         readable synonym for car
(rest '(a b c))    ; => (B C)     readable synonym for cdr
(second '(a b c))  ; => B
(third '(a b c))   ; => C
(nth 2 '(a b c d)) ; => C         0-based
(nthcdr 2 '(a b c d)) ; => (C D)
(last '(a b c))    ; => (C)       the last CONS, not the last element
(car (last '(a b c))) ; => C
(length '(a b c))  ; => 3
(car nil)          ; => NIL       NIL is safe to take car and cdr of

You can combine car/cdr in one name: cadr is (car (cdr x)), cddr is (cdr (cdr x)), caddr is the third element. Up to four letters work (cadddr). Use first, second and nth in new code for readability.

Here is a stand-in: the cons cell implemented in JavaScript, with a printer that follows Lisp's dot rules. It is not Lisp, but the structure and printing rules are the real ones.

JS Stand-in: cons cells and printing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Building lists

LISP
(cons 0 '(1 2))          ; => (0 1 2)    add to the front: O(1)
(list 1 2 3)             ; => (1 2 3)
(append '(1 2) '(3 4))   ; => (1 2 3 4)  joins lists (copies all but the last)
(list '(1 2) '(3 4))     ; => ((1 2) (3 4))   nested, NOT joined
(reverse '(1 2 3))       ; => (3 2 1)
(make-list 3 :initial-element 0) ; => (0 0 0)
(copy-list '(1 2 3))     ; => (1 2 3)    a fresh top-level copy
(list* 1 2 '(3 4))       ; => (1 2 3 4)  like cons with many leading items

cons adds at the front in constant time and does not change the original list; the new cell simply points to it. This is why Lisp code builds lists backwards and reverses at the end.

push and pop

push and pop are macros on a place that holds a list:

LISP
(defparameter *stack* '())
(push 1 *stack*)      ; *stack* => (1)
(push 2 *stack*)      ; *stack* => (2 1)
(pop *stack*)         ; => 2, and *stack* is (1) again

Both are constant time, which makes lists excellent stacks.

Shared structure

Because cons points to an existing list instead of copying it, two lists can share a tail:

LISP
(defparameter *tail* (list 3 4))
(defparameter *a* (cons 1 *tail*))   ; (1 3 4)
(defparameter *b* (cons 2 *tail*))   ; (2 3 4)

(eq (cdr *a*) (cdr *b*))   ; => T   same tail object

Sharing saves memory but means destructive changes show through both lists:

LISP
(setf (car *tail*) 99)
*a*   ; => (1 99 4)
*b*   ; => (2 99 4)

The rule: do not modify lists you did not create yourself, especially quoted literals. (setf (car '(1 2 3)) 9) modifies a constant and is undefined behavior. Use copy-list or build with list.

Destructive and non-destructive functions

Many list functions have a destructive twin that reuses cells to save memory:

Safe Destructive (may reuse cells)
reverse nreverse
append nconc
remove delete
sort (always destructive!)

Use the safe ones first; use the destructive ones only on lists you own, and always use the return value, not the original variable: (setf lst (nreverse lst)).

Proper lists, dotted pairs, trees

  • A proper list ends in NIL. (listp x) checks for a cons or NIL.
  • A dotted pair (a . b) is a cons whose cdr is not a list; it is the basis of association lists (next lessons).
  • A tree is a list whose elements may be lists. Functions like subst, tree-equal, copy-tree and flatten (which you write) walk both car and cdr.
LISP
(copy-tree '(1 (2 3) 4))              ; copies the nested structure too
(subst 'x 'b '(a (b c) b))            ; => (A (X C) X)
(consp '(1 2))                        ; => T
(atom 5)                              ; => T   (atom = not a cons)
(listp nil)                           ; => T

Circular lists

Because a cdr can point anywhere, a list can point back at itself. SBCL's printer will loop forever (or until memory runs out) printing such a list unless you set *print-circle* to t. Most programs never need circular lists; just know that length on one never returns.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does (cdr '(a b c)) return?

    cdr returns everything after the first element, as a list.
  2. 2. How does Lisp print (cons 1 2)?

    The cdr is not a list, so the printer uses dotted notation.
  3. 3. What does (last '(a b c)) return?

    last returns the final cons cell (a list of one element), not the element itself.
  4. 4. Two lists share a tail and you destructively change the tail. What happens?

    They point to the same cons cells, so the modification shows through both.
  5. 5. Which operation adds an element to the front of a list in constant time?

    cons allocates one new cell pointing at the existing list.

Summary

  • A list is a chain of cons cells; the last cdr is NIL.
  • car/first gets the head, cdr/rest the tail; nth, last, length read further in.
  • cons and push add to the front in O(1); append copies all but its last argument.
  • Lists can share structure, so avoid modifying lists you did not build, and never modify quoted literals.
  • Destructive functions (nreverse, delete, nconc, sort) reuse cells; use their return values.

Next: List Functions