Insertion in Doubly Linked List in C++

Insertion in Doubly Linked List

What is insertion in doubly linked in CPP programming?

Insertion in doubly linked in C++ in general words can be understood as insertion of a new node in a doubly linked list that is already created. We can perform three different types of insertion operations on singly linked list, these different types of insertion operations are:-

  • Insertion at beginning of the doubly linked list.
  • Inserting a new node at the specific position in doubly linked list.
  • Insertion at end in doubly linked list.

In this article, we will discuss what is the difference between these types of insertion and how we can execute them over a doubly linked list.

Types of Insertion in Doubly Linked list?

Insertion at beginning

In this type of insertion in doubly linked list a new node is added before the head of the list i.e. before the first node of the list.

Insertion at specific position

Here we insert a new node at specific position by traversing till the desired position and inserting new node there.

Insertion at end

We insert new node after the last node i.e. after the tail node in the insertion at end doubly linked list.

Types of insertion in doubly linked list

Insertion at beginning

Insertion at beginning

How to perform insertion at beginning in doubly linked list?

To perform insertion at beginning in doubly linked list we will use the following steps:-

  1. We will allocate space for the new node at the beginning of the list
  2. After that we will built a new node on the space created.
  3. Now we will insert data in the newly created node.
void insertNodeAtBeginning(int num)
{
    struct node * newnode;
    if(stnode == NULL)
    {
        cout<<" No data found in the list\n";
    }
    else
    {
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->num = num;
        newnode->nextptr = stnode;  
        newnode->preptr = NULL;     
        stnode->preptr = newnode;   
        stnode = newnode;          
    }
}
Type of insertion | At beginning

Insertion at specific position

Insertion at specific position

How to perform insertion at specific position in doubly linked list?

To perform insertion at specific position in doubly linked list we will use the following steps:-

  1. We will traverse till the specific position in the list.
  2. We will insert a node here by changing linking the next pointer of the previous node to new node.
  3. Also we will linked the previous pointer of next node with the new node.
void insertSpecific(int num, int pos)
{
    int i;
    struct node * newnode, *tmp;
    if(ennode == NULL)
    {
        cout<<" No data found in the list!\n";
    }
    else
    {
        tmp = stnode;
        i=1;
        while(i<pos-1 && tmp!=NULL)
        {
            tmp = tmp->nextptr;
            i++;
        }
        if(tmp!=NULL)
        {
            newnode = (struct node *)malloc(sizeof(struct node));
            newnode->num = num;
                        
            newnode->nextptr = tmp->nextptr; 
                        
            newnode->preptr = tmp;              
            if(tmp->nextptr != NULL)
            {
                tmp->nextptr->preptr = newnode; 
            }
            tmp->nextptr = newnode; 
        }
        else
        {
            cout<<" The position you entered, is invalid.\n";
        }
    }
} 
Type of insertion | At specific position

Insertion at end

Insertion at end

How to perform insertion at end in singly linked list?

To perform insertion at end in singly linked list we will use the following steps:-

After creating a linked list with some data in it we will :-

  1. Use a pointer to traverse till the end of the list.
  2. After that we will create a new node after the last node.
  3. Insert the data that you want to enter by putting it in the node.
void insertNodeAtEnd(int num)
{
    struct node * newnode;
 
    if(ennode == NULL)
    {
        cout<<" No data found in the list!\n";
    }
    else
    {
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->num = num;
        newnode->nextptr = NULL;        
        newnode->preptr = ennode;       
        ennode->nextptr = newnode;      
        ennode = newnode;                 
    }
}
Type of insertion | At end