Doubly Linked List
This section explores operations on a doubly linked list
We'll cover the following...
We ended the section on linked list with a question on the complexity of an operation that seeks to find the parent of a given linked list node. The answer is O(n) since if you give me a linked list node, I still need to start from the head and traverse down the linked list matching each node with the one given to me until I find an exact match. At that point, I return the just previously seen node that I can keep track of using an additional variable. Worst case, it takes me to the end of the linked list for a total of n operations.
Doubly Linked List
Meet doubly linked list. It solves the above described problem by keeping a link to the previous node. Sure, we now have double the number of nodes, but the space complexity doesn't change.
...