Delete a node in the Linked List under the given conditions

Introduction

This article will learn the function of deleting a node from a Singly Linked List. A linked list is a collection of data structures linked together via links. A Linked List is a list of items taken up from a series of links. Each link is connected to a different link. After array, the linked list is the most often used Data Structure. The following constraints must be met by our function for implementing the deletion of a node in the Linklist.

• No pointer to the head node should be returned.
   
• Pointer to pointer to the head node should not be accepted.
   
• It must take a pointer to the start node as the first parameter and a pointer to the node to be deleted as the second parameter; a pointer to the head node is not global. 

Deleting Node in Different Situations

Getting rid of the initial node

1. Create a delete first struct Node* method that, after eliminating the current head, returns the pointer to the new head. 
    
2. In the function, we'll pass the current head pointer. 
    
3. Make a new struct Node* pointer ptr with the current head as the pointer. 
    
4. Because this will be the new head of the linked list, assign head to the next member of the list using head = head->next. 
    
5. The pointer ptr should be freed. Return the head as well.
    

// Case 1: The first member in the linked list is removed. 
struct Node * deleteFirst(struct Node * head){
    struct Node * ptr = head;
    head = head->next;
    free(ptr);
    return head;
}

Delete a node in the middle: 

1. Create a deleteAtIndex struct Node* function that returns the pointer to the head. 
    
2. We'll send the current head pointer and the index where the node should be destroyed to the function. 
    
3. Create a new struct Node* pointer pointing to the head, with the value p. 
    
4. Create a new struct Node* pointer q pointing to head->next, then loop until this pointer reaches the index when the node will be deleted. 
    
5. Using p-> next = q->next, assign q->next to the next item of the p structure. 
    
6. Free the pointer q, as it no longer has any connections to the list. 
    
7. Return to your original position.
    

// Case 2: Removing an element from a linked list at a specific index. 
struct Node * deleteAtIndex(struct Node * head, int index){
    struct Node *p = head;
    struct Node *q = head->next;
    for (int i = 0; i < index-1; I++)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = q->next;
    free(q);
    return head;
}

Delete the final node: 

1. Delete the last node in the same way you would any other index. The discrepancy persists at the while loop's end. In this case, we run a loop until the pointer reaches the end of the list and points to NULL. 
    
2. Using p-> next = NULL, assign NULL to the next item of the p structure. 
    
3. By releasing the ptr q, you can break the link between q and NULL. 
    
4. Return to your original position.
    

/ /Case 3: Delete the last element struct Node * deleteAtLast(struct Node * head) 
struct Node * deleteAtLast(struct Node * head){
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->next !=NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = NULL;
    free(q);
    return head;
}

Delete the linked list element with the provided value: 

1. We already have a value in the list that has to be removed. The important thing is that only the first occurrence will be deleted. 
    
2. Create a deleted value struct Node* method that returns the pointer to the head. 
    
3. Pass the head node and the value to be erased to this function. 
    
4. Make a new struct Node* pointer pointing to the head, with the value p. 
    
5. Make a new struct Node* pointer q that points to the next head. 
    
6. Run a while loop until the pointer q reaches the specified value, or the list is exhausted. 
    
7. If it comes across the value, delete that node by setting p to the next node and skipping node q. Also, q must be freed from memory.
    
8. And if the list simply ends, it signifies the list included no such value. Continue without taking any action. 
    
9. Return to your original position.
    

//Case 4: Deleting an element from a linked list with a given value 
struct Node * deleteByValue(struct Node * head, int value)
{
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->data!=value && q->next!= NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    if(q->data == value)
    
    {
        p->next = q->next;
        free(q);
    }
    return head;
}

Time Complexity 

O(N), Where ‘N’ stands for the length of the linked list.

Reason: Finding the element you wish to delete takes O(N) time, this is because you have to shift all components to their right and one space to the left so that you can delete it.

Auxiliary Space Complexity 

O(1) 

Reason: Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.