doubly linked list(insertion)

 Doubly Linked List:

 A doubly linked list is a type of data structure(self-referential structures). Each node in the doubly linked list consists of three parts, namely the data and the reference to the next node, and the reference to the previous node.

insertion in a doubly linked list:

In doubly linked list insertion takes place in different ways that are ;

• insertion at start/first node
• insertion at the end/last node
• insertion at nth node

insertion at start of doubly linked list:

In a doubly-linked list, each node contains double pointers therefore we need to maintain more pointers as compare to a singly linked list. Insertion of any element into a doubly-linked list consists of two scenarios. 

• list is empty 
• list contains at least one element. 

c++ code:

void insertatStart(int value)

{

Node*newNode = new Node();

newNode->data = value;

newNode->next = head;

newNode->prev = NULL;

if (head!= NULL)

        head->prev = newNode;

        head = newNode;

}

insertion at end of doubly linked list:

In case of insertion at the end of the last node of the doubly linked list, we need to check whether the list is empty or it contains any element.

c++ code:

void insertatEnd(int value)

{

Node*newNode = new Node();

newNode->data = value;

newNode->next = NULL;

if (head == NULL)//check if list is empty

{

        newNode->prev = NULL;

        head = newNode;

         }

         else

         {

             Node* temp = head;

              while (temp->next != NULL)

               {

                temp = temp->next;

                }

               temp->next = newNode;

               newNode->prev = temp;

         }

}

insertion at nth position in doubly linked list:

void insertAtNth(int value,int position)

    {

      Node* newNode = new Node(); 

      newNode->data = value;

      newNode->next = NULL;

      newNode->prev = NULL;

    int i;

    Node*temp=head;

    if(position==1)//if list contain only one node

        {

        newNode->next=temp;

    head=newNode;

    return;

    }

    for(int i = 1; i < position-1; i++) 

    {

          if(temp != NULL)

          {

            temp = temp->next;

          }

        }

        if(temp != NULL) 

        {

          newNode->next = temp->next;

          newNode->prev = temp;

          temp->next = newNode;

          if(newNode->next != NULL)

            newNode->next->prev = newNode;  

        } 

        else 

        {

          cout<<"\nThe previous node is null.";

        } 

}