The singly linked list (SLL) is a linear data structure comprising of nodes chained together in a single direction. Each node contains a data member holding useful information, and a pointer to the next node.
The problem with this structure is that it only allows us to traverse forward, i.e., we cannot iterate back to a previous node if required.
This is where the doubly linked list (DLL) shines. DLLs are an extension of basic linked lists with only one difference:
A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.
From the definition above, we can see that a DLL node has three fundamental members:
A DLL costs more in terms of memory due to the inclusion of a
p (previous) pointer. However, the reward for this is that iteration becomes much more efficient.
The worst case complexity for search, insertion, and deletion is O(n). Insertion and deletion at the head can be done in O(1).
View all Courses