Linked Lists: basic-level questions

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

• Albert's and Robert's slides

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?

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()

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 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?

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 ***"

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

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 ***"

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

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