In this lab we will add a 'previous' link to a Linked List data structure making it a 'doubly linked list'..
Here is the code from Lecture 24 supporting linked lists and priority queues:
Starting with this implementation, add code that maintains 'prev' links to pointing to the previous node in the list. This means, the 'tail' will point at the last node in the list (who's 'next' pointer is null of course). That node will have a 'prev' pointer pointing at the node before it. This chain continues util you reach the 'head' node which has a null 'prev' pointer.
Conceptually, this is how your LinkedList will look:
I've added two methods, dumpLL() and dumpLLReversed(). The second one is commented out as it will not compile until you make some basic changes. These are to test your implementation of the Linked List at the end.
You will, of course, have to start by adding a 'prev' member to the Node class. After that, you can modify all the add and remove methods to adjust 'prev' pointers similar to how the 'next' pointers are updated. You will have to think carefully about order of operations to make sure you do not lose an important 'link'.
When you are finished, uncomment dumpLLReversed() and in TestLL, make a call to dumpLL() and to dumpLLReversed(). The list printed by dumpLLReversed() should be the exact elements in reverse of that printed by dumpLL().
When you are done with these, feel free to leave the lab.