How to insert a node after a specified node in a linked list?


To insert a new node after the specified node in a singly linked list, first we get the number of the node in an existing singly linked list after which the new node is to be inserted. This is based on the assumption that the nodes of the list are numbered serially from 1 to n. The list is then traversed to get a pointer to the node, whose number is given. If this pointer is x, then the link field of the new node is made to point to the node pointed to by x, and the link field of the node pointed to by x is made to point to the new node.

Figure 1 and  2 show the list before and after the insertion of the node, respectively.


/* a function which inserts a newly created node after the specified
   node */
struct node * newinsert ( struct node *p, int node_no, int value )
{
        struct node *temp, * temp1;
        int i;
        if ( node_no <= 0 || node_no > length (p))
        {
                printf("Error! the specified node does not exist\n");
                exit(0);
        }
        if ( node_no == 0)
        {
                temp = ( struct node * )malloc ( sizeof ( struct node ));
                if ( temp == NULL )
                {
                        printf( " Cannot allocate \n");
                        exit (0);
                }
                temp -> data = value;
                temp -> link = p;
                p = temp ;
        }
        else
        {
                temp = p ;
                i = 1;
                while ( i < node_no )
                {
                        i = i+1;
                        temp = temp-> link ;
                }
                temp1 = ( struct node * )malloc ( sizeof(struct node));
                if ( temp == NULL )
                {
                        printf ("Cannot allocate \n");
                        exit(0)
                }
                temp1 -> data = value ;
                temp1 -> link = temp -> link;
                temp -> link = temp1;
        }
        return (p);
}

Linked List before Insertion of the new node

Linked List after Insertion of the new node

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: