# Discussion 8: Linked Lists

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Now switch to Pensieve:

**Everyone**: Go to pensieve.co, log in with your @berkeley.edu email, and**enter your group number**(which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

# 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).

**Pro tip:** Groups tend not to ask for help unless they've been stuck for a
looooooong time. Try asking for help sooner. We're pretty helpful! You might
learn something.

# Linked Lists

A linked list is a `Link`

object or `Link.empty`

.

You can mutate a `Link`

object `s`

in two ways:

- Change the first element with
`s.first = ...`

- Change the rest of the elements with
`s.rest = ...`

You can make a new `Link`

object by calling `Link`

:

`Link(4)`

makes a linked list of length 1 containing 4.`Link(4, s)`

makes a linked list that starts with 4 followed by the elements of linked list`s`

.

```
class Link:
"""A linked list is either a Link object or Link.empty
>>> s = Link(3, Link(4, Link(5)))
>>> s.rest
Link(4, Link(5))
>>> s.rest.rest.rest is Link.empty
True
>>> s.rest.first * 2
8
>>> print(s)
<3 4 5>
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
```

**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.

### 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.

`s.first`

to the sum of the first `k-1`

elements in `s.rest`

. Your base case
condition should include `s is Link.empty`

so that you're checking whether `s`

is empty before ever evaluating `s.first`

or `s.rest`

.
`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.
**Discussion time:** When adding up numbers, the intermediate sums depend on the
order. `(1 + 3) + 5`

and `1 + (3 + 5)`

both equal 9, but the first one makes 4
along the way while the second makes 8 along the way. For the same linked list
`s`

and length `k`

, will `sum_rec`

and `sum_iter`

both make the same
intermediate sums along the way?

### Q2: Overlap

Implement `overlap`

, which takes two linked lists of numbers called `s`

and `t`

that are sorted in increasing order and have no repeated elements within each
list. It returns the count of how many numbers appear in both lists.

This can be done in *linear* time in the combined length of `s`

and `t`

by
always advancing forward in the linked list whose first element is smallest
until both first elements are equal (add one to the count and advance both) or
one list is empty (time to return). Here's a
lecture video clip
about this (but the video uses Python lists instead of linked lists).

Take a vote to decide whether to use recursion or iteration. Either way works (and the solutions are about the same complexity/difficulty).

Run in 61A Code```
if s is Link.empty or t is Link.empty:
return 0
if s.first == t.first:
return __________________
elif s.first < t.first:
return __________________
elif s.first > t.first:
return __________________
```

```
k = 0
while s is not Link.empty and t is not Link.empty:
if s.first == t.first:
__________________
elif s.first < t.first:
__________________
elif s.first > t.first:
__________________
return k
```

# Document the Occasion

Please all fill out the attendance form (one submission per person per week).