## Linked Lists

A linked list is either an empty linked list (`Link.empty`) or a first value and the rest of the linked list.

``````class Link:
"""
>>> s = Link(1, Link(2, Link(3)))
>>> s
Link(1, Link(2, Link(3)))
"""
empty = ()

def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest

def __repr__(self):
if self.rest is not Link.empty:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), rest_str)``````

To check if a `Link` is empty, compare it against the class attribute `Link.empty`. For example, the below function prints out whether or not the link it is handed is empty:

``````def test_empty(link):
if link is Link.empty:
print('This linked list is empty!')
else:
print('This linked list is not empty!')``````

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (`first`) and a reference to another linked list (`rest`) which contains the rest of the values in the list.

### Question 1: Link to List

Write a function `link_to_list` that converts a given `Link` to a Python list.

``````def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.

>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> link_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q link_to_list``

### Question 2: Every Other

Implement `every_other`, which takes a linked list `s`. It mutates `s` such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

``````>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True``````

If `s` contains fewer than two elements, `s` remains unchanged.

Do not return anything! `every_other` should mutate the original list.

``````def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q every_other``

### Question 3: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function useful.

``````def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.

>>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
>>> print_link(s) # unchanged
<1 <2 3> 4>
>>> print_link(deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5))))))
<<2 <4 6> 8> <<10>>>
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q deep_map``

### Question 4: Mutable Mapping

Implement `deep_map_mut(fn, link)`, which applies a function `fn` onto all elements in the given linked list `link`. If an element is itself a linked list, apply `fn` to each of its elements, and so on.

Your implementation should mutate the original linked list. Do not create any new linked lists.

Hint: The built-in `isinstance` function may be useful.

``````>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False``````
``````def deep_map_mut(fn, link):
"""Mutates a deep link by replacing each item found with the
result of calling fn on the item.  Does NOT create new Links (so
no use of Link's constructor)

Does not return the modified Link object.

>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> deep_map_mut(lambda x: x * x, link1)
>>> print_link(link1)
<9 <16> 25 36>
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q deep_map_mut``

### Question 5: Slice

Implement a function `slice_link` that slices a given `link`. `slice_link` should slice the `link` starting at `start` and ending one element before `end`, as with a normal Python list.

``````def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).

>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> new = slice_link(link, 1, 4)
>>> print_link(new)
<1 4 1>
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q slice_link``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``