Exercise 14: Double Linked Lists

The previous exercise may have taken you quite a while to complete since you have to figure out how to make a single linked list work. Hopefully, the video gave you enough information to complete the exercise and also showed you exactly how to do an audit of your code. In this exercise you're going to implement the better version of linked lists called DoubleLinkedList.

In the SingleLinkedList you should have realized that any operation involving the end of the list has to travel through each node until it gets to the end. A SingleLinkedList is only efficient from the front of the list where you can easily change the next pointer. The shift and unshift operations are fast, but pop and push cost you as the list gets bigger. You might be able to speed this up by keeping a reference to the next-to-last element, but then what if you want to replace that element? Again, you'll have to go through all of the elements to find this one. You can get some speed improvements with a few minor changes like this, but a better solution is to simply change the structure to make it easier to work from any position.

The DoubleLinkedList is nearly the same as the SingleLinkedList except it also has a prev (for previous) link to the DoubleLinkedListNode that comes before it. One extra pointer per node and suddenly many of the operations become much easier. You can also easily add a pointer to the end in the DoubleLinkedList so you have direct access to both the beginning and the end. This makes push and pop efficient again since you can access the end directly and use the node.prev pointer to get the previous node.

With these changes in mind our node class looks like this:

View Source file ex14/dllist.py Only