Given only a pointer/reference to a node to be deleted in a singly linked list, how do you delete it?
Last Updated :
18 Oct, 2023
Given a pointer to a node to be deleted, delete the node. Note that we don’t have a pointer to the head 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. Something like the following.
// Find next node using next pointer
struct Node *temp = node_ptr->next;
// Copy data of next node to this node
node_ptr->data = temp->data;
// Unlink next node
node_ptr->next = temp->next;
// Delete next node
free(temp);
Program:
C++
#include <bits/stdc++.h>
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 printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void deleteNode(Node* node)
{
Node* prev;
if (node == NULL)
return;
else {
Node* temp = node->next;
node->data = temp->data;
node->next = temp->next;
temp = NULL;
}
}
int main()
{
Node* head = NULL;
push(&head, 1);
push(&head, 4);
push(&head, 1);
push(&head, 12);
push(&head, 1);
cout << "Before deleting \n";
printList(head);
deleteNode(head);
cout << "\nAfter deleting \n";
printList(head);
return 0;
}
|
C
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*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)
{
struct Node* prev;
if (node == NULL)
return;
else {
Node* temp = node->next;
node->data = temp->data;
node->next = temp->next;
temp = NULL;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 1);
push(&head, 4);
push(&head, 1);
push(&head, 12);
push(&head, 1);
printf("Before deleting \n");
printList(head);
deleteNode(head);
printf("\nAfter deleting \n");
printList(head);
getchar();
return 0;
}
|
Java
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;
}
public void printList()
{
Node tNode = head;
while (tNode != null) {
System.out.print(tNode.data + " ");
tNode = tNode.next;
}
}
public void deleteNode(Node Node_ptr)
{
Node temp = Node_ptr.next;
Node_ptr.data = temp.data;
Node_ptr.next = temp.next;
temp = null;
}
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);
System.out.println("Before deleting");
llist.printList();
llist.deleteNode(llist.head);
System.out.println("\nAfter Deleting");
llist.printList();
}
}
|
Python
class Node():
def __init__(self, val = None):
self.data = val
self.next = None
def push(head, val):
newnode = Node(val)
newnode.next = head.next
head.next = newnode
def print_list(head):
temp = head.next
while(temp != None):
print(temp.data, end = ' ')
temp = temp.next
print()
def delete_node(node):
prev = Node()
if(node == None):
return
else:
temp = Node()
temp = node.next;
node.data = temp.data;
node.next = temp.next;
temp = None;
if __name__ == '__main__':
head = Node()
push(head, 1)
push(head, 4)
push(head, 1)
push(head, 12)
push(head, 1)
print('list before deleting:')
print_list(head)
delete_node(head.next)
print('list after deleting: ')
print_list(head)
|
C#
using System;
public class LinkedList
{
Node head;
public class Node
{
public int data;
public Node next;
public 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;
}
public void printList()
{
Node tNode = head;
while (tNode != null)
{
Console.Write(tNode.data + " ");
tNode = tNode.next;
}
}
public void deleteNode(Node Node_ptr)
{
Node temp = Node_ptr.next;
Node_ptr.data = temp.data;
Node_ptr.next = temp.next;
temp = null;
}
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);
Console.WriteLine("Before deleting");
llist.printList();
llist.deleteNode(llist.head);
Console.WriteLine("\nAfter Deleting");
llist.printList();
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function push(new_data) {
var new_Node = new Node(new_data);
new_Node.next = head;
head = new_Node;
}
function printList() {
var tNode = head;
while (tNode != null) {
document.write(tNode.data + " ");
tNode = tNode.next;
}
}
function deleteNode(Node_ptr) {
var temp = Node_ptr.next;
Node_ptr.data = temp.data;
Node_ptr.next = temp.next;
temp = null;
}
push(1);
push(4);
push(1);
push(12);
push(1);
document.write("Before deleting<br/>");
printList();
deleteNode(head);
document.write("<br/>After Deleting <br/>");
printList();
</script>
|
Output:
Before deleting
1 12 1 4 1
After deleting
12 1 4 1
Time Complexity:
- For printing linked list: O(N)
- For inserting node: O(1)
- For deleting node: O(N)
- Auxiliary Space: O(1)
This solution doesn’t work if the node to be deleted is the last node of the list. 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.
Exercise: Try this problem with the doubly linked list.
One line in the function deletenode():
C++
void deleteNode(Node *node)
{
*node = *(node->next);
}
|
Java
static void deleteNode(Node node)
{
node = (node.next);
}
|
Python3
def deleteNode(Node Node):
Node = (Node.next);
|
C#
void deleteNode(Node *node)
{
*node = *(node->next);
}
|
Javascript
function deleteNode(node)
{
node = (node.next);
}
</script>
|
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...