Delete a node at a given position

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list and a position. We have to delete the node present at the given position.

Problem Statement Understanding

Let’s first understand the problem statement with help of an example.

Suppose the linked list is 1 β†’ 5 β†’ 2 β†’ 7 and the position given is 2. So, we have to delete the node present at the 2nd position.

Note : We are using 0 based indexing in this problem.

Here, in the given linked list, the node present at the 2nd position is 2. So, we have to delete 2 from the given list. Final linked list after deleting 2 will be: 1 β†’ 5 β†’ 7

Input :

Output :

Explanation : The node at the 2nd position has been deleted.

How should we approach this problem? What is the first thing that comes to mind? Try to reach the position, right?
Yes, But with a little change.

To delete a node, we should also have the pointer to its previous node. We can tackle this by traversing till the (position - 1)th node.

Let us have a glance at the approach.

Approach

First, let's think in terms of linked list what deleting a node means.

Let the linked list be:
1 β†’ 5 β†’ 2 β†’ 7.

So, here, if we delete the node (2), we get :
1 β†’ 5 β†’ 7.

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).

Observation

  • If we take some more examples, we will notice that we need to access the previous and the next node of the node that we need to delete.

Say, if the node to be deleted is target, and its previous node is prev and its next node is next1. So, to do the deletion of target node from the linked list, we need to perform the following operations:
1) prev β†’ next = next1.
2) And finally free the target node.

By doing this, we are removing the target node at the given position and changing the necessary links.

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.

Algorithm

  • If the head is NULL, return.
  • Create a node temp and make it point to the head.
  • 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 β†’ next and free(temp). As temp was pointing to the head, we have incremented the head and freed temp.
  • 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.
  • Now, after the loop ends, if the temp is NULL or temp β†’ next is NULL, we will simply return as the position is more than the number of nodes in the linked list.
  • 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.
  • We will save the temp β†’ next β†’ next in a new node next1. Now, we will free temp β†’ next, as it is the node at the given position. In the end, temp β†’ next = next1. - In this way, there is no unnecessary memory leak and the node at the given position is getting deleted successfully.

Dry Run

Code Implementation

#include 
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

void push(Node** head_ref, int new_data)
{
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void deleteNode(Node **head_ref, int position)
{

    if (*head_ref == NULL)
        return;

    Node* temp = *head_ref;

    if (position == 0)
    {

        *head_ref = temp->next;

        free(temp);            
        return;
    }
 
    for(int i = 0; temp != NULL && i < position - 1; i++)
        temp = temp->next;

    if (temp == NULL || temp->next == NULL)
        return;

     Node *next1 = temp->next->next;
 
    
    free(temp->next); 

    temp->next = next1;
}

void printList( Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{

    Node* head = NULL;
 
    push(&head, 7);
    push(&head, 2);
    push(&head, 5);
    push(&head, 1);
 
    cout << "Created Linked List: ";
    printList(head);
    deleteNode(&head, 2);
    cout << "\nLinked List after Deletion at position 2: ";
    printList(head);
    return 0;
}
public class LinkedList
{
    Node head; 
    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public void push(int new_data)
    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;
    }

    void deleteNode(int position)
    {

        if (head == null)
            return;

        Node temp = head;

        if (position == 0)
        {
            head = temp.next;  
            return;
        }

        for (int i=0; temp!=null && i

						 

Output

Created Linked List: 1 5 2 7
Linked List after Deletion at position 2: 1 5 7

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to delete a node at a given position. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Find the smallest and largest elements in a singly linked list
Next post LinkedList add() method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *