If we want to remove items from the end of a linked list a single step, 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 take a single step, regardless of how many elements are in the list. 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