Deep Link Length

Write a function in Python that returns the length (aka number of elements) of a deep linked list link.

Hint: It might be worth trying the Link Length problem first.

def deep_length(link):
    """
    >>> deep_length(Link(1, Link(Link(2, Link(3)), Link(4))))
    4
    """

    # Your Code Here
Toggle Solution
def deep_length(link):
    if not type(link) is Link:
        return 1
    elif link is Link.empty:
        return 0
    return deep_length(link.first) + deep_length(link.rest)

For this problem, we're merely traversing the deep linked list and returning the number of elements it contains. It doesn't matter if we use the ADT or the Class implementation of linked lists in this case, although this solution is written with the Class implementation because that's what I felt like at the time.

The logic behind our solution is actually not too different from the logic for Link Length: for every element in the link, we want to add however many elements are in link's first position (if it's a link, the length is many elements are in that, if it's a single element the length is just 1), and then add how many elements there are in the rest of link. We can do this with a couple of recursive calls.

But first, the base cases: If the thing we parse in isn't a Link, it's going to be a single element - so we return a length of 1. If the thing we parse in is Link.empty (aka an empty Link), that means there's nothing else in the list and we can return a length of 0.

Finally, if neither of these base cases are satisfied, we recurse by taking the deep_length of link.first and link.rest, and then we add all of that together.

results matching ""

    No results matching ""