Week 3: Linked List Complexity

Background

We worked on Wednesday on making operations adding and removing things from the end of a linked list O(1) time. Every group realized that this means we have to add a tail node. But that also means that to remove things quickly, every node needs to have both a next pointer and a previous pointer, so that we can quickly find what the new tail should be. Today, students will finish up by implementing such a doubly-linked list data structure so that all operations are O(1). Skeleton code has been provided for add_first, add_last, remove_first, and remove_last. Students should also write a method concatenate that takes another doubly-linked list as a parameter, and which adds that list to the back of the current list in O(1) time.

Click here to download the starter code. A few things to keep in mind as you're going:

• Be careful to update both next and prev nodes in all of your operations
• There are special cases in adding and removing when there is only one node in the list
• To check if two objects are equal, you can say
• To check if an object is not None, you can type Or, conversely, to check if an object is None, you can say

Time permitting, students should try to write empirical tests that show that the operations are O(1), regardless of how many elements are in the list.