Linked Lists: Conceptual Solutions

BOX AND POINTER DIAGRAMS

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

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

Screen Shot 2019-01-13 at 4.44.43 PM.png

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

Screen Shot 2019-01-13 at 4.47.43 PM.png

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

Screen Shot 2019-01-13 at 4.48.01 PM.png

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 lst.rest is Link.empty:
        return lst.first
    return lst.first + sum_vals(lst.rest)

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 lnk is Link.empty:
        return False
    return y == lnk.first or search(lnk.rest, y)

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 lnk is Link.empty:
        return lnk
    else if lnk.first % 2 != 0:
        return remove_odd_nondestructive(lnk.rest)
    return Link(lnk.first,remove_odd_nondestructive(lnk.rest))

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 lnk is Link.empty:
        return lnk
    else if lnk.first % 2 != 0:
        lnk = remove_odd(lnk.rest)
    else:
        lnk.rest = remove_odd(lnk.rest)
    return lnk