# 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
```

```
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.