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

return [first, rest]

def first(s):
return s

def rest(s):
return s``````

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?

1. `link(1, 3)`
2. `link(1, None)`
3. `link(1, link(4, empty))`
4. `link(1, empty)`
5. `link()`

The correct answers are in bold:

1. `link(1, 3)`
2. `link(1, None)`
3. `link(1, link(4, empty))`
4. `link(1, empty)`
5. `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

(1, 2, 3)
"""

A recursive version:

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

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.

[1, 4, 9]
"""

A recursive version:

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