Insertion in Doubly Linked List

A double-linked list is a variation of a single-linked list. A single linked list is a collection of nodes, recognizing that each node has a data piece and a pointer to the next node.

Like a single linked list, a double linked list has a beginning and an end. The pointer in front of the head is set to NULL because this is the first node. The next pointer to the queue node is set to NULL because this is the last node.

The following figure shows the basic layout of a double linked list.

insertion

In the above figure, you can see that each node has two pointers, one points to the previous node and the other points to the next. The previous node only of the first node (head) is set to null and the next pointer of the last node (tail) is set to null.

The double-linked list contains two pointers, one before and one after, so you can scroll back and forth. This is the main advantage of double linked lists over single linked lists.

Declaration:

A node of doubly linked list is represented are as follows:

struct node
{
     struct node *prev;
     int data;
     struct node *next;
};

Aside from the above declaration, nodes in a double-linked list can also be represented as C ++ classes. When using STL in C ++, double linked lists are represented as classes.

Insertion in doubly linked list:

The Insert Double Linked List operation inserts a new node into the linked list. Depending on where you want to insert the new node, you can perform the following insert operations.

Nodes can be added in three ways:
  1. Insert a node at the front.
  2. Insert node at the end.
  3. Insert node before-after given node.

1. Insert a node at the front:

insertion

Here’s how to insert a new node at the top of the list. As you can see, the new node N above is set to null. The head points to a new node. The pointer after N now points to N1, and the pointer before N1, which previously pointed to Null, now points to N.

For example:

insertion

Here Code:

void push(struct Node** head_ref, int new_data)
{
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          new_node->data = new_data;
          new_node->next = (*head_ref);
          new_node->prev = NULL;
          if ((*head_ref) != NULL)
                   (*head_ref)->prev = new_node;
          (*head_ref) = new_node;
}

2. Insert node at the end:

insertion

To insert a node at the end of a double-linked list, point the following pointer at the new node N to null. The pointer before N points to N5. The “Next” pointer on N5 points to N.

For example:

insertion

Here Code:

void append(struct Node** head_ref, int new_data)
{
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          struct Node* last = *head_ref;
          new_node->data = new_data;
          new_node->next = NULL;
          if (*head_ref == NULL) {
                   new_node->prev = NULL;
                   *head_ref = new_node;
                   return;
          }
          while (last->next != NULL)
                   last = last->next;
          last->next = new_node;
          new_node->prev = last;
          return;
}

3. Insert node before/after given node:

insertion

If you need to add nodes before or after a particular node, as shown above, change the pointers before and after the node before and after to properly point to the new node. Also, the new node pointer points to the existing node appropriately.

For example:

insertion
Insert node after given node

Here Code:

void insertAfter(struct Node* prev_node, int new_data)
{
          if (prev_node == NULL) {
                   printf("the given previous node cannot be NULL");
                   return;
          }
          struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
          new_node->data = new_data;
          new_node->next = prev_node->next;
          prev_node->next = new_node;
          new_node->prev = prev_node;
          if (new_node->next != NULL)
                   new_node->next->prev = new_node;
}

For example:

insertion
Insert node before given node

Here Code:

struct Node {
          int data;
          Node* next;
          Node(int val, Node* link = 0)
                   : data(val), next(link)
          {
          }
};
The following C ++ program demonstrates all of the above methods for inserting a node into a double-linked list.

For example:

insertion

insertion

insertion

insertion

The above program double-links by inserting a node using three insertion methods: insert node before, insert last node, and insert node after specified node. Create a list.

Here Code:

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   struct Node* prev;
};
void insert_front(struct Node** head, int new_data)
{
   struct Node* newNode = new Node;
   newNode->data = new_data;
   newNode->next = (*head);
   newNode->prev = NULL;
   if ((*head) != NULL)
   (*head)->prev = newNode;
   (*head) = newNode;
}
void insert_After(struct Node* prev_node, int new_data)
{
   if (prev_node == NULL) {
   cout<<"Previous node is required , it cannot be NULL";
   return;
}
   struct Node* newNode = new Node;
   newNode->data = new_data;
   newNode->next = prev_node->next;
   prev_node->next = newNode;
   newNode->prev = prev_node;
   if (newNode->next != NULL)
   newNode->next->prev = newNode;
}
void insert_end(struct Node** head, int new_data)
{
   struct Node* newNode = new Node;
   struct Node* last = *head;
   newNode->data = new_data;
   newNode->next = NULL;
   if (*head == NULL) {
   newNode->prev = NULL;
   *head = newNode;
    return;
}
while (last->next != NULL)
last = last->next;
last->next = newNode;
newNode->prev = last;
return;
}
void displayList(struct Node* node) {
   struct Node* last;
   while (node != NULL) {
      cout<<node->data<<"<==>";
      last = node;
      node = node->next;
   }
   if(node == NULL)
   cout<<"NULL";
   }
int main() {
   struct Node* head = NULL;
   insert_end(&head, 40);
   insert_front(&head, 20);
   insert_front(&head, 10);
   insert_end(&head, 50);
   insert_After(head->next, 30);
   cout<<"Doubly linked list is as follows: "<<endl;
   displayList(head);
   return 0;
}

Conclusion:

A double-linked list is a variation of a single-linked list. This differs from a single linked list in that each node contains an additional pointer to the previous node along with the next pointer.

The presence of these additional pointers facilitates insertion and deletion operations in the double-linked list, but at the same time requires additional memory to store these additional pointers.

As mentioned above, double-link lists have a variety of uses in real-time scenarios, such as browser caches and MRUs. Double-linked lists can also be used to represent other data structures, such as trees and hash tables.

Recommended Articles:

  1. Deletion in Doubly Linked List
  2. How to reverse a doubly linked list?
  3. QuickSort on Doubly Linked List
  4. Merge Sort for Doubly Linked List
  5. How to reverse a string using stack?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 103 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
6 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Insertion in Doubly Linked List […]

trackback

[…] Insertion in Doubly Linked List […]

trackback

[…] Insertion in Doubly Linked List […]

trackback

[…] Insertion in Doubly Linked List […]

trackback

[…] Insertion in Doubly Linked List […]

trackback

[…] Insertion in Doubly Linked List […]

You cannot copy content of this page
Scroll Up
6
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.