Discussion 7: Linked Lists

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

Getting Started

Everybody say your name and your birthday and then tell the group about your favorite birthday party you've attended (either for your birthday or someone else's).

Linked Lists

A linked list is a Link object or (), the empty tuple.

You can make a new Link object by calling Link. The second argument to Link should always be a a linked list (another Link object or ()):

Drawing time: Pick a way for your group to draw diagrams. Paper, a whiteboard, or a tablet, are all fine. If you don't have anything like that, ask another group in the room if they have extra paper. You can also use this drawing tool to draw a linked list.

Q1: Sum Two Ways

Implement both sum_rec and sum_iter. Each one takes a linked list of numbers s and a non-negative integer k and returns the sum of the first k elements of s. If there are fewer than k elements in s, all of them are summed. If k is 0 or s is empty, the sum is 0.

Use recursion to implement sum_rec. Don't use recursion to implement sum_iter; use a while loop instead.

To get started on the recursive implementation, consider the example a = Link(1, Link(6, Link(8))) and the call sum_rec(a, 2). Write down the recursive call to sum_rec that would help compute sum_rec(a, 2). Then, write down what that recursive call should return. Discuss how this return value is useful in computing the return value of sum_rec(a, 2).

def sum_rec(s: LinkedList[int], k: int) -> int:
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_rec(a, 2)
    7
    >>> sum_rec(a, 5)
    15
    >>> sum_rec((), 1)
    0
    """
    # Use a recursive call to sum_rec; don't call sum_iter


def sum_iter(s: LinkedList[int], k: int) -> int:
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_iter(a, 2)
    7
    >>> sum_iter(a, 5)
    15
    >>> sum_iter((), 1)
    0
    """
    # Don't call sum_rec or sum_iter

Hint 1: Recursive Version (at the end)

Hint 2: Iterative Version (at the end)

Q2: Print Every Other

Implement print_every_other, which takes a linked list s and prints every other element of s, starting with the first, each on its own line. It prints nothing if s is empty. It returns None, which should happen automatically; you don't need a return statement.

def print_every_other(s: LinkedList) -> None:
    """Print every other element of linked list s, starting with the first.

    >>> sentence = Link('I', Link('have', Link('love', Link('for', Link('Oski')))))
    >>> print_every_other(sentence)
    I
    love
    Oski
    >>> print_every_other(Link(1, Link(2, Link(3, Link(4)))))
    1
    3
    >>> print_every_other(Link(5))
    5
    >>> print_every_other(())
    """

Linked list problems often appear on exams. Here's one:

Q3: Linked Sum

This was Question 6 on the Summer 2016 61A Midterm.

Implement linked_sum, which takes a linked list of positive integers s and a non-negative integer total. It returns the number of ways that adding up items in s can sum up to total. Each item can be used more than once.

def linked_sum(s: LinkedList[int], total: int) -> int:
    """Return the number of combinations of elements in s that
    sum up to total.

    >>> # Four combinations: 1 1 1 1 , 1 1 2 , 1 3 , 2 2
    >>> linked_sum(Link(1, Link(2, Link(3, Link(5)))), 4)
    4
    >>> linked_sum(Link(2, Link(3, Link(5))), 1)
    0
    >>> # One combination: 2 3
    >>> linked_sum(Link(2, Link(4, Link(3))), 5)
    1
    """
    if ____________________________:
        return 1
    elif ____________________________:
        return 0
    else:
        with_first = ____________________________
        without_first = ____________________________
        return ____________________________

Hints

Hint 1: Recursive Version

Add s.first to the sum of the first k-1 elements in s.rest. Your base case condition should include not isinstance(s, Link) so that you're checking whether s is empty before ever evaluating s.first or s.rest.

Hint 2: Iterative Version

Introduce a new name, such as total, then repeatedly (in a while loop) add s.first to total, set s = s.rest to advance through the linked list, and reduce k by one.