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 ()):
Link(4)makes a linked list containing 4.Link(4, Link(5))makes a linked list containing 4 and 5.Link(4, 5)is not well formed because the second argument is not a linked list. Don't do that!
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(())
"""
Highly Recommended Question (If Time Allows)
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.