If you need help reviewing Linked Lists, take a look at these resources:

We will be using the following implementation of immutable linked lists. Keep in mind that your code should not depend on the assumption that links are implemented as lists — preserve data abstraction!

```
empty = None
def link(first, rest=empty):
return [first, rest]
def first(s):
return s[0]
def rest(s):
return s[1]
```

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## Concept Questions

### Question 1

What type of object can `first`

be (e.g. int, string, function, etc.)?
What type of object can `rest`

be?

`first`

can be any type of object, even a linked list. `rest`

can only be a
linked list.

### Question 2

Which of the following are valid linked list constructors?

`link(1, 3)`

`link(1, None)`

`link(1, link(4, empty))`

`link(1, empty)`

`link()`

The correct answers are in bold:

`link(1, 3)`

`link(1, None)`

`link(1, link(4, empty))`

`link(1, empty)`

`link()`

### Question 3

Construct a linked list that contains the following elements:

`1, 3, lambda x: x, 'hi'`

`link(1, link(3, link(lambda x: x, link('hi', empty))))`

### Question 4

What is the third element of the following link?

`link('this', link(link('is', link('a', empty)), link('question', empty)))`

`'question'`

### Question 5

What is the length of the linked list in the previous question (i.e. how many elements are in the linked list, not including the elements of nested linked lists?

3

## What would Python print?

### Question 6

```
>>> r = link(1, link(2, link(3, empty)))
>>> first(r)
______1
>>> rest(r)
______(2, (3, None))
>>> rest(rest(r))
______(3, None)
>>> first(rest(r))
______2
>>> first(rest(rest(r)))
______3
```

## Code-Writing Questions

### Question 7

Implement a function `link_to_list`

that takes a linked as an argument,
and returns a list that contains the same elements as the linked list.

```
def link_to_list(lst):
"""Returns a list that contains the same elements as the
linked list.
>>> r = link(1, link(2, link(3, empty)))
>>> link_to_tup(r)
(1, 2, 3)
"""
"*** YOUR CODE HERE ***"
```

A recursive version:

```
def link_to_list(lst):
if lst == empty:
return []
return [first(lst)] + link_to_list(rest(lst))
```

An iterative version:

```
def link_to_list(lst):
new = []
while lst != empty:
new += [first(lst)]
lst = rest(lst)
return new
```

### Question 8

Implement a function `map_link`

that maps a function `f`

onto each element of
a linked list.

```
def map_link(lst, f):
"""Maps f onto each element in the linked list.
>>> r = link(1, link(2, link(3, empty)))
>>> link_to_list(map_link(r, lambda x: x**2))
[1, 4, 9]
"""
"*** YOUR CODE HERE ***"
```

A recursive version:

```
def map_link(lst, f):
if lst == empty:
return empty
return link(f(first(lst)), map_link(rest(lst), f))
```

An iterative version:

```
def map_link(lst, f):
new = empty
while lst != empty:
new = link(f(first(lst)), new)
lst = rest(lst)
while new != empty:
lst = link(first(new), lst)
new = rest(new)
return lst
```