Linked Lists: Conceptual

Box and Pointer Diagrams

Draw the box and pointer diagrams for the following linked lists.

Link(1, Link(2, Link(3, Link(4))))

Link(6, Link(Link(7, Link(8)), Link(9, Link(10))))

Link(Link(Link(4, Link(8)), Link(12, Link(Link(16), Link(20)))), Link(24))

Code Writing

Write out a function that will sum up all of the values in a linked list (the linked list may be nested). Assume there is at least one value in the list.
def sum_vals(lnk):
>>> lnk = Link(1, Link(2, Link(3, Link(4))))
>>> sum_vals(lnk)
10
    if ______:
        return ______
    return ______

Write out a function that will return true if y is a value in linked list lnk.
def search(lnk, y):
>>> lnk = Link(1, Link(2, Link(3, Link(4))))
>>> search(lnk, 4)
True
>>> search(lnk, 7)
False
    if ______:
        return ______
    return ______

Write out a function that will take in a linked list and remove any links with odd first values from it (by creating a new linked list, not mutating lnk).
def remove_odd_nondestructive(lnk):
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> remove_odd_nondestructive(lnk)
Link(2, Link(4))
>>> lnk
Link(1, Link(2, Link(3, Link(4, Link(5)))))
    if ______:
        return ______
    else if ______:
        return ______
    return ______

Write out a function that will take in a linked list and remove any links with odd first values from it (by mutating, so there should be no calls to the Link constructor).
def remove_odd_mutative(lnk):
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> remove_odd_mutative(lnk)
Link(2, Link(4))
>>> lnk
Link(2, Link(4))
    if ______:
        return ______
    else if ______:
        lnk = ______
    else:
        lnk.rest = ______
    return lnk