Deleting an Element from a Linear Linked List

To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). This tutorial covers the deletion of a node from the following three positions:

1. At the beginning of the list
2. At the end of the list
3. After a given element

Deleting from the Beginning of the List

An element from the beginning of the list can be deleted by performing the following steps:

• Assign the value of head (address of the first element of the list) to a temporary variable (say temp)
• Assign the value of the next pointer field of the first node to head.
• Deallocate the memory occupied by the node pointed to by temp.

void deletefrombeginning( node **head)

{

    node *temp;

    if (*head == NULL)

        return;

    else

    {

        temp = *head;

        *head = (*head) ->next;

        free(temp);

    }

}

Deleting from the End of the List

To delete from the end of the list, we first traverse to the second last element of the list. Then the last element can be deleted by performing the following steps:

• Assign the next pointer field of the second last node to a temporary variable (say temp).
• Assign NULL to the next pointer field of the second last node of the list.
• Deallocate the memory occupied by the node pointed to by temp.

void deletefromend( node **head)

{

    node *temp, *prev;

    if (*head == NULL)

        return;

    else if ((*head)->next == NULL)

    {

        temp = *head;

        *head = NULL;

        free(temp);

    }

    else

    {

        prev = *head;

        temp = (*head)->next;

        while (temp->next != NULL)

        {

            prev = temp;

            temp = temp->next;

        }

        prev->next = NULL;

        free(temp);

    }

}

Deleting after a Given Element

To delete an element after a given element, first we find the location, sayprev, of the element after which the element can be deleted by performing the following steps:

• Assign the next pointer field of the node pointed by prev to a temporary variable (say temp).
• Assign the next pointer field of the node to be deleted to the next pointer field of node pointed to by prev.
• Deallocate the memory occupied by the node pointed to by temp.

void deleteafterelement(node *head, int after)

{

    node *temp, *prev;

    prev = searchunsortedlist(head,after);

    if (prev==NULL)   /*element 'after' not found*/

        return;

    temp= prev->next;

    prev->next=temp->next;

    free(temp);

}

Deleting the Entire List

Before the program terminates, the entire list must be deleted so that the memory occupied by the nodes of the list is properly released to the OS. This task can be accomplished by performing the following steps:

• Assign the head pointer to a temporary variable, say temp.
• Advance the head pointer to the next node.
• Deallocate the memory occupied by the node pointed to by temp.

The above steps are repeated till the entire list is deleted.

void deletelist(node **head)

{

    node *temp;

    while(*head!=NULL)

    {

        temp = *head;

        *head = (*head)->next;

        free(temp);

    }

}