# Common Lisp/Basic topics/Lists

*This module is***far from finished**. Improvements are welcome.

**Lists** in common lisp are built up from pairs called *cons cells*. Each cell has two parts, historically named **car** (for the first part) and **cdr** (for the remainder).

```
(car . cdr)
```

Lists are implemented with cons cells by having the cdr of the first cell point to another cons cell.

The empty list is also known as nil, it's written representation is either the literal nil or the empty list: ().

You can create a list by using cons to construct a new cons cell with a left and right hand part:

```
(cons 'a '()) ⇒ (A)
(cons 'a '(b)) ⇒ (A B)
(cons 'a (cons 'b (cons 'c nil))) ⇒ (A B C)
```

Keep in mind that it is possible to create a cons cell which is not a list:

```
(cons 'a 'b) ⇒ (A . B)
```

This is called a dotted list. To be a proper list, the final cdr in the chain of cons cells must point to the empty list (nil). You can also create a list with the function **list**:

```
(list 'a 'b 'c) ⇒ (A B C)
```

which is equivalent to:

```
(cons 'a (cons 'b (cons 'c '()))) ⇒ (A B C)
(cons 'a (cons 'b (cons 'c nil))) ⇒ (A B C)
(cons 'a '(b c)) ⇒ (A B C)
'(a b c) ⇒ (A B C)
```

You can access the members of a list with the functions **car** (or **first**) and **cdr** (or **rest**):

```
(setf list '(a b c))
(car list) ⇒ a
(first list) ⇒ a
(cdr list) ⇒ (b c)
(rest list) ⇒ (b c)
```

Common Lisp also defines the functions **second**, **third** and **fourth** (on up to **tenth**). Note that **second** is not the same as **cdr** or **rest**. **cdr** and **rest** both return the remaining list after the first element, while **second** returns the second item in the list:

```
(rest list) ⇒ (b c)
(second list) ⇒ b
(third list) ⇒ c
(fourth list) ⇒ nil
```

Lists are sequences, so functions that operate on sequences also operate on lists:

```
(subseq list 0 1) ⇒ (a)
(subseq list 0 2) ⇒ (a b)
```

The function **nth** also allows you to retrieve selected items from a list:

```
(nth 0 list) ⇒ a
```

Note that the first item in a list is the 0th. Common Lisp also has several forms (functions and macros) for operating on the contents of lists. **mapcar** can be used to process each element of a list one at a time to build up a new list:

```
(defun add2 (n)
(+ 2 n))
(mapcar #'add2 '(1 2 3)) ⇒ (3 4 5)
```

In that example, we were mapping over a single list so we used a unary function (a function of one argument). The `#'` is a special way to pass a function as an argument into a function. We will talk more about it in the next chapter. It is also possible to map over more than one list - the function must then take the same number of arguments as there are lists:

```
(mapcar #'+ '(1 2 3) '(4 5 6)) ⇒ (5 7 9)
```