Deep Link Length
Write a function in Python that returns the length (aka number of elements) of a deep linked list
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
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
link.rest, and then we add all of that together.