Doubly Linked Lists (DLL)
After singly-linked lists, we've come to the more evolved version of the linked list data structure: doubly-linked lists.
We'll cover the following
Introduction #
By now, you must have noticed a constraint that arises when dealing with singly-linked lists. For any function which does not operate at the head node, we must traverse the whole list in a loop.
While the search operation in a normal list works in the same way, access is much faster as lists allow indexing.
Furthermore, since a linked list can only be traversed in one direction, we needlessly have to keep track of previous elements.
This is where the doubly linked list comes to the rescue!
Structure of the Doubly Linked List (DLL) #
The only difference between doubly and singly-linked lists is that in DLLs, each node contains pointers for both the previous and the next node. This makes the DLLs bi-directional.
To implement this in code, we simply need to add a new member to the already constructed Node class:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.