What is a Doubly Linked List (DLL)?
This lesson briefly discusses the Doubly Linked List and how it is different from a Singly Linked List. We will also look at its implementation in Java.
We'll cover the following
Introduction
Often, we need to traverse through the whole list – the most time-consuming operation in linked lists—to perform the basic operations. Although we have to traverse an array as well, an array element can be accessed in O(1) by the index because array elements are present on contiguous memory locations. In linked lists, however, the nodes are not present on contiguous memory locations. Therefore, you will need to traverse all the nodes to get to the desired node.
Another concern that must be taken into account here is that linked lists are unidirectional: they can only move forward, not backward. Also, while adding or removing elements from the list, we need to keep track of the previous node as well, which makes it complicated. That is where the Doubly Linked List (DLL) comes to the rescue!
Doubly Linked List (DLL)
The difference between a Doubly and a Singly Linked List is that a DLL is bi-directional; this means any particular node stores both the previous and next pointers that point to the previous and next nodes, respectively.
To implement the node class for DLL, we only need to add a new data member, a node called prevNode, in the already constructed Node class of the SLL given below:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.