Singly linked lists are immensely useful data structures with a host of applications such as:
Implementations of stacks and queues
Chaining in hash tables
Adjacency lists for graph representations
However, various applications need a doubly linked list instead of a singly linked list. One such example is implementing forward and backward navigation in web browsers.
Note: For more information on doubly linked lists , refer to this Answer. And to view their common operations, refer to this Answer.
Luckily, it's incredibly straightforward to transform a singly linked list into a doubly linked list.
Convert a singly linked list to a doubly linked list.
To solve our problem, we use the basic implementation of the singly linked list as illustrated in the following code snippet. We assume that the common operations for it have already been defined.
struct listNode {int data;listNode* next;};
Since the listNode
structure above is for a singly linked list, we need to modify it to contain a pointer to the previous node, as a doubly linked list contains both next and previous pointers. Hence, listNode
is to be modified as follows, with prev
storing the previous pointer:
struct listNode {int data;listNode* next;listNode* prev;};
Next, we traverse the entire list and assign the previous pointer at every node. This way, we have converted our singly linked list to a doubly linked list.
void doublyMaker (listNode* head) {if (head == NULL) {cout << "Error: List is empty!" << endl;}else {listNode* current = head;listNode* previous = NULL;while (current != NULL) {current -> prev = previous;previous = current;current = current -> next;}}}
listNode
structureLine 2: The data
member variable stores the value of the node.
Line 3: The listNode* next
variable stores the next pointer for a node.
Line 4: The listNode* prev
variable stores the previous pointer for a node.
linkedList
structureLine 2: The listNode* head
stores the head of the linked list.
doublyMaker
functionLine 1: The parameter of the function takes in listNode* head
which is just the head of our singly linked list.
Lines 2–4: The if
condition makes sure we don't attempt to doubly link an empty list (which will occur when head
is NULL
).
Line 6: A temporary variable, current
, is created to traverse the linked list.
Line 7: A temporary variable, previous
, is created to store the value of the node preceding (to the left) of the current
node.
Lines 9–13: The list is traversed until its end is reached, which occurs when current
is equal to NULL
.
Line 10: The previous pointer of the current
node is being set to the node stored in previous
.
Line 11: The node stored in previous
is changed to current
so that this can be assigned when we move on to the next node.
Free Resources