ATTACHED SOLUTION to Lab 5 - Linked Lists

Learning outcomes
By the end of this lab, you will be able to:

Implement non-mutating linked list methods using iteration.
Override Python magic methods to enable the use of some built-in Python syntax for a custom class.
Task 0 - Setup
Download and put it into your labs/lab5 folder:

linked_list.py (Task 1)
timer.py (Task 2)
time_lists.py (Task 2)
Here is some helpful 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 navigating 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. If you click on an item, it will take you to the location of that item in the file. You can get to it by navigating to View - Tool Windows - Structure.
Task 1 - Non-mutating linked list methods
Note: All of the methods you are about to write are non-mutating. This means that the state of self (that includes every attribute in it) when the method ends should be the same as when it began.

In the starter code, find and read the docstring of the method __len__, then write the method body. Note that as we did in class with method __str__, you'll be overriding a Python built-in method. This will allow you to call the function len on a linked list just as you do with a regular Python list. Run the doctests to make sure the method works.
Next, find and read the docstring of the method __contains__ and write the method body. Now you can use the syntax a in L to check if a linked list L contains a. Awesome! Run the doctests to make sure the method works.
Now find and read the docstring of the method count and implement it. Run the doctests to make sure the method works.
Finally, find and read the docstring of the method index and implement it. Run the doctests to make sure the method works.
Task 2 - Timing __len__ for LinkedList vs. a regular Python list
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 method __len__. Do you expect it to take longer to run on larger linked list than on a smaller one?
If you were to draw a graph where the x-axis is the size of the linked list and the y-axis is the time taken to run your __len__ method on the linked list, do you think the graph would show time increases "linearly" (in a straight line), more than linearly, or less than linearly?
Complete the code in time_lists.py to measure how running time for your __len__ method grows as the size of the linked list grows. This code does the same for ordinary Python lists, so you can compare them to your linked lists.
Can you think of a way to make your __len__ method run faster? Hint: it's very simple!
Additional exercise: Modifying your linked list implementation
If you have time, revise your LinkedList class in the way you just invented at the end of in Task 2:

Write Representation Invariant(s) that record any relevant new facts that now must remain true in order to have a valid instance of your LinkedList class.
Determine which methods must be revised to incorporate your new implementation of LinkedList.
Now revise the code for those methods. Re-run your doctests to make sure they still work!
Finally, rerun your timing tests to demonstrate that you really have improved how running time grows for your __len__ method.