Introduction
A Doubly Linked List (DLL) contains an extra pointer, commonly referred to as the previous pointer, in addition to the next pointer and data found in a singly linked list.
Below is a representation of a DLL node:
// Node of a doubly linked list
class Node {
public:
int data;
// Pointer to next node in DLL
Node* next;
// Pointer to previous node in DLL
Node* prev;
}; |
Advantages of the doubly linked list (DLL) over the singly linked list (SLL):
- A DLL can be navigated in both forward and reverse directions.
- If a pointer to the node to be deleted is provided, the delete operation in DLL is more efficient.
- We can quickly add a new node before a specific node.
- To delete a node in a singly linked list, a pointer to the previous node is required. Sometimes the list is traversed to get to the preceding node. We can access the previous node in DLL by utilizing the previous pointer.
Disadvantages of the doubly linked list (DLL) over the singly linked list (SLL):
- Every DLL node requires more space for a prior pointer. However, DLL can be implemented with a single pointer.
- All operations necessitate the keeping of a prior pointer. In insertion, for example, we must adjust previous and next pointers simultaneously. In the following functions, for example, we require 1 or 2 more steps to set the previous pointer for insertions at different places.
Insertion in DLL
A node can be added in four ways:
- At the front of the DLL
- After a given node.
- At the end of the DLL
- Before a given node.
- Add a node at the front:
The head of the provided Linked List is always added before the new node. The newly added node serves as the DLL's new head.
E.g., if we add item 5 to the front of the given Linked List, which is 1->0->1->5, the Linked List will change to 5->1->0->1->5.
Let’s call the function that adds to the top of the list push (). Because the push() function must modify the head pointer to point to the new node, it must be passed a pointer to the head pointer.
The following is the implementation of the five stages for inserting a node at the beginning of a linked list:
/* Given a reference (pointer to pointer)
to the head of a list
and an int, inserts a new node on the
front of the list. */
void push(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head
and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
} |
Time Complexity: O(1)
Auxiliary Space: O(1)
Note: Four of the above five steps are the same as the four steps used to insert at the front of the singly linked list. The only additional step is to replace the prior head.
- Add a node after a given node:
The pointer to a node is given as prev_node, and the new node is inserted after the previous node.
The following is the implementation of the seven stages for inserting a node in the linked list after a given node:
/* Given a node as prev_node, insert
a new node after the given node */
void insertAfter(Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
/* 2. allocate new node */
Node* new_node = new Node();
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. Make the next of prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of new_node's next node */
if (new_node->next != NULL)
new_node->next->prev = new_node;
} |
Time Complexity: O(1)
Auxiliary Space: O(1)
Note: Five of the above stages are identical to the five steps needed to insert after a given node in the singly linked list. Two more steps are required to alter the new node's previous pointer and the new node's next node's previous pointer.
- Add a node at the end:
The new node is always added to the Linked List after the last node.
E.g., 5->1->0->1->5->2 is the given DLL and we add item 30 at the end, the new DLL is 5->1->0->1->5->2->30.
Since the head of a Linked List is usually how it is shown, we have to go through the list and change the next-to-last node to the new node.
The following is the implementation of the seven stages for inserting a node at the end of a linked list:
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void append(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
} |
Time Complexity: O(n)
Auxiliary Space: O(1)
Note: Six of the seven steps listed above are the same as the six steps necessary to insert after a given node in a singly linked list. To update the prior pointer of the new node, one more step is required.
- Add a node before a given node:
To resolve the issue, follow the actions outlined below.
Let the next node be the reference to this given node, and new_data be the data of the new node.
- Determine whether or not the next node is NULL. If it is NULL, the method should be exited because no additional nodes can be inserted before a NULL.
- Allocate memory for the new node and name it new_node.
- Set new_node-> data = new_data
- Set this new node's previous reference to the previous node of the next node, new node->prev = next node->prev
- Set the next_node's previous pointer as the new_node, next node->prev = new node
- Set this new_node's next pointer as the next_node, new node->next = next node;
- If the previous node of the new_node is not NULL, set the previous node's next pointer as new_node, new node->prev->next = new_node
- Otherwise, if the new node's prev is NULL, it will be the new head node. As a result, set (*head_ref) = new_node.
Below is the complete code for testing the above functions:
// A complete working C++ program to
// demonstrate all insertion methods
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node {
public:
int data;
Node* next;
Node* prev;
};
/* Given a reference (pointer to pointer)
to the head of a list
and an int, inserts a new node on the
front of the list. */
void push(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head
and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}
/* Given a node as prev_node, insert
a new node after the given node */
void insertAfter(Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
/* 2. allocate new node */
Node* new_node = new Node();
/* 3. put in the data */
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. Make the next of prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of new_node's next node */
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void append(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
Node* last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so
make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new
node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
/* 7. Make last node as previous of new node */
new_node->prev = last;
return;
}
// This function prints contents of
// linked list starting from the given node
void printList(Node* node)
{
Node* last;
cout << "\nTraversal in forward direction \n";
while (node != NULL) {
cout << " " << node->data << " ";
last = node;
node = node->next;
}
cout << "\nTraversal in reverse direction \n";
while (last != NULL) {
cout << " " << last->data << " ";
last = last->prev;
}
}
// Driver code
int main()
{
/* Start with the empty list */
Node* head = NULL;
// Insert 6. So linked list becomes 6->NULL
append(&head, 6);
// Insert 7 at the beginning. So
// linked list becomes 7->6->NULL
push(&head, 7);
// Insert 1 at the beginning. So
// linked list becomes 1->7->6->NULL
push(&head, 1);
// Insert 4 at the end. So linked
// list becomes 1->7->6->4->NULL
append(&head, 4);
// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);
cout << "Created DLL is: ";
printList(head);
return 0;
} |
Output
Created DLL is:
Traversal in forward direction
1 7 8 6 4
Traversal in reverse direction
4 6 8 7 1 |
Time Complexity: O(n)
Auxiliary Space: O(1)
An alternative method that makes use of a constructor call:
However, there is another approach that leverages constructor calls within the node class to reduce memory allocation work. It also reduces the number of lines of code required.
The above technique is implemented as follows:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
class node {
public:
node* prev;
int data;
node* next;
node(int value)
{ // A constructor is called here
prev = NULL; // By default previous pointer is
// pointed to NULL
data = value; // value is assigned to the data
next = NULL; // By default next pointer is pointed
// to NULL
}
};
void insert_at_head(node*& head, int value)
{
node* n = new node(value);
n->next = head;
if (head != NULL) {
head->prev = n;
}
head = n;
}
void insert_at_tail(node*& head, int value)
{
if (head == NULL) {
insert_at_head(head, value);
return;
}
node* n = new node(value);
node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
n->prev = temp;
}
void display(node* head)
{
node* temp = head;
while (temp != NULL) {
cout << temp->data << " --> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
// Driver code
int main()
{
node* head
= NULL; // declaring an empty doubly linked list
// Function call
insert_at_tail(head, 1);
insert_at_tail(head, 2);
insert_at_tail(head, 3);
insert_at_tail(head, 4);
insert_at_tail(head, 5);
cout << "After insertion at tail: ";
display(head);
cout << "After insertion at head: ";
insert_at_head(head, 0);
display(head);
return 0;
} |
Output
After insertion at tail: 1 --> 2 --> 3 --> 4 --> 5 --> NULL
After insertion at head: 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> NULL |
Time Complexity: O(n)
Auxiliary Space: O(1)