Starting from:

$29.99

Quiz 5 LinkedList and _Node

Quiz 5
Below is a bare-bones implementation of LinkedList and _Node with the method
insert_after.

Read the docstring for insert_after. Make sure you understand what it's supposed
to do.

Your tasks are listed below.
    1.  In the docstring of insert_after, fill in the expected result.
        This should be a string assigned to the provided variable 'expected'.

    2.  In the docstring of insert_after, fill in the actual result.
        This should be the result of the (currently buggy) implementation of
        insert_after.
        Once again, this should be a string assigned to the provided variable
        'actual'.

    3.  Fix the bug in insert_after.
        You should NOT use any other LinkedList methods -- use only what we've
        provided in quiz5.py

After you finish Task (1) and (3), you should be able to run and pass
the doctests.

Submit your code on MarkUs and run the automated self-test.
Your grade on the quiz will be based solely on the results of the self-test.
(i.e. if you pass all of the tests, you get full marks on the quiz.)
"""
from __future__ import annotations
from typing import Any, Optional


################################################################################
# Below is the implementation of LinkedList.
# Do NOT add any methods to either class, and do NOT modify the __init__
# methods.
#
# You should ONLY modify insert_after.
################################################################################
class LinkedList:
    """A linked list implementation of the List ADT.
    """
    # === Private Attributes ===
    # _first:
    #     The first node in the linked list, or None if the list is empty.
    # _size:
    #     The number of items in this linked list.
    _first: Optional[_Node]
    _size: int

    def __init__(self, items: list) -> None:
        """Initialize a new linked list containing the given items.

        The first node in the linked list contains the first item
        in <items>.
        """
        if items == []:
            self._first = None
        else:
            self._first = _Node(items[0])
            curr = self._first
            for item in items[1:]:
                curr.next = _Node(item)
                curr = curr.next

    def __str__(self) -> str:
        """Return a string representation of this list in the form
        '[item1 -> item2 -> ... -> item-n]'.

        >>> str(LinkedList([1, 2, 3]))
        '[1 -> 2 -> 3]'
        >>> str(LinkedList([]))
        '[]'
        """
        items = []
        curr = self._first
        while curr is not None:
            items.append(str(curr.item))
            curr = curr.next
        return '[' + ' -> '.join(items) + ']'

    def insert_after(self, marker: Any, item: Any) -> None:
        """Insert <item> after the first time <marker> occurs in this
        linked list.

        Precondition: <marker> is in this linked list.

        >>> lst = LinkedList([1, 3, 2, 6])
        >>> lst.insert_after(3, 4)
        >>> expected = '[1 -> 3 -> 4 -> 2 -> 6]'
        >>> actual = '[1 -> 3 -> 4]'
        >>>
        >>> # If you've done Task 1 and Task 3 correctly, the below should work:
        >>> str(lst) == expected
        True
        """
        curr = self._first
        while curr.item != marker:
            curr = curr.next

        insert = _Node(item)
        next_node = curr.next
        curr.next = insert
        insert.next = next_node


################################################################################
# Below is the implementation of _Node
# Do NOT modify the below in any way. You have no tasks related to _Node.
################################################################################
class _Node:
    """A node in a linked list.

    Note that this is considered a "private class", one which is only meant
    to be used in this module by the LinkedList class, but not by client code.

    === Attributes ===
    item:
        The data stored in this node.
    next:
        The next node in the list, or None if there are no more nodes.
    """
    item: Any
    next: Optional[_Node]

    def __init__(self, item: Any) -> None:
        """Initialize a new node storing <item>, with no next node.
        """
        self.item = item
        self.next = None  # Initially pointing to nothing


if __name__ == '__main__':
    import doctest
    doctest.testmod()

More products