# Recursive Lists: exam-level questions

If you need help reviewing Recursive 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.

## What would Python print?

### Question 1

``````>>> r = link(1, link(link(2, empty), link(4, empty)))
>>> first(r)
______1
>>> first(rest(rest(r)))
______4
>>> first(first(rest(r)))
______2``````

### Question 2

``````>>> r = link(link(1, link(2, empty)), link(3, link(4, empty)))
>>> first(rest(r))
______3
>>> first(rest(first(r)))
______2
>>> first(first(rest(r)))
______IndexError``````

## Code-Writing questions

### Question 3

Implement a function `alternate` which takes a linked list and returns a new linked list that contains every other element in the original linked list.

``````def alternate(lst):
"""Returns a new linked list that contains every other element
of the original.

[1, 3]
[1, 3]
"""
``````def alternate(r):
if r == empty:
return empty
elif rest(r) == empty:
return r
else:

### Question 4

Implement a function `filter_link` which takes a linked list and returns a new linked list that contains only elements that satisfy the given predicate.

``````def filter(pred, lst):
"""Returns a new link that contains elements of lst that
satisfy the predicate.

``````def filter(pred, lst):