{"id":4193,"date":"2021-08-21T06:56:35","date_gmt":"2021-08-21T06:56:35","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4193"},"modified":"2023-07-27T13:05:05","modified_gmt":"2023-07-27T13:05:05","slug":"delete-a-node-at-a-given-position","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/delete-a-node-at-a-given-position\/","title":{"rendered":"Delete a Node at a Given Position in Singly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

In this blog we will see how to delete a node from the singly linked list before the specified position. Given a singly linked list and a specific position, we must delete a node in that position in a singly linked list. Linked lists are fundamental data structures used in computer science to store and manage collections of elements efficiently. They offer dynamic memory allocation and provide flexible means of adding, removing, and traversing elements. Two common variations of linked lists are singly linked lists and doubly linked lists, each with its unique features and use cases.<\/p>\n

How to Delete a Node at a Given Position in a Singly Linked List<\/h3>\n

Let’s start with an example to better understand the problem statement.
\nSuppose the linked list is 1 \u2192 5 \u2192 2 \u2192 7 and the position given is 2. So, we have to delete the node present at the second position.<\/p>\n

Note:<\/strong> We are using 0 based indexing in this problem.<\/p>\n

The node in the second position of the given linked list is 2. As a result, we must remove two items from the given list. The final linked list after deleting 2 will be: 1 \u2192 5 \u2192 7<\/p>\n

Input :<\/strong><\/p>\n

\"\"<\/p>\n

Output :<\/strong><\/p>\n

\"\"<\/p>\n

Explanation:<\/strong> The node at the 2nd position has been deleted.
\nWhat approach should we take to this problem? What comes to mind first when we consider how to delete a node from a linked list at a given position? Attempt to obtain the position, correct?
\nYes, but with a slight modification.
\nTo delete a node, we must also have a pointer to its predecessor. This can be solved by traversing until the (position – 1)th node.<\/p>\n

Let’s take a look at the approach.<\/p>\n

Approach on How to Delete a Node Before a Given Position in a Singly Linked List<\/h3>\n

First, let’s think in terms of how to delete a node from the linked list at a given position. <\/p>\n

Let the linked list be:<\/p>\n

1 \u2192 5 \u2192 2 \u2192 7.<\/p>\n

So, here, if we delete the node (2), we get :<\/p>\n

1 \u2192 5 \u2192 7.<\/p>\n

So, by deleting the node(2) we are making a connection between node(1) and node(5). That means the next of node(1) point to node(5).<\/p>\n

Observation<\/strong><\/p>\n

    \n
  • If we take some more examples, we will notice that we need to access the previous and next node of the node that we need to delete.<\/li>\n
  • Say if the node to be deleted is target, its previous node is prev, and its next node is next1. So, to delete the target node from the linked list, we need to perform the following operations:
    \n1) prev \u2192 next = next1.
    \n2) And finally, free the target node.<\/li>\n<\/ul>\n

    By doing this, we are removing the target node at the given position and changing the necessary links.<\/p>\n

    There are a few corner cases. Try to think them out by taking a few examples. Everything is discussed in detail in the algorithm section delete a node from linked list at a given position.<\/p>\n

    Algorithm for How to Delete a Node Before a Given Position in a Singly Linked List<\/h3>\n
      \n
    • If the head is NULL, return.<\/li>\n
    • Create a node temp and make it point to the head.<\/li>\n
    • If the position is 0, it means that we have to delete the head of the list. We can easily do that by head = temp \u2192 next and free(temp). As temp was pointing to the head, we have incremented the head and freed temp.<\/li>\n
    • If the position is not 0, we will proceed. Now, we will write a loop with i = 0 to i < (position -1). As we have discussed, to delete a node, we need a pointer to its previous node. So while traversing the loop, we will increment temp.<\/li>\n
    • Now, after the loop ends, if the temp is NULL or temp \u2192 next is NULL, we will simply return as the position is more than the number of nodes in the linked list.<\/li>\n
    • If the above condition fails, we will have temp pointing to the (position – 1)th node. Now, we simply have to change the required pointers.<\/li>\n
    • We will save the temp \u2192 next \u2192 next in a new node next1. Now, we will free temp \u2192 next, as it is the node at the given position. In the end, temp \u2192 next = next1. – In this way, there is no unnecessary memory leak and the node at the given position is getting deleted successfully.<\/li>\n<\/ul>\n

      Now, as are having the idea for the algorithm to delete a node before specified position in singly linked list in C. Let\u2019s see the dry to understand more in depth to delete a node from linked list at a given position.<\/p>\n

      Dry Run on How to Delete a Node Before a Given Position in a Singly Linked List<\/h3>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      Code Implementation on How to Delete a Node at a Given Position in a Singly Linked List<\/h3>\n\t\t\t\t\t\t