WRITE AND EXPLAIN CODE (PYTHON 3.9)(CODE IS BOLDED)

Your linked_list.py file will become quite large once the method bodies are written. It will be helpful if you can efficiently navigate large files like this one. PyCharm's Structure tool window can help. It shows the structure of the file you currently have open, including any classes, methods, and functions defined...

INSTRUCTIONS (linked list.py):

Here is some advice: Draw lots of pictures. Pictures will help you understand what your linked list structures should look like before, during, and after operations that change (mutate) those structures. If you skip the drawing, you are much more likely to make mistakes! Be sure that you know exactly what attribute each part of your drawing represents. This will guide your code. Your linked_list.py file will become quite large once the method bodies are written. It will be helpful if you can efficiently navigate large files like this one. PyCharm's Structure tool window can help. It shows the structure of the file you currently have open, including any classes, methods, and functions defined. #Task 1: Practice with linked lists In the starter code, find and read the docstring of the method __len__, and then implement it. You already implemented this method in this week's prep, but it's good practice to implement it again. (And if you missed this week's prep, do it now!) Then, implement the methods count, index, and __setitem__. You might have noticed that all the doctests were commented out in the previous part. This is because they use a more powerful initializer than the one we've started with. Your final task in this section is to implement a new initializer with the following interface: 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 . """ The lecture notes suggest one way to do this using append; however, here we want you to try doing this without using append (or any other helper method). There are many different ways you could implement this method, but the key idea is that you need to loop through items, create a new _Node for each item, link the nodes together, and initialize self._first. Spend time drawing some pictures before writing any code! #Task 2: Timing __len__ for linked lists vs. array-based lists Most methods take longer to run on large inputs than on small inputs, although this is not always the case. Look at your code for your linked list method __len__. Do you expect it to take longer to run on a larger linked list than on a smaller one? Pick one the following terms to relate the growth of __len__'s running time vs. input size, and justify. constant, logarithmic, linear, quadratic, exponential Complete the code in time_lists.py to measure how running time for your __len__ method changes as the size of the linked list grows. Compare this to the behaviour of calling len on a built-in list (the starter code begins this for you). What do you notice? #Task 3: Augmenting our linked list implementation Now, it makes sense that our implementation of LinkedList.__len__ is so slow; how is the built-in list.__len__ so much faster? It turns out that built-in Python lists use an additional attribute to store their length, so that whenever list.__len__ is called, it simply returns the value of this attribute. The process of adding an extra attribute to an existing data structure is known as augmentation, and is very common in computer science. Every data structure augmentation poses a question of trade-offs: The benefit of augmenting is that the extra attribute makes certain operations simpler and/or more efficient to implement. The cost of augmenting is that this extra attribute increases the complexity of the data structure implementation. In particular, such attributes often have representation invariants associated with them that must be maintained every time the data structure is mutated. Create a copy of your LinkedList class (you can pick a name for the copy), and add a new private attribute _length to the class documentation and initializer. Write down a representation invariant for this new attribute; you can use English here, but try to be precise without using the word "length" in your description. (Hint: how do we define length in terms of the nodes of a list?) Update each mutating method to preserve your representation invariant for this new attribute. (Why don't we need to worry about the non-mutating methods?) Now let's enjoy the benefit of this augmentation! Modify your new class' __len__ method to simply return this new attribute. Use doctests wisely to ensure you've made the correct changes for this and the previous step. Finally, perform some additional timing tests to demonstrate that you really have improved the efficiency of __len__. #Additional exercises Generalizing __getitem__ The implementation we've provided for __getitem__ has many shortcomings compared to Python's built-in lists. The two features we would like to implement are negative indexes and slices (e.g., my_list[2:5]). Your first task here is to investigate the different ways in which Python supports these operations for built-in Python lists; you can do this by experimenting yourself in the Python console, or by doing some reading online. Then, modify the linked list implementation of __getitem__ so that it handles both negative indexes and slices. Note that a slice in Python is actually a class: the expression my_list[2:5] is equivalent to my_list.__getitem__(slice(2, 5)). Use isinstance to determine whether the input to __getitem__ is an integer or a slice. The fully general method signature of __getitem__ should become: def __getitem__(self, index: Union[int, slice]) -> Union[Any, LinkedList] Note: slicing should always return a new LinkedList object. This means that for a given slice, you'll need to create a LinkedList and new _Nodes as well, in a similar manner to how you implemented the more powerful initializer at the end of Task 1.

(time list.py) CODE:

 === Module description === This module runs timing experiments to determine how the time taken to call `len` on a Python list vs. a LinkedList grows as the list size grows. """ from timeit import timeit from linked_list import LinkedList NUM_TRIALS = 3000 # The number of trials to run. SIZES = [1000, 2000, 4000, 8000, 16000] # The list sizes to try. def profile_len(list_class: type, size: int) -> float: """Return the time taken to call len on a list of the given class and size. Precondition: list_class is either list or LinkedList. """ # TODO: Create an instance of list_class containing  0's. my_list = ... # TODO: call timeit appropriately to check the runtime of len on the list. # Look at the Lab 4 starter code if you don't remember how to use timeit: # https://mcs.utm.utoronto.ca/~148/labs/w4_ADTs/starter-code/timequeue.py return 0.0 if __name__ == '__main__': # Try both Python's list and our LinkedList for list_class in [list, LinkedList]: # Try each list size for s in SIZES: time = profile_len(list_class, s) print(f'[{list_class.__name__}] Size {s:>6}: {time}')

(Linked list.py) CODE:

=== Module Description === This module contains the code for a linked list implementation with two classes, LinkedList and _Node. All of the code from lecture is here, as well as some exercises to work on. """ 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. _first: Optional[_Node] def __init__(self) -> None: """Initialize a new empty linked list containing the given items. """ self._first = None # ------------------------------------------------------------------------ # Methods from lecture/readings # ------------------------------------------------------------------------ def is_empty(self) -> bool: """Return whether this linked list is empty. # >>> LinkedList([]).is_empty() # True # >>> LinkedList([1, 2, 3]).is_empty() # False """ return self._first is None 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 __getitem__(self, index: int) -> Any: """Return the item at position  in this list. Raise IndexError if  is >= the length of this list. """ curr = self._first curr_index = 0 while curr is not None and curr_index < index: curr = curr.next curr_index += 1 assert curr is None or curr_index == index if curr is None: raise IndexError else: return curr.item def insert(self, index: int, item: Any) -> None: """Insert the given item at the given index in this list. Raise IndexError if index > len(self) or index < 0. Note that adding to the end of the list is okay. # >>> lst = LinkedList([1, 2, 10, 200]) # >>> lst.insert(2, 300) # >>> str(lst) # '[1 -> 2 -> 300 -> 10 -> 200]' # >>> lst.insert(5, -1) # >>> str(lst) # '[1 -> 2 -> 300 -> 10 -> 200 -> -1]' # >>> lst.insert(100, 2) # Traceback (most recent call last): # IndexError """ # Create new node containing the item new_node = _Node(item) if index == 0: self._first, new_node.next = new_node, self._first else: # Iterate to (index-1)-th node. curr = self._first curr_index = 0 while curr is not None and curr_index < index - 1: curr = curr.next curr_index += 1 if curr is None: raise IndexError else: # Update links to insert new node curr.next, new_node.next = new_node, curr.next # ------------------------------------------------------------------------ # Lab Task 1 # ------------------------------------------------------------------------ # TODO: implement this method def __len__(self) -> int: """Return the number of elements in this list. # >>> lst = LinkedList([]) # >>> len(lst) # Equivalent to lst.__len__() # 0 # >>> lst = LinkedList([1, 2, 3]) # >>> len(lst) # 3 """ pass # TODO: implement this method def count(self, item: Any) -> int: """Return the number of times  occurs in this list. Use == to compare items. # >>> lst = LinkedList([1, 2, 1, 3, 2, 1]) # >>> lst.count(1) # 3 # >>> lst.count(2) # 2 # >>> lst.count(3) # 1 """ pass # TODO: implement this method def index(self, item: Any) -> int: """Return the index of the first occurrence of  in this list. Raise ValueError if the  is not present. Use == to compare items. # >>> lst = LinkedList([1, 2, 1, 3, 2, 1]) # >>> lst.index(1) # 0 # >>> lst.index(3) # 3 # >>> lst.index(148) # Traceback (most recent call last): # ValueError """ pass # TODO: implement this method def __setitem__(self, index: int, item: Any) -> None: """Store item at position  in this list. Raise IndexError if index >= len(self). # >>> lst = LinkedList([1, 2, 3]) # >>> lst[0] = 100 # Equivalent to lst.__setitem__(0, 100) # >>> lst[1] = 200 # >>> lst[2] = 300 # >>> str(lst) # '[100 -> 200 -> 300]' """ pass if __name__ == '__main__': # import python_ta # python_ta.check_all() import doctest doctest.testmod()