Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 38 ยท Lists and Recursion

Pairs and Lists

Understand the pair, the building block of Lisp lists. Learn cons, car, cdr, list, quote, dotted pairs, list functions and why lists are linked chains.

Lisp is named for list processing, and lists are still the most important data structure in Racket and Scheme. They are built from just one idea, the pair, and everything else (functions, algorithms, even the program text) follows from it. In this lesson you learn how pairs make lists, how to take them apart, and what the printed forms mean.

The Run examples use the stand-in interpreter's pairs; they behave like Racket's immutable pairs.

The pair

A pair holds exactly two values. cons builds one; car and cdr read the two halves (historically "contents of address register" and "contents of decrement register", now just first and rest):

RACKET
(define p (cons 1 2))
(car p)   ; 1
(cdr p)   ; 2
p         ; '(1 . 2)   a "dotted pair"

Lists are chains of pairs

A list is either the empty list '() (also null or empty), or a pair whose cdr is a list. So (list 1 2 3) is really:

RACKET
(cons 1 (cons 2 (cons 3 '())))
flowchart LR
    A["1 | โ€ข"] --> B["2 | โ€ข"] --> C["3 | โ€ข"] --> D["'()"]

Three pairs, each pointing to the next, ending in the empty list.

This is a linked list. car of a list is its first element; cdr is the list of everything else. A list with a non-list cdr at the end prints as a dotted pair such as '(1 2 . 3).

cons, car and cdr

Notice that (cons 0 xs) does not change xs. Pairs are immutable: cons makes a new pair that shares the old list as its tail. That is why adding to the front of a list is instant, however long it is.

Writing lists

There are three equivalent ways:

RACKET
(list 1 2 3)                    ; build by calling list; arguments are evaluated
'(1 2 3)                        ; quote: a literal list, nothing evaluated
(cons 1 (cons 2 (cons 3 '())))  ; by hand

The difference between list and quote matters when the elements are expressions:

RACKET
(list (+ 1 2) 'a)   ; '(3 a)
'((+ 1 2) a)        ; '((+ 1 2) a)   the + expression is just data

Quasiquote lets you mix both. A backquote starts a template and a comma evaluates one part:

RACKET
`(1 ,(+ 1 1) 3)     ; '(1 2 3)
list versus quote

Lists can contain anything, including other lists, so '(1 (2 3) 4) has length three.

The essential list functions

Function Meaning Example
(first lst) / car First element (first '(a b c)) is 'a
(rest lst) / cdr Everything but the first (rest '(a b c)) is '(b c)
(null? lst) / empty? Is it the empty list? (null? '()) is #t
(pair? x) Is it a pair? (pair? '(1)) is #t
(length lst) Number of elements (length '(a b c)) is 3
(append a b) Join lists (append '(1 2) '(3)) is '(1 2 3)
(reverse lst) Reverse (reverse '(1 2 3)) is '(3 2 1)
(list-ref lst n) Element at index (list-ref '(a b c) 1) is 'b
(member x lst) Sublist starting at x, or #f (member 2 '(1 2 3)) is '(2 3)
(take lst n) / (drop lst n) First/remaining n (take '(1 2 3) 2) is '(1 2)
(range n) 0 to n-1 (range 4) is '(0 1 2 3)
Common list functions

Empty list and nesting

The empty list '() is the base case of nearly every list algorithm. In Racket, (first '()) is an error; always check empty? first. Nested lists model trees:

RACKET
(define tree '((1 2) (3 (4 5))))
(car (cdr (car (cdr tree))))   ; the first element of the second child's tail

cadr, cddr, caddr, and the other c...r combinations read as a path: cadr is "car of cdr", the second element.

Why a linked list?

The structure explains the performance. cons, first and rest are constant time, but list-ref and length must walk the chain, taking time proportional to the length. For random access use a vector (a later lesson). Lists shine for sequential processing and for building results step by step, and recursion follows their shape, which is the topic of the next lesson.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is (cdr '(a b c))?

    cdr returns everything after the first element.
  2. 2. How is (list 1 2 3) represented internally?

    A list is nested pairs: (cons 1 (cons 2 (cons 3 '()))).
  3. 3. What does (cons 0 xs) do to xs?

    Pairs are immutable; cons creates a new pair pointing at the existing list.
  4. 4. What does '((+ 1 2) a) contain as its first element?

    Quote suppresses evaluation, so (+ 1 2) stays a three-element list.

Summary

  • A pair holds two values (cons, car, cdr); a list is a chain of pairs ending in '().
  • Pairs are immutable; cons shares tails, so prepending is cheap.
  • Write lists with list, quote or quasiquote.
  • Know first, rest, null?, length, append, reverse, list-ref, member.
  • length and list-ref walk the chain, so lists suit sequential work.

Next: Recursion Basics