Lab 7: Linked Lists
- Due: Friday 10/16 @ 11:59pm
- Points: 1
- Download: lab07.zip
Attendance
You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.
If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.
Required Questions
Python 3.12 or newer is required for the remainder of the course. Please upgrade if you're using Python 3.11 (or older). See the Install Python section of Lab 0 for instructions.
Review
This drop-down provides an overview of working with linked lists.
Linked Lists
A linked list is a sequence type that is more efficient than a built-in list for
certain operations, such as inserting a value at the front of a long list.
Two linked lists that differ only in their first item can share the same rest.
type LinkedList[T] = Link[T] | tuple[()]
@dataclass
class Link[T]:
first: T
rest: LinkedList[T] = () # rest defaults to an empty linked list
A Link is a non-empty LinkedList, and so has a first and rest. The
rest of a Link should always be a linked list: either another Link or
().
You can make a LinkedList 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 lists.
Printing a Link shows its elements within parentheses: print(Link(3, Link(4))) displays (3 4).
The second element of s is s.rest.first and the third is
s.rest.rest.first.
This linked list visualizer is a great way to understand the structure of a complex linked list.
To check whether a linked list s is empty, use isinstance(s, Link). The VS
Code type checker infers that s is a Link and therefore has first and
rest attributes only when isinstance(s, Link) is true:
def sum_link(s: LinkedList[int]) -> int:
"""Return the sum of the items in linked list s."""
if not isinstance(s, Link):
return 0
return s.first + sum_link(s.rest)
The type LinkedList[int] describes a linked list whose elements are all
integers. A type variable, such as T in def extend[T](s: LinkedList[T], t: LinkedList[T]) -> LinkedList[T], represents any type and expresses that the
inputs and output to this function all contain the same type of items.
Linked Lists
Q1: WWPD: Linked Lists
Read over the Link class in link.py. Make sure you understand the
doctests.
Predict what Python will display when the following lines are entered into an
interactive session in which the Link class has already been defined, then
unlock the test to check your answers. Type ERROR if it errors:
python3 -m pytest -k link_wwpd --unlockUnlocking Examples
>>> from lab07 import Link
>>> a = Link(1000)
>>> a.first
______
>>> a.rest # the empty linked list is ()
______
>>> print(a) # printing a linked list shows all its items in parentheses
______
>>> b = Link(1, Link(2, Link(3)))
>>> print(b)
______
>>> b.first
______
>>> b.rest.rest.first
______
>>> b.rest.rest.rest
______
>>> skip = Link(9001, b.rest.rest)
>>> skip.first
______
>>> skip.rest.first
______
>>> skip.rest.rest
______
>>> b.rest.first
______
>>> print(Link(4, b))
______
>>> c = Link(Link(1), Link(2))
>>> c.first.first
______
>>> c.first.rest
______
>>> c.rest.first
______
>>> print(c)
______
>>> d = Link(5, Link(6, Link(7)))
>>> print(d)
______
>>> print(d.rest.rest)
______
>>> print(Link(8, Link(9, d.rest)))
______
>>> print(Link(10, Link(d.rest.rest, d.rest)))
______
>>> print(Link(5, 6))
______
If you get stuck, try drawing a linked list on a piece of paper or running
python3 -i link.pyand then evaluating different expressions.
Q2: Change
Write a function that takes in a linked list s and two values, old and
new. The function returns a copy of s but with all instances of old
replaced with new.
Hint: Use recursion. It's easier in this case!
def change[T](s: LinkedList[T], old: T, new: T) -> LinkedList[T]:
"""Returns a linked list matching s but with all instances of old (if any)
replaced by new.
>>> s = Link(1, Link(2, Link(3)))
>>> t = change(s, 3, 1)
>>> print(t)
(1 2 1)
>>> u = change(t, 1, 2)
>>> print(u)
(2 2 2)
>>> v = change(u, 5, 1)
>>> print(v)
(2 2 2)
>>> print(s) # The original linked list s is unchanged.
(1 2 3)
"""
"*** YOUR CODE HERE ***" # replace the code below
return ()
python3 -m pytest -k changeQ3: Without One
Implement without, which takes a linked list s and a non-negative integer
index i. It returns a linked list with all of the elements of s except for the
one at index i. (Assume s.first is the element at index 0.)
The original linked list s should not be changed.
If i is greater than or equal to the length of s, then without should return a linked list with the same contents as s.
Hint: Use recursion. It's easier in this case!
def without(s: LinkedList, i: int) -> LinkedList:
"""Return a linked list like s but without the element at index i.
>>> s = Link(3, Link(5, Link(7, Link(9))))
>>> print(without(s, 0))
(5 7 9)
>>> print(without(s, 2))
(3 5 9)
>>> print(without(s, 4)) # There is no index 4, so all of s is retained.
(3 5 7 9)
>>> print(s) # The original linked list s is unchanged.
(3 5 7 9)
>>> without((), 0)
()
"""
"*** YOUR CODE HERE ***" # replace the code below
return ()
python3 -m pytest -k withoutQ4: Store Digits
Write a function store_digits that takes in an integer n and returns a linked
list containing the digits of n in the same order (from left to right).
Important: Do not use any string manipulation functions, such as
strorreversed.
def store_digits(n: int) -> LinkedList[int]:
"""Stores the digits of a positive number n in a linked list.
>>> s = store_digits(1)
>>> s
Link(first=1, rest=())
>>> print(store_digits(2345))
(2 3 4 5)
>>> print(store_digits(876))
(8 7 6)
>>> print(store_digits(2450))
(2 4 5 0)
>>> print(store_digits(20105))
(2 0 1 0 5)
>>> # a check that you do not use str or reversed
>>> import inspect, ast
>>> [n.id for n in ast.walk(ast.parse(inspect.getsource(store_digits)))
... if isinstance(n, ast.Name) and n.id in ('str', 'reversed')]
[]
"""
"*** YOUR CODE HERE ***" # replace the code below
return ()
python3 -m pytest -k store_digitsSubmit Assignment
Submit this assignment by running Provenance: Prepare Submission Bundle from the VS Code command palette and uploading the resulting zip to Gradescope. The zip already contains the files you've edited. Lab 00 has detailed instructions.
Your responses to WWPD questions are not submitted, and they do not need to be. Lab credit is based on the code writing questions.