How do you delete a node in a linked list if head is not given?

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

A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement.

Table of Contents Show

• Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
• Problem Statement
• Approach to delete node without head pointer
• If head pointer was given
• Delete a Node from linked list without head pointer in C++
• Deleting a node from a linked list without head pointer
• How do you delete a node from singly linked list when you are given only the node?
• How do you delete a node in a linked list Python?

The fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like this:

It is important to note that this approach will only work if it is guaranteed that the given pointer does not point to the last node. Because if it is the last node, then you don’t have a next node to copy the data from.

struct Node *temp = node_ptr->next; node_ptr->data = temp->data; node_ptr->next = temp->next; free(temp);

Below is the implementation of the above code:

C++

// C++ program to del the node // in which only a single pointer // is known pointing to that node #include <assert.h> #include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public: int data; Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new 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(Node* head) { Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void deleteNode(Node* node_ptr) { // If the node to be deleted is the // last node of linked list if (node_ptr->next == NULL) { free(node_ptr); // this will simply make the node_ptr NULL. return; } // if node to be deleted is the first or // any node in between the linked list. Node* temp = node_ptr->next; node_ptr->data = temp->data; node_ptr->next = temp->next; free(temp); } // Driver code int main() { /* Start with the empty list */ 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); cout << "Before deleting \n"; printList(head); /* I m deleting the head itself. You can check for more cases */ deleteNode(head); cout << "\nAfter deleting \n"; printList(head); return 0; } // This code is contributed by rathbhupendra

C

// C++ program to del the node // in which only a single pointer // is known pointing to that node #include <assert.h> #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ 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 the node to be deleted is the last // node of linked list if (node_ptr->next == NULL) { free(node_ptr); // this will simply make the node_ptr NULL. return; } struct Node* temp = node_ptr->next; node_ptr->data = temp->data; node_ptr->next = temp->next; free(temp); } // Driver code int main() { /* Start with the empty list */ 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); /* I m deleting the head itself. You can check for more cases */ deleteNode(head); printf("\n After deleting \n"); printList(head); getchar(); }

Java

// Java program to del the node in // which only a single pointer is // known pointing to that node class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } void deleteNode(Node node) { Node temp = node.next; node.data = temp.data; node.next = temp.next; System.gc(); } // Driver code public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(12); list.head.next.next = new Node(1); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(1); System.out.println("Before Deleting "); list.printList(head); /* I m deleting the head itself. You can check for more cases */ list.deleteNode(head); System.out.println(""); System.out.println("After deleting "); list.printList(head); } } // This code has been contributed by Mayank Jaiswal

Python3

# A python3 program to delete # the node in which only a single pointer # is known pointing to that node # Linked list node class Node(): def __init__(self): self.data = None self.next = None # Given a reference (pointer to pointer) # to the head of a list and an int, # push a new node on the front of the list def push(head_ref, new_data): # allocate node new_node = 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 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 # Driver code if __name__ == '__main__': # Start with the empty list head = None # Use push() to construct below list # 1->12->1->4->1 head = push(head, 1) head = push(head, 4) head = push(head, 1) head = push(head, 12) head = push(head, 1) print("Before deleting ") printList(head) # I'm deleting the head itself. # You can check for more cases deleteNode(head) print("\nAfter deleting") printList(head) # This code is contributed by Yashyasvi Agarwal

C#

// C# program to del the node in // which only a single pointer is // known pointing to that node using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } void deleteNode(Node node) { Node temp = node.next; node.data = temp.data; node.next = temp.next; } // Driver code public static void Main() { LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(12); list.head.next.next = new Node(1); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(1); Console.WriteLine("Before Deleting "); list.printList(list.head); /* I m deleting the head itself. You can check for more cases */ list.deleteNode(list.head); Console.WriteLine(""); Console.WriteLine("After deleting "); list.printList(list.head); } } /* This code contributed by PrinciRaj1992 */

Javascript

