Delete node given pointer to it

© Parineeth M R

Question 5. Delete a node in a linked list given only a pointer/reference to that node


Let us say that we are given only a pointer n1 to the node that needs to be deleted. We don’t know the node previous to n1. If we delete the node that n1 points to, then we can’t update the next pointer of the node preceding n1. So we can’t directly delete n1, but we have to employ a trick to do the job.
To solve the problem, let n2 be the pointer to the node next to n1. We copy n2->data into n1->data. We also copy n2->next into n1->next. Now n1 points to a node that is exactly identical to the node pointed by n2. Now instead of deleting n1, we delete n2. This achieves the required result.
This solution will not work if the node being deleted is the last node in the linked list and the last node points to NULL. One possible approach to make this solution work for all nodes in the linked list is to use a circular linked list.

C/C++


/* 
n1: pointer to the node to be deleted
Return value: 0 on success, -1 on failure
*/
int delete_node(struct node *n1)
{
	struct node *n2;

	if (n1->next) {
		/*Get the pointer to the next node*/
		n2 = n1->next;

		/*Copy the contents of the next node into the current node*/
		n1->data = n2->data;
		n1->next = n2->next;

		/*Free the next node*/
		free(n2);

		/*Return indicating the operation is successful*/
		return 0;
	}

	/*return indicating the operation failed*/
	return -1;
}


Java


/* 
n1: the node to be deleted
Return value: true on success, false on failure
*/
public static boolean deleteNode(LinkedListNode n1) {

	if (n1.next != null) {
		/*Get the next node*/
		LinkedListNode n2 = n1.next;

		/*Copy the contents of the next node into the current node*/
		n1.data = n2.data;
		n1.next = n2.next;

		/*Return indicating the operation is successful*/
		return true;
	}

	/*return indicating the operation failed*/
	return false;
}


Python


#n1: the node to be deleted
#Return value: True on success, False on failure
@staticmethod
def delete_node(n1):
	if (n1.next): 
		#Get the next node
		n2 = n1.next

		#Copy the contents of the next node into the current node
		n1.data = n2.data
		n1.next = n2.next

		#Return indicating the operation is successful
		return True

	#return indicating the operation failed
	return False