from __future__ import annotations from typing import Any, Optional

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 , with no next node. """ self.item = item self.next = None # Initially pointing to nothing

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. # curr : cursor pointing to nodes during the run

_first: Optional[_Node]

def __init__(self) -> None: """Initialize an empty linked list. """ self._first = None

def print_items(self) -> None: """Print out each item in this linked list.""" curr = self._first while curr is not None: print(curr.item) curr = curr.next

########################################################################## # Part 1 # # For each of the following linked list methods, read its docstring # and the complete its implementation. # You should use the provided *linked list traversal* code template # as your starting point, but of course you should modify it as necessary! # # NOTE: the first two methods are new special methods (you can tell by the # double underscores), and enable some special Python behaviour that we've # illustrated in the doctests. # # At the bottom of this file, we've included some helpers # to create some basic linked lists for our doctests. ##########################################################################

def __len__(self) -> int: """Return the number of elements in this list.

>>> lst = LinkedList() >>> len(lst) # Equivalent to lst.__len__() 0 >>> lst = three_items(1, 2, 3) >>> len(lst) 3 """ # TODO: implement this method # curr = self._first # while curr is not None: # ... curr.item ... # curr = curr.next

def __contains__(self, item: Any) -> bool: """Return whether is in this list.

Use == to compare items.

>>> lst = three_items(1, 2, 3) >>> 2 in lst # Equivalent to lst.__contains__(2) True >>> 4 in lst False """ # TODO: implement this method # curr = self._first # while curr is not None: # ... curr.item ... # curr = curr.next

# HINTS: for this one, you'll be adding a new item to a linked list. # 1. Create a new _Node object first. # 2. Consider the cases where the list is empty and non-empty separately. # 3. For the non-empty case, you'll first need to iterate to the # *last node* in the linked list. (Review this prep's Quercus quiz!) def append(self, item: Any) -> None: """Append to the end of this list.

>>> lst = LinkedList() >>> lst.append(1) >>> lst._first.item 1 >>> lst.append(2) >>> lst._first.next.item 2 """ # TODO: implement this method # curr = self._first # while curr is not None: # ... curr.item ... # curr = curr.next

# TODO: Make sure you address the task in prep5_starter_tests.py! # In that task, you will be writing test cases for __contains__

# ------------------------------------------------------------------------ # Helpers for creating linked lists (testing purposes only) # You may use these to help you construct a LinkedList # Do NOT change these helper functions. # ------------------------------------------------------------------------ def one_item(x: Any) -> LinkedList: """Return a linked list containing the given item.""" lst = LinkedList() node = _Node(x) lst._first = node return lst

def three_items(x1: Any, x2: Any, x3: Any) -> LinkedList: """Return a linked list containing the given three items.""" lst = LinkedList() node1 = _Node(x1) node2 = _Node(x2) node3 = _Node(x3) node1.next = node2 node2.next = node3 lst._first = node1 return lst

if __name__ == '__main__': import python_ta python_ta.check_all(config={ 'allowed-io': ['LinkedList.print_items'], 'disable': ['W0212', 'E1136'] })

import doctest doctest.testmod()

-----------------------------------------------------------------------------

"""CSC148 Prep 5: Linked Lists

=== CSC148 Winter 2023 === Department of Computer Science, University of Toronto

This code is provided solely for the personal and private use of students taking the CSC148 course at the University of Toronto. Copying for purposes other than this use is expressly prohibited. All forms of distribution of this code, whether as given or with any changes, are expressly prohibited.

Authors: David Liu, Diane Horton and Sophia Huynh

All of the files in this directory and all subdirectories are: Copyright (c) 2020 David Liu, Diane Horton and Sophia Huynh

=== Module Description === This module contains sample tests for Prep 5. You may use these to test your code.

Complete the TODO in this file.

When writing a test case, make sure you create a new function, with its name starting with "test_". For example:

def test_my_test_case(): # Your test here """ from prep5 import LinkedList, _Node # You may also import the one_item and three_items helper functions.

################################################################################ # Part 2 # In this part of the prep, you are to write test cases for the __contains__ # method. # # We will run your tests on a correct version of prep5.py, as well as a version # with an undisclosed bug in the __contains__ method. We will not give you # hints as to what the bug is, so test thoroughly! # # When you are done, run the automated self-test on MarkUs. If you pass the # test case named 'test_contains_test_cases': congratulations! You've found # the bug, and you're done with this part. # # You may write as many test cases as you want. However, your test cases must # fulfill the following requirements: # - All of your tests must pass on our correct version of prep5.py # - At least one of your tests must fail on the version with a bug. # # Make sure your tests all have different names that start with test_! # # You may assume __len__ and append work properly in both versions of prep5.py # that we run your test cases on. # # Hint: Try to think about the different LinkedLists you could have: # - Consider both the length of the LinkedList, and its content. # - Consider the item being searched for: its position, and whether # it's in the LinkedList at all. # There are many different combinations for you to try. ################################################################################ # TODO: Write test cases for __contains__

# Below are provided sample test cases for your use. You are encouraged # to add additional test cases. # WARNING: THIS IS AN EXTREMELY INCOMPLETE SET OF TESTS! # Add your own to practice writing tests and to be confident your code is # correct. def test_len_empty() -> None: """Test LinkedList.__len__ for an empty linked list.""" lst = LinkedList() assert len(lst) == 0

def test_len_three() -> None: """Test LinkedList.__len__ on a linked list of length 3.""" lst = LinkedList() node1 = _Node(10) node2 = _Node(20) node3 = _Node(30) node1.next = node2 node2.next = node3 lst._first = node1

assert len(lst) == 3

def test_contains_doctest() -> None: """Test LinkedList.__contains__ on the given doctest.""" lst = LinkedList() node1 = _Node(1) node2 = _Node(2) node3 = _Node(3) node1.next = node2 node2.next = node3 lst._first = node1

assert (2 in lst) is True assert (4 in lst) is False

def test_append_empty() -> None: """Test LinkedList.append on an empty list.""" lst = LinkedList() lst.append(1) assert lst._first.item == 1

def test_append_one() -> None: """Test LinkedList.append on a list of length 1.""" lst = LinkedList() lst._first = _Node(1) lst.append(2) assert lst._first.next.item == 2

if __name__ == '__main__': import pytest pytest.main(['prep5_starter_tests.py'])

I only need part 2, in which we have to create test cases for __contains__ function. It says we don't know what the bug is, but we have to create test cases, which fail the buggy code, but pass the original code.