Doubly Linked List
Explore how doubly linked lists address the limitations of singly linked lists by allowing constant time access to a node's predecessor. Understand the impact on space and time complexity, and see how these structures support advanced uses like LRU caches.
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.
...