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
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
prevnodes 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