Insertion of node in Doubly linked list

Share

Insertion of node means adding a new node in the linked list or pushing a new node to a linked list . We can insert elements at 3 different positions of a doubly-linked list :

  1. Add at beginning
  2. Add at end
  3. Add at specified position

Suppose we have doubly linked list with following elements:

1.Add at beginning:

We have to add new node with value 6 at the beginning of doubly linked list we have above.

Algorithm

  1. START

2.Allocate memory for new node .

i e. new node=(struct DLL*)malloc (size of (struct DLL))

3.Assign number to data field,

new node->data=num;

4. Set :newnode ->prev=NULL

Set :newnode ->next=NULL

5. Check : if head==NULL then ,

Set: head= newnode,

Else,

Set: newnode->next=head

Set: head ->prev=newnode,

Set: head=newnode

6. Stop

Steps for inserting node at beginning of list:

Creation of new node
 Set prev and next pointers of new node
Make new node as head node

Code for Insertion at the Beginning

// insert node at the front
void insertFront(struct Node** head, int data) {

    // allocate memory for newNode
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // point next of newNode to the first node of the doubly linked list
    newNode->next = (*head);

    // point prev to NULL
    newNode->prev = NULL;

    // point previous of the first node (now first node is the second node) to newNode
    if ((*head) != NULL)
        (*head)->prev = newNode;

    // head points to newNode
    (*head) = newNode;
}

2.Add at end

Now ,we have to add a node with value 6 at the end of the doubly linked list we have above

Algorithm

  1. START

2.Allocate memory for new node .

i e. new node=(struct DLL*)malloc (size of (struct DLL))

3.Assign number to data field,

new node->data=num;

4. Set :newnode ->prev=NULL

Set :newnode ->next=NULL

5. Check : if head==NULL then ,

Set: head= newnode,

Else,

Set: temp=head,

While(temp->next =NULL){

temp=temp->next

}

temp->next=new node,

newnode->prev=temp,

6. Stop

Steps for inserting node at end of list:

Create a new node
 Set prev and next pointers of new node and the previous node

Code for Insertion at the End

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
    // allocate memory for node
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // assign NULL to next of newNode
    newNode->next = NULL;

    // store the head node temporarily (for later use)
    struct Node* temp = *head;

    // if the linked list is empty, make the newNode as head node
    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    // if the linked list is not empty, traverse to the end of the linked list
    while (temp->next != NULL)
        temp = temp->next;
   
    // now, the last node of the linked list is temp

    // point the next of the last node (temp) to newNode.
    temp->next = newNode;

    // assign prev of newNode to temp
    newNode->prev = temp;
}

3.Add at specified position

Now , we have to add a node with value 6 after node with value 1 in the doubly linked list.

Algorithm

  1. START

2.Allocate memory for new node .

i e. new node=(struct DLL*)malloc (size of (struct DLL))

3.Assign number to data field,

new node->data=num;

4. Set :newnode ->prev=NULL

Set :newnode ->next=NULL

5. Check : if head==NULL then ,

Set: head= newnode,

Else,

Set: i=1

temp=head,

Read the position (POS)

for(i=1;i<POS-1;i++){

temp=temp->next

}

newnode ->next=temp->next,

temp->next=newnode,

6. Stop

Steps for inserting node at specific position of list:

 Create a new node
Set the next pointer of new node and previous node
Set the prev pointer of new node and the next node
The final doubly linked list after this insertion

Code for Insertion in specific position

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {

    // check if previous node is NULL
    if (prev_node == NULL) {
        cout << "previous node cannot be NULL";
        return;
    }

    // allocate memory for newNode
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // set next of newNode to next of prev node
    newNode->next = prev_node->next;

    // set next of prev node to newNode
    prev_node->next = newNode;

    // set prev of newNode to the previous node
    newNode->prev = prev_node;

    // set prev of newNode's next to newNode
    if (newNode->next != NULL)
        newNode->next->prev = newNode;
}
Share
Raj Tuladhar

Raj Tuladhar

learning everything from everywhere!!

%d bloggers like this: