Week 3: Linked Lists

Background

We saw how to create a basic linked list data structure in python at the end of the last module, and the code is copied below for your convenience. One of the issues with this implementation is that the add_last method takes O(N) time. Modify the linked list so that the operations satisfy the following complexity bounds. Some of the methods you can leave as is, but others you can leave as is. You also may need to add some private variables to store more information to help you reach these bounds.

Once you believe you've matched all of these time bounds, write a test to time your implementation for varying sizes of the linked list using the testing framework from module 4, and make a plot showing empirically that the bounds are satisfied.

add	O(1)
remove_first	O(1)
add_last	O(1)
remove_last (New method!)	O(1)
__str__	O(N)
__len__	O(1)