<script> // javascript program to del the node in // which only a single pointer is // known pointing to that node var head; class Node{ constructor(val){ this.data = val; this.next = null; } } function printList(node){ while (node != null){ document.write(node.data + " "); node = node.next; } } function deleteNode(node) { var temp = node.next; node.data = temp.data; node.next = temp.next; } // Driver code head = new Node(1); head.next = new Node(12); head.next.next = new Node(1); head.next.next.next = new Node(4); head.next.next.next.next = new Node(1); document.write("Before Deleting<br/> "); printList(head); /* * I m deleting the head itself. You can check for more cases */ deleteNode(head); document.write("<br/>"); document.write("After deleting<br/> "); printList(head); // This code is contributed by todaysgaurav </script>

Output

Before deleting 1 12 1 4 1 After deleting 12 1 4 1

To make this solution work, we can mark the end node as a dummy node. But the programs/functions that are using this function should also be modified.
Try this problem in a doubly-linked list.

Article Tags :

Linked List

Practice Tags :

Linked List

Read Full Article

Problem Statement

The problem “Delete a Node from linked list without head pointer” states that you have a linked list with some nodes. Now you want to delete a node but you don’t have its parent node address. So delete this node.

Example

Pin

Explanation: Since we wanted to delete the node with value 4. We removed it from the linked list and are left with a list that is mentioned in the output.

Approach to delete node without head pointer

Linked List is a linear data structure that has a huge advantage over an array is that it can vary in size. If you want to add an element in a linked list, you can add it in O(1) time. Considering that you are inserting the element in the first place. But if you had to do the same in a normal array. It will cost you O(N) time to do so. Thus it is favorable to use a linked list over an array in real-world applications. And linked list achieves all of this because it does not store the data as a contiguous chunk. It stores each element at some random location. But then how does it maintain order? The answer to this question is, the linked list takes the usage of the pointer. Each node points to another node in the linked list and this way we do not have to allocate a single chunk changing which in turn would have required many computations.

If head pointer was given

Now the problem asks us to delete a node. Generally, we are given a node’s address and are required to delete the next node in the linked list. But here we are required to delete a node whose address is given to us. One way to solve this problem is to first traverse the whole linked list. Then store the parent of each node and break the loop when you are at a node that is provided as input. This way in the end we have the parent of the node to be deleted. So now the problem is changed to the simple deletion of a node in the linked list whose parent’s address is given. But doing this will cost us O(N) operations. But this way can be used only when you have the head pointer.

Solution

The approach for the problem “Delete a Node from linked list without head pointer” would be to swap the data of the node to be deleted and the next node in the linked list. Each node in the linked list stores which node is next. So this operation has only O(1) time complexity. Now when the data has been swapped. Once again, we have changed the problem to the deletion of the node whose parent’s address is given. So now it’s easier for us to solve the problem. But there is one edge case when we have to delete the end node but we won’t be able to delete that. Because there is no next node.

Delete a Node from linked list without head pointer in C++

In this tutorial, we are going to learn how to delete a node without head pointer in a singly linked list.

Let's see the steps to solve the problem.

• Write struct with data, and next pointer.

• Write a function to insert the node into the singly linked list.

• Initialize the singly linked list with dummy data.

• Take a node from the linked list using the next pointer.

• Move the delete node to the next node.

Deleting a node from a linked list without head pointer

In this article, we are going to see how to delete a node in a linked list without having head pointer?
Submitted by Radib Kar, on February 11, 2019

Problem statement:

Write a program to delete a node in a linked list where the head pointer to the node is not given, only the address of the node to be deleted is provided.

Example:

Solution:

In this problem we don’t have head to the list, we only have address of the node to be deleted that is pointer to the node 1

So actually we have access to the part:

So we can simply swap the node values one by one:

And then make the last node NULL

So the total linked list actually begins:

Algorithm:

C++ implementation

Output

How do you delete a node from singly linked list when you are given only the node?

A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement. The fast solution is to copy the data from the next node to the node to be deleted and delete the next node.

How do you delete a node in a linked list Python?

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

1. Find the previous node of the node to be deleted.
2. Change the next of the previous node.
3. Free memory for the node to be deleted.