Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Deleting Node in Different Situations
2.1.
Getting rid of the initial node
2.2.
Delete a node in the middle: 
2.3.
Delete the final node: 
2.4.
Delete the linked list element with the provided value: 
2.5.
Time Complexity 
2.6.
Auxiliary Space Complexity 
3.
Frequently Asked Questions
3.1.
What is the procedure for deleting a node after a specific node?  
3.2.
What is data structure deletion?  
3.3.
In a binary search tree, what is the difficulty of deletion? 
3.4.
In DSA, what is the AVL tree?  
3.5.
What is the definition of a delete operation? 
4.
Conclusion
Last Updated: Mar 27, 2024

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.

Frequently Asked Questions

What is the procedure for deleting a node after a specific node?  

If the root node is to be deleted, simply delete it. To delete a middle node, we need a pointer to the node before the one we want to destroy. If positions are not zero, we conduct a position-1 loop to obtain a pointer to the preceding node. 

What is data structure deletion?  

Deletion is the process of eliminating an existing element from an array and reorganizing all of its elements. ​​The act of removing a specific element from an array. If an element is removed from its current location, all items from the (i+1)th location must be shifted one step to the left. As a result, the (i+1)  element is transferred to the (i+1) place, and so on.

In a binary search tree, what is the difficulty of deletion? 

Time complexity is O in general (h). The deletion of element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).

In DSA, what is the AVL tree?  

A binary search tree in which the height difference between each node’s left and right subtrees is less than or equal to one is known as an AVL tree. Adelson, Velskii, and Landi discovered the approach for balancing the height of binary trees, which is known as the AVL tree or Balanced Binary Tree. 

What is the definition of a delete operation? 

Deletion is the process of eliminating an existing element from an array and reorganizing all of its elements. The delete action can be applied to one or more objects that meet the specified conditional expression. The delete operation can be combined with a list (of any kind), allowing the user to select the object(s) to be erased.

Conclusion

This article has gone through Deleting Node in Different Situations, Removing an element from the list's beginning. The list is displayed in its entirety. Searches for an element using the specified key. Check out our articles in Library. You may also CheckOut our course on the linked list.

Attempt our Online Mock Test Series on Coding Ninjas Studio now! 

Ninja, have a great time learning.

Live masterclass