How to delete a specified node from a Linked List?


Deleting a specified node from a linked List

To delete a node, first we determine the node number to be deleted (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, as well as a pointer to a node that appears before the node to be deleted. Then the link field of the node that appears before the node to be deleted is made to point to the node that appears after the node to be deleted, and the node to be deleted is freed.

Implementation :

struct node *delet ( struct node *p, int node_no )
{

        struct node *prev, *curr ;
        int i;

        if (p == NULL )
        {
                printf("There is no node to be deleted \n");
        }
        else
        {
                if ( node_no > length (p))
                {
                        printf("Error\n");
                }
                else
                {
                        prev = NULL;
                        curr = p;
                        i = 1 ;
                        while ( i < node_no ) { prev = curr; curr = curr-> link;
                                i = i+1;
                        }
                        if ( prev == NULL )
                        {
                                p = curr -> link;
                                free ( curr );
                        }
                        else
                        {
                                prev -> link = curr -> link ;
                                free ( curr );
                        }
                }
        }
        return(p);
}
/* a function to compute the length of a linked list */
int length ( struct node *p )
{
        int count = 0 ;
        while ( p != NULL )
        {
                count++;
                p = p->link;
        }
        return ( count ) ;
}

Figure 1 : before delete

Figure 2 : After delete

Advertisements
  1. Sorting and Reversing a Linked List « Encrypt3d

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: