# Lab 5: Linked Lists

*Due at 11:59pm on 07/07/2016.*

## Starter Files

Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Submission

By the end of this lab, you should have submitted the lab with
`python3 ok --submit`

. You may submit more than once before the
deadline; only the final submission will be graded.

- Questions 1, 2, and 3 must be completed in order to receive credit for this lab. Starter code for questions 2 and 3 is in lab05.py.
- Questions 4 through 11 (Coding) are
**optional**.*It is recommended that you complete these problems on your own time.*Starter code for these questions is in lab05_extra.py.

# Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

## List Comprehension

List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

```
>>> [i**2 for i in [1, 2, 3, 4] if i%2 == 0]
[4, 16]
```

is equivalent to

```
>>> lst = []
>>> for i in [1, 2, 3, 4]:
... if i % 2 == 0:
... lst += [i**2]
>>> lst
[4, 16]
```

The general syntax for a list comprehension is

`[<expression> for <element> in <sequence> if <conditional>]`

The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."

Note: The`if`

clause in a list comprehension is optional.

## Linked Lists

Python has many built-in types of sequences: lists, ranges, and strings, to name
a few. In this lab, we instead construct our own type of sequence called a
*linked list*. A linked list is a simple type of sequence that is comprised of
multiple *links* that are connected.

Each `link`

is a pair where the `first`

element is an item in the linked list,
and the `second`

element is another `link`

.

Constructors:

`link(first, rest)`

: Construct a linked list with`first`

element and the next link`rest`

.`empty`

: The empty linked list.

Selectors

`first(s)`

: Returns the first element in the given linked list`s`

.`rest(s)`

: Returns the rest of the linked list`s`

.

Other

`is_link(s)`

: Returns`True`

if`s`

is a linked list.`print_link(s)`

: Prints out the linked list`s`

.

We can construct the Linked list shown above by using the constructors. The
`first`

element of this Linked list is 12 while the `rest`

is another Linked
list that contains 99 and 37:

```
>>> x = link(12, link(99, link(37)))
>>> first(x)
12
>>> first(rest(x))
99
>>> first(rest(rest(x)))
37
```

Note: Notice that we can just use`link(37)`

instead`link(37, empty)`

. This is because the second argument of the`link`

constructor has a default argument of`empty`

.

# Required Questions

## What Would Python Display?

### Question 1: WWPD: Lists?

What would Python display? Try to figure it out before you type it into the interpreter!

Use OK to test your knowledge with the following "What Would Python Display?" questions:

`python3 ok -q lists -u`

```
>>> [x*x for x in range(5)]
______[0, 1, 4, 9, 16]
>>> [n for n in range(10) if n % 2 == 0]
______[0, 2, 4, 6, 8]
>>> ones = [1 for i in ["hi", "bye", "you"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]
______[1, 1, 1, '6', '3', '8', '4']
>>> [i+5 for i in [n for n in range(1,4)]]
______[6, 7, 8]
```

```
>>> [i**2 for i in range(10) if i < 3]
______[0, 1, 4]
>>> lst = ['hi' for i in [1, 2, 3]]
>>> print(lst)
______['hi', 'hi', 'hi']
>>> lst + [i for i in ['1', '2', '3']]
______['hi', 'hi', 'hi', '1', '2', '3']
```

## Coding Practice

### Question 2: Coordinates

Implement a function `coords`

that takes a function `fn`

, a sequence `seq`

,
and a `lower`

and `upper`

bound on the output of the function. `coords`

then
returns a list of coordinate pairs (lists) such that:

- Each (x, y) pair is represented as
`[x, fn(x)]`

- The x-coordinates are elements in the sequence
- The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)

See the doctest for examples.

Note: your answer can only beone line long. You should make use of list comprehensions!

```
def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> fn = lambda x: x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
"*** YOUR CODE HERE ***"
return ______
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]
```

Use OK to test your code:

`python3 ok -q coords`

### Question 3: Is Sorted?

Implement the `is_sorted(lst)`

function, which returns `True`

if the linked
list `lst`

is sorted in increasing from left to right. If two adjacent elements
are equal, the linked list can still be considered sorted.

```
def is_sorted(lst):
"""Returns True if the linked list is sorted.
>>> lst1 = link(1, link(2, link(3, link(4))))
>>> is_sorted(lst1)
True
>>> lst2 = link(1, link(3, link(2, link(4, link(5)))))
>>> is_sorted(lst2)
False
>>> lst3 = link(3, link(3, link(3)))
>>> is_sorted(lst3)
True
"""
"*** YOUR CODE HERE ***"
if lst == empty or rest(lst) == empty::
return True
elif first(lst) > first(rest(lst)):
return False
return is_sorted(rest(lst))
```

Use OK to test your code:

`python3 ok -q is_sorted`

# Optional Questions

## Coding Practice

**Note**: The following questions are in lab05_extra.py.

### Question 4: Sum

Write a function that takes in a linked list `lst`

and a function `fn`

which
is applied to each number in `lst`

and returns the sum. If the linked list is
empty, the sum is 0.

```
def sum_linked_list(lst, fn):
"""Applies a function FN to each number in LST and returns the sum
of the resulting values
>>> square = lambda x: x * x
>>> double = lambda y: 2 * y
>>> lst1 = link(1, link(2, link(3, link(4))))
>>> sum_linked_list(lst1, square)
30
>>> lst2 = link(3, link(5, link(4, link(10))))
>>> sum_linked_list(lst2, double)
44
"""
"*** YOUR CODE HERE ***"
if lst == empty:
return 0
return fn(first(lst)) + sum_linked_list(rest(lst), fn)
# Iterative Solution
def sum_linked_list(lst, fn):
sum = 0
while lst != empty:
sum += fn(first(lst))
lst = rest(lst)
return sum
```

Use OK to test your code:

`python3 ok -q sum_linked_list`

### Question 5: Change

Write a function that takes in a linked list, `lst`

, and two elements,
`s`

and `t`

. The function returns lst but with all instances of `s`

replaced with `t`

.

```
def change(lst, s, t):
"""Returns a link matching lst but with all instances of s
replaced by t. If s does not appear in lst, then return lst
>>> lst = link(1, link(2, link(3)))
>>> new = change(lst, 3, 1)
>>> print_link(new)
1 2 1
>>> newer = change(new, 1, 2)
>>> print_link(newer)
2 2 2
>>> newest = change(newer, 5, 1)
>>> print_link(newest)
2 2 2
"""
"*** YOUR CODE HERE ***"
if lst == empty:
return lst
if first(lst) == s:
return link(t, change(rest(lst), s, t))
return link(first(lst), change(rest(lst), s, t))
```

Use OK to test your code:

`python3 ok -q change`

### Question 6: Link to List

Write a function `link_to_list`

that takes a linked list and converts it to a Python list.

Hint: To check if a linked list is empty, you can use`lst == empty`

. Also, you can combine two Python lists using`+`

.

```
def link_to_list(linked_lst):
"""Return a list that contains the values inside of linked_lst
>>> link_to_list(empty)
[]
>>> lst1 = link(1, link(2, link(3, empty)))
>>> link_to_list(lst1)
[1, 2, 3]
"""
"*** YOUR CODE HERE ***"
if linked_lst == empty:
return []
else:
return [first(linked_lst)] + link_to_list(rest(linked_lst))
# Iterative version
def link_to_list_iterative(linked_lst):
"""
>>> link_to_list_iterative(empty)
[]
>>> lst1 = link(1, link(2, link(3, empty)))
>>> link_to_list_iterative(lst1)
[1, 2, 3]
"""
new_lst = []
while linked_lst != empty:
new_lst += [first(linked_lst)]
linked_lst = rest(linked_lst)
return new_lst
```

Use OK to test your code:

`python3 ok -q link_to_list`

### Question 7: Insert

Implement the `insert`

function that creates a copy of the original
list with an item inserted at the specific index. If the index is
greater than the current length, you should insert the item
at the end of the list. Review your solution for `change`

if you are
stuck.

Hint: This will be much easier to implement using recursion, rather than using iteration!

Note: Remember we are not actually inserting the item into theoriginallinked list. Instead, we are creating a copy of the original linked list, but with the provided item added at the specified index. The original linked list stays the same.

```
def insert(lst, item, index):
"""Returns a link matching lst but with the given item inserted at the
specified index. If the index is greater than the current length, the item
is appended to the end of the list.
>>> lst = link(1, link(2, link(3)))
>>> new = insert(lst, 9001, 1)
>>> print_link(new)
1 9001 2 3
>>> newer = insert(new, 9002, 15)
>>> print_link(newer)
1 9001 2 3 9002
"""
"*** YOUR CODE HERE ***"
if lst == empty:
return link(item, empty)
elif index == 0:
return link(item, lst)
else:
return link(first(lst), insert(rest(lst), item, index-1))
```

Use OK to test your code:

`python3 ok -q insert`

### Question 8: Interleave

Write `interleave(s0, s1)`

, which takes two linked lists
and produces a new linked list with elements of `s0`

and `s1`

interleaved. In
other words, the resulting list should have the first element of the `s0`

, the
first element of `s1`

, the second element of `s0`

, the second element of `s1`

,
and so on.

If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.

```
def interleave(s0, s1):
"""Interleave linked lists s0 and s1 to produce a new linked
list.
>>> evens = link(2, link(4, link(6, link(8, empty))))
>>> odds = link(1, link(3, empty))
>>> print_link(interleave(odds, evens))
1 2 3 4 6 8
>>> print_link(interleave(evens, odds))
2 1 4 3 6 8
>>> print_link(interleave(odds, odds))
1 1 3 3
"""
"*** YOUR CODE HERE ***"
# Recursive version
if s0 == empty:
return s1
elif s1 == empty:
return s0
return link(first(s0),
link(first(s1),
interleave(rest(s0), rest(s1))))
# Iterative version
def interleave(s0, s1):
interleaved = empty
while s0 != empty and s1 != empty:
interleaved = link(first(s1), link(first(s0), interleaved))
s0, s1 = rest(s0), rest(s1)
remaining = s1 if s0 == empty else s0
while remaining != empty:
interleaved = link(first(remaining), interleaved)
remaining = rest(remaining)
return reverse_iterative(interleaved)
def reverse_iterative(s):
rev_list = empty
while s != empty:
rev_list = link(first(s), rev_list)
s = rest(s)
return rev_list
```

Use OK to test your code:

`python3 ok -q interleave`

### Question 9: Filter

Implement a `filter_list`

function that takes a linked list `lst`

and
returns a new linked list only containing elements from `lst`

that satisfy
`predicate`

. Remember, recursion is your friend!

```
def filter_list(predicate, lst):
"""Returns a link only containing elements in lst that satisfy
predicate.
>>> lst = link(25, link(5, link(50, link(49, link(80, empty)))))
>>> new = filter_list(lambda x : x % 2 == 0, lst)
>>> print_link(new)
50 80
"""
"*** YOUR CODE HERE ***"
if lst == empty:
return lst
elif predicate(first(lst)):
return link(first(lst), filter_list(predicate, rest(lst)))
else:
return filter_list(predicate, rest(lst))
```

Use OK to test your code:

`python3 ok -q filter_list`

### Question 10: Reverse

Write iterative and recursive functions that reverse a given linked list,
producing a new linked list with the elements in reverse order. Use only the
`link`

constructor and `first`

and `rest`

selectors to manipulate linked lists.
(You may write and use helper functions.)

```
def reverse_iterative(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reversed_primes = reverse_iterative(primes)
>>> print_link(reversed_primes)
7 5 3 2
"""
"*** YOUR CODE HERE ***"
rev_list = empty
while s != empty:
rev_list = link(first(s), rev_list)
s = rest(s)
return rev_list
def reverse_recursive(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reversed_primes = reverse_recursive(primes)
>>> print_link(reversed_primes)
7 5 3 2
"""
"*** YOUR CODE HERE ***"
return reverse_helper(s, empty)
def reverse_helper(s, tail):
if s == empty:
return tail
return reverse_helper(rest(s), link(first(s), tail))
```

Use OK to test your code:

```
python3 ok -q reverse_iterative
python3 ok -q reverse_recursive
```

### Question 11: Kth to Last

Implement the `kth_last(lst, k)`

function, which returns the element
that is `k`

positions from the last element.

```
def kth_last(lst, k):
"""Return the kth to last element of `lst`.
>>> lst = link(1, link(2, link(3, link(4))))
>>> kth_last(lst, 0)
4
>>> print(kth_last(lst, 5))
None
"""
"*** YOUR CODE HERE ***"
# Iterative Version
ahead = lst
for _ in range(k):
if ahead == empty:
return None
ahead = rest(ahead)
start = lst
while rest(ahead) != empty:
ahead = rest(ahead)
start = rest(start)
if start == empty:
return None
return first(start)
# Recursive Version
def unwind_rewind(lst):
if lst == empty:
return (k, None, False)
previous_k, kth_element, found = unwind_rewind(rest(lst))
if found:
return (0, kth_element, True)
if previous_k == 0 and not found:
return (0, first(lst), True)
return (previous_k-1, kth_element, False)
return unwind_rewind(lst)[1]
# Alternate
def unwind_rewind(lst):
if lst == empty:
return
unwind_rewind(rest(lst))
nonlocal k
if k == 0:
return first(lst)
k -= 1
return unwind_rewind(lst)
```

Use OK to test your code:

`python3 ok -q kth_last`