Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

Last Updated on November 16, 2022 by Prepbytes

Introduction

In this article, we will discuss about given only a pointer to a node in a singly linked list, how can we delete that node. The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp on Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given only a pointer to a node to be deleted in a singly linked list. We have to delete that node from the list.

Problem Statement Understanding

Well, our lives would’ve been easier if we were given the pointer to the head.

• In that case, a simple traversal would’ve done the job.

But, here, we don’t have a pointer to the head; instead we have a pointer to the node that is to be deleted.

Suppose the given list is

and we have a pointer to 2.

• So, according to the problem statement, we have to delete 2 from the list, and also we don’t have the head pointer.
• The final resultant list will be after deletion of 2 will be

Well, now that we’ve understood the problem statement, let us discuss how we can approach this problem.

So, how should we approach this problem?

• Well, instead of deleting the node, we can copy the data from the next node and then delete the next node. This will work. Let us dive deeper into the approach section.

Approach about how to delete a node from a linked list, if only a pointer to that node is given

Our approach is going to be pretty straightforward.

• Suppose the pointer given is node (Pointer node is pointing to the node to be deleted).

• Now, to delete the node to which pointer node is pointing, we will perform the following steps:

  • First, we will copy the data of node → next in node.
  • Then, we will create a pointer, say temp, and point it to node -> next.
  • After that, we will make node -> next point to node -> next -> next.
  • In the end, we will delete temp.

• Finally, after performing the above steps, our task will be over, the node to which pointer node was pointing will get deleted from the list.

Let us take an example.

• Suppose our list is 1 → 2 → 3 → 4, and we have a pointer to the node with value 2.
• According to the problem statement, we have to delete 2.
• Now, instead of deleting 2, we will first copy the value of 2 → next, i.e., 3 in 2.
• So, after copying, the list will look like 1 → 3 → 3 → 4.
• Now, we will simply make the 2^nd node point to 4.
• So, our final list will be 1 → 3 → 4.
• As we can see, we have successfully deleted the node with value 2 from the list.

Note: This approach will only work if the node to be deleted is not the last node of the list. As we are copying the next node’s data, the last node doesn’t have a next node, so it would throw an error.

Algorithm about how to delete a node from a linked list, if only a pointer to that node is given

• Create a pointer temp and store current node’s next in it.
• Now, copy the current node’s next’s data in the current node using current – > data = temp – > data (As temp = current – > next)
• Now, as the data has been copied, we can delete the next node of the current. So, make current – > next = temp – > next (Changing links).
• In the end, free(temp).

Dry Run of how to delete a node from a linked list, if only a pointer to that node is given

Code Implementation of how to delete a node from a linked list, if only a pointer to that node is given:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    /* put in the data  */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
 
void deleteNode(struct Node* node_ptr)
{
    if (node_ptr->next == NULL)
    {
        free(node_ptr);
        
        return;
    }
    struct Node* temp = node_ptr->next;
    node_ptr->data = temp->data;
    node_ptr->next = temp->next;
    free(temp);
}
 
int main()
{
    struct Node* head = NULL;
 
    /* Use push() to construct below list
    1->12->1->4->1  */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);
 
    printf("\n Before deleting \n");
    printList(head);
 
    deleteNode(head);
 
    printf("\n After deleting \n");
    printList(head);
    getchar();
}

#include <assert.h>
#include <bits stdc++.h="">
using namespace std;

/* Structure of a linked list node */
class Node {
public:
    int data;
    Node* next;
};

/* Inserting a node at the head of a linked list */
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;
}

/* Using this function we will be printing the content of the linked list */
void printList(Node* head)
{
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

/* Using this function we will be deleting a node whose pointer is given in input */
void deleteNode(Node* node_ptr)
{
    if (node_ptr->next == NULL)
    {
        free(node_ptr);
    
        return;
    }
    
    Node* temp = node_ptr->next;
    node_ptr->data = temp->data;
    node_ptr->next = temp->next;
    free(temp);
}

/* Main function (driver function) */
int main()
{
    Node* head = NULL;

    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    cout << "Linked list before deleting the node \n";
    printList(head);

    deleteNode(head->next);

    cout << "\nLinked list after deleting the node \n";
    printList(head);
    return 0;
}

public class LinkedList {

    static Node head;
    /* Node structure of a linked list */
    static class Node {

        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    
    /* Using this function we will be printing the content of the linked list */
    void printList(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    /* Using this function we will be deleting a node whose pointer is given in input */
    void deleteNode(Node node)
    {
        Node temp = node.next;
        node.data = temp.data;
        node.next = temp.next;
        System.gc();
    }
    
    /* Main function (Driver function) */
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);

        System.out.println("Linked list before deleting the node");
        list.printList(head);

        list.deleteNode(head.next);
        System.out.println("");
        System.out.println("Linked list after deleting the node ");
        list.printList(head);
    }
}

class Node():
    def __init__(self):
        self.data = None
        self.next = None

def push(head_ref, new_data):

    new_node = Node()
    new_node.data = new_data
    new_node.next = head_ref
    head_ref = new_node

    return head_ref


def printList(head):
    temp = head
    while(temp != None):
        print(temp.data, end=' ')
        temp = temp.next


def deleteNode(node_ptr):
    temp = node_ptr.next
    node_ptr.data = temp.data
    node_ptr.next = temp.next


if __name__ == '__main__':

    head = None

    head = push(head, 4)
    head = push(head, 3)
    head = push(head, 2)
    head = push(head, 1)

    print("Before deleting ")
    printList(head)

    deleteNode(head.next)

    print("\nAfter deleting")
    printList(head)

Output

Linked list before deleting the node
1 2 3 4
Linked list after deleting the node
1 3 4

Time Complexity: O(1), as no traversal is needed.

So, in this article, we have tried to explain how to delete a node from a linked list, if only a pointer to that node is given. Learning linked list plays a very crucial rolein the interview process as majorly companies asked questions based on linked list. This is a very tricky and 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.

FAQ Related to how to delete a node from a linked list, if only a pointer to that node is given

1. How do you delete a specific node in a linked list?

To delete a node from the linked list, we need to do the following steps:

• Find the previous node of the node to be deleted.
• Change the next of the previous node.
• Free memory for the node to be deleted.
2. What is underflow in linked list?

Underflow is a condition that occurs when we try to delete a node from a linked list that is empty. This happens when START = NULL or when there are no more nodes to delete. Note that when we delete a node from a linked list, we actually have to free the memory occupied by that node.

3. Why do we need linked list pointers?

The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list. A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.