Lab 8: Linked Lists

Due by 11:59pm on Thursday, July 23.

Starter Files

Download lab08.zip.

Attendance

You need to submit the lab problems in addition to attending to get credit for lab.

If you miss lab for a good reason (such as sickness or a scheduling conflict) or you don't get checked in for some reason, email cs61a@berkeley.edu within one week to receive attendance credit.

Linked Lists

Consult the drop-down if you need a refresher on Linked Lists. It's okay to skip directly to the questions and refer back here should you get stuck.

A linked list is a data structure for storing a sequence of values. It is more efficient than a regular built-in list for certain operations, such as inserting a value in the middle of a long list. Linked lists are not built in, and so we define a class called Link to represent them. A linked list is either a Link instance or Link.empty (which represents an empty linked list).

A instance of Link has two instance attributes, first and rest.

The rest attribute of a Link instance should always be a linked list: either another Link instance or Link.empty. It SHOULD NEVER be None.

To check if a linked list is empty, compare it to Link.empty. Since there is only ever one empty list, we can use is to compare, but == would work too.

def is_empty(s):
    """Return whether linked list s is empty."""
    return s is 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.

Here is the implementation of the Link class:

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) + ')'

Tip: You can open the terminal in VS Code by pressing Control + ` (the key above Tab).

Required Questions

Visualizing Linked Lists

If you would like some support with visualizing linked lists, please navigate to code.cs61a.org, select Start Python Interpreter, and call autodraw().

Q1: WWPD: Linked Lists

Read over the Link class. Make sure you understand the doctests.

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

python3 ok -q link -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab07.py.

>>> link = Link(1000)
>>> link.first

______
1000

>>> link.rest is Link.empty

______
True

>>> link = Link(1000, 2000)

______
AssertionError

>>> link = Link(1000, Link())

______
TypeError
>>> link = Link(1, Link(2, Link(3)))
>>> link.first

______
1

>>> link.rest.first

______
2

>>> link.rest.rest.rest is Link.empty

______
True

>>> link.first = 9001
>>> link.first

______
9001

>>> link.rest = link.rest.rest
>>> link.rest.first

______
3

>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty

______
False

>>> link.rest.rest.rest.rest.first

______
1

>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first

______
1

>>> link2.rest.first

______
2
>>> link = Link(5, Link(6, Link(7)))
>>> link                 # Look at the __repr__ method of Link

______
Link(5, Link(6, Link(7)))

>>> print(link)          # Look at the __str__ method of Link

______
(5 6 7)

Q2: Without One

Implement without, which takes a linked list s and a non-negative integer 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.

Hint: Using recursive approach might be easier than the iterative approach.

def without(s: Link, i: int) -> Link:
    """Return a new linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 0)
    Link(5, Link(7, Link(9)))
    >>> without(s, 2)
    Link(3, Link(5, Link(9)))
    >>> without(s, 4)  # There is no index 4, so all of s is retained.
    Link(3, Link(5, Link(7, Link(9))))
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q without

Write a function duplicate_link that takes in a linked list s and a value val. It mutates s so that each element equal to val is followed by an additional val (a duplicate copy). It returns None. Be careful not to get into an infinite loop where you keep duplicating the new copies!

Note: In order to insert a link into a linked list, reassign the rest attribute of the Link instances that have val as their first. Try drawing out a doctest to visualize!

def duplicate_link(s: Link, val: int) -> None:
    """Mutates s so that each element equal to val is followed by another val.

    >>> x = Link(5, Link(4, Link(5)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(5, Link(5)))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, Link(2, Link(3))))
    >>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q duplicate_link

Q4: Slice

Implement a function slice_link that slices a given linked list link. slice_link should slice the link starting at start and ending one element before end, as with a normal Python list. Additionally, similar to slicing normal Python lists, this function should return a new list and not modify the original list.

def slice_link(link: Link, start: int, end: int) -> Link:
    """Slices a linked list from start to end (as with a normal Python list) and returns
    a linked list. You do NOT have to support negative indices.

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> print(new)
    (1 4 1)
    >>> print(slice_link(link, 0, 2))
    (3 1)
    >>> print(slice_link(link, 0, 6))
    (3 1 4 1 5 9)
    >>> print(slice_link(link, 2, 2))
    ()
    >>> print(slice_link(link, 2, 3))
    (4)
    >>> print(slice_link(link, 3, 100))
    (1 5 9)
    >>> print(slice_link(link, 10, 12))
    ()
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q slice_link

Q5: Cycles

The Link class can represent lists with cycles. That is, a list may contain itself as a sublist.

>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3

Implement has_cycle,that returns whether its argument, a Link instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which Link objects you've already seen.

def has_cycle(link: Link) -> bool:
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    >>> u = Link(2, Link(2, Link(2)))
    >>> has_cycle(u)
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q has_cycle

Extra challenge (Optional): Implement has_cycle without keeping track of all Link objects you've already seen. The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around.

def has_cycle_constant(link: Link) -> bool:
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q has_cycle_constant

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

Correctly completing all questions is worth one point. Please ensure your TA has taken your attendance before leaving.