Insertion in singly linked list at the end

Two scenarios are mentioned while inserting a node at the last. These are:

  • Inserting a node to an empty list.
  • Inserting a node to the end of a linked list.

Inserting a node to an empty list:

  • In this case, the condition (head == NULL) gets satisfied. Thus, only the space for the node needs to be allocated by using the malloc statement in C. We can use the below statements to set up the data and the linked part of the node.
    ptr->data = item;  
    ptr -> next = NULL;  
    
  • Here, the ptr is the only node that will be inserted in the list. We can thus use the below statement to make this node pointed by the head pointer of the list.
    Head = ptr     
    

Inserting a node to the end of a linked list:

  • In this case, Head is not null, thus, the condition Head = NULL would fail. To traverse through the list, a temporary pointer temp needs to be declared which is made to point the first node of the list.
    Temp = head   
    
  • We can use the below statements to traverse through the entire linked list.
    while (temp→ next != NULL)  
    temp = temp → next;  
    
  • The last node of the list is what the temp will be pointing to, at the end of the loop. Along with allocating the space for the new node, we need to assign the item to its data part. Now, the next part of this node needs to be pointing to the null. This is because the new node is going to be the last node of the list. The next part of the temp node is thus, the last node of the list at present. We need to point this part of the temp node to the new node (ptr).
    temp = head;  
    while (temp -> next != NULL)  
    {  
     temp = temp -> next;  
    }  
    temp->next = ptr;  
    ptr->next = NULL;  
    

Algorithm:

  • Step 1:
    IF PTR = NULL Write OVERFLOW
    Go to Step 1
    [END OF IF]
  • Step 2: SET NEW_NODE = PTR
  • Step 3: SET PTR = PTR – > NEXT
  • Step 4: SET NEW_NODE – > DATA = VAL
  • Step 5: SET NEW_NODE – > NEXT = NULL
  • Step 6: SET PTR = HEAD
  • Step 7: Repeat Step 8 while PTR – > NEXT != NULL
  • Step 8:
    SET PTR = PTR - > NEXT
    [END OF LOOP]
    
  • Step 9: SET PTR – > NEXT = NEW_NODE
  • Step 10: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void insertNodeAtEnd(int);  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\nEnter the element to insert:\n");  
        scanf("%d",&item);  
        insertNodeAtEnd(item);  
        printf("\nPress 0 to insert more elements:\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void insertNodeAtEnd(int item)  
    {  
        struct node *ptr = (struct node*)malloc(sizeof(struct node));     
        struct node *temp;  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW");     
        }  
        else  
        {  
            ptr->data = item;  
            if(head == NULL)  
            {  
                ptr -> next = NULL;  
                head = ptr;  
                printf("\nNode inserted successfully!!");  
            }  
            else  
            {  
                temp = head;  
                while (temp -> next != NULL)  
                {  
                    temp = temp -> next;  
                }  
                temp->next = ptr;  
                ptr->next = NULL;  
                printf("\nNode inserted successfully!!");  
 
            }  
        }  
    }

Output:

Enter the element to insert:
2
 
Node inserted successfully!!
Press 0 to insert more elements:
0
 
Enter the element to insert:
4
 
Node inserted successfully!!
Press 0 to insert more elements:
0
 
Enter the element to insert:
6
 
Node inserted successfully!!
Press 0 to insert more elements:
 
Enter the element to insert:
8
 
Node inserted successfully!!
Press 0 to insert more elements:
10
Content Protection by DMCA.com
Please Share