# Mutable Linked Lists: exam-level questions

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

For this section, we will be using the `Link` class implementation from lecture:

``````class Link(object):
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def__len__(self):
return 1 + len(self.rest)

def __getitem__(self, i):
if i == 0:
return self.first
return self.rest[i - 1]

def __repr__(self):
if self.rest is empty:
repr(self.rest))``````

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

## Code-Writing questions

### Question 1

Implement a function `validate`, which takes a Link and returns True if the Link is valid.

``````def validate(lst):
"""Returns True if lst is a valid Link.

>>> validate(lst)
True
>>> validate(okay)
True
True
"""
"*** YOUR CODE HERE ***"``````
``````def validate(lst):
if lst is Link.empty:
return True
elif lst.rest is not Link.empty and type(lst.rest) != Link:
return False
else:
return valdiate(lst.rest)``````

### Question 2

Implement a function `count`, which takes a Link and another value, and counts the number of times that `value` is found in the Link.

``````def count(r, value):
"""Counts the number of times VALUE shows up in R.

>>> count(r, 3)
3
>>> count(r, 2)
1
"""
"*** YOUR CODE HERE ***"``````
``````def count(r, value):
if r is Link.empty:
return 0
elif r.first == value:
return 1 + count(r.rest, value)
else:
return count(r.rest, value)``````

### Question 3

Implement a function `extend_link`, which takes two Links, `s1` and `s2`, and mutates `s1` such that it contains the elements of `s2` at its tail. Do this mutatively — don't return anything! Also, make sure `s2` itself does not get attached to `s1`. You may assume `s1` always has at least one element.

``````def extend_link(s1, s2):
"""Extends s1 to include the elements of s2.

>>> s1 = Link(1)
>>> s1
>>> s1.rest is not s2
True
"""
"*** YOUR CODE HERE ***"``````

Hint: This question is similar to the `extend_link` from lecture, except this version mutates the original Link and does not make `s2` part of `s1`.""",

``````def extend_link(s1, s2):
if s2 is Link.empty:
return
elif s1.rest is Link.empty:
else:

### Question 4

Implement a function `deep_map`, which takes an (possibly nested) Link and a function `fn`, and applies `fn` to every element in the Link. If an element is itself a Link, recursively apply `fn` to each of the element's elements.

``````def deep_map(fn, lst):
"""Applies FN to every element in lst.

>>> deep_map(lambda x: x*x, normal)
>>> normal
``````def deep_map(fn, lst):