So we’ve come to, in my opinion, a much simpler data structure in terms of visualization. What separates a doubly linked list from a singly is the fact that it has another node (in our homework’s case: last) that will keep track of the final element in our list. The nodes themselves also have pointers that reference the following item (next) and the item preceding it (prev). Take a look at a snippet from our homework:
We have a class (MyDeque) with 2 nodes that will eventually track the beginning and end of our list. They’re currently set to null because, well… We don’t have anything to reference yet. Like the last homework, we have N to keep track of the length of the list.
Also notable, in our Node class we have two pointers, next and prev that will serve as references to the item immediately after and before the item currently in the list. Now take a look at this:
A little tip while doing this week’s homework:
[box]Professor Riely provides tests for you. Look at what these tests are doing/how they’re called.
Notice that initially there is an empty list, therefore…
Wouldn’t it make sense that this homework may revolve around N?
After you nail the above idea down the rest is a piece of cake. [/box]