What if you want to pack more than two values into a data structure? Does Scheme provide a different kind of data structure for each different number of values?

That turns out not to be necessary. Since pairs can have pairs as components, they are extensible -- whenever you need space for an extra component, just replace one of the components that you already have with a new pair.

In fact, there's a conventional way to do this in Scheme that is very well supported in the language: Let's say that you want to put the integers from 1 to 5 into a data structure. Construct a pair in which the first component is the first integer 1 and the second component is another pair. Construct this second pair so that its first component is the integer 2 and its second component is another pair. Construct this third pair so that it s first component is the integer 3 and its second component is another pair. Construct this fourth pair so that its first component is the integer 4 and its second component is ...

... the integer 5?

You could do that, but the conventional way is to construct yet another pair, with 5 as its first component and an end-marker, denoted by the literal `'()`, as its second component:

```(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))
```
The fact that all the elements of the data structures are in the `car` position of their respective pairs makes it simpler to write procedures to work with them, without having to consider the last element as a special case.

A structure that is built up in this way from pairs, with the end-marker as the second component of the last pair, is called a list. More precisely, a list is either the empty list, `'()`, or else a pair in which the second component is a list.

What's the ``empty list''?

What I've been calling the end-marker is actually a list that contains zero components. It's not a pair -- it's a special value belonging to a type of its own (the null type). You use it when you want something that has the shape of a data structure but has no constituents, or alternatively when you want to mark the terminus of some succession of components in a data structure.

How does Scheme treat lists differently from other pairs in Scheme?

For one thing, they are printed differently:

```> (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))
(1 2 3 4 5)
```
The usual external representation for a list is a pair of parentheses enclosing all of the elements of the list, separated by spaces. (The Scheme 48 implementation attaches a single quotation mark at the front of a list when displaying it as the value of a top-level expression.) The external representation of an empty list is just a pair of parentheses, with nothing between them.

This document is available on the World Wide Web as

`http://www.math.grin.edu/~stone/scheme-web/lists.html`

created August 6, 1995
last revised December 29, 1995