Convert to List
Write a function in Python that creates and returns a regular list based off a linked list lnk
.
def convert_to_list(lnk):
"""
>>> convert_to_list(Link.empty)
[]
>>> convert_to_list(Link(1, Link(2, Link(3))))
[1, 2, 3]
"""
# Your Code Here
def convert_to_list(link):
result = []
def convert(l):
if l is Link.empty:
return result
result.append(l.first)
return convert(l.rest)
return convert(link)
In this problem, we need to create a new list to return as a result, but we also need to be able to modify it recursively (because how else are you going to traverse a linked list?) - therefore, we use a helper function to stop us from rewriting result
every time we try to recurse along the list.
Our base case, as the first doctest shows, is what happens if our linked list is empty - if that's the case, only an empty list gets returned. If not, we append the first element onto the end of result
(recall that this is the same as result += [l.first]
). Then, we wish to recurse along the rest of the linked list until we hit that base case of Link.empty
.
And finally, to top it off, we want to actually call our helper function, otherwise nothing would be done.