Is this the right way to delete a node?

Question

This is how I am deleting a node from a singly linked list. Would this be the most correct way?

void Remove(Node** head, int value)
{
 Node** ptr = head;
 while (*ptr && (*ptr)->data != value)
 ptr = &(*ptr)->next;
 if (*ptr)
 { 
 Node* next = (*ptr)->next;
 delete *ptr;
 *ptr = next;
 }
} 

• Sungguk Lim: Please don't use double pointer(**). it makes difficult to read code.

Answer 1

Comments

This is not really C++.
It is just some C code.

Code Review

Everything @matsjoyce said:

1. Don't need 'head'
2. Always use '{}' around sub block statements.

Naming conventions

In C++ it is common convention that names of objects (anything that can have its address taken) begins with a lower case letter (this includes function and method names). So I would rename Remove to remove. This is so it is easier to spot the names of user defined types (which should begin with an upper case letters).

Design

Encapsulation is your friend.
A free function to delete elements from a list is the wrong way to go. You should have created a list class that contains nodes. Then add a member function to delete the node.

Query

By the way, why a singly linked list? That sounds like premature optimization to me. Code is much simpler using a doubly linked list (with a sentinel). Of course you are writing in C so you are probably trying to write optimal code down as close to the metal with no help from language semantics.

Without double indirection

Double indirection is horrible. It is hard to read and hard to use in the code. If you want to pass something that needs to be updated pass a reference to the object. Then it will be updated in the function.

A simple technique for traversing a singly linked list is to use two pointers. A pointer to the current element and a pointer to the previous element. Unlinking the element then becomes a simple assignment to the previous element.

class SinleLinkedList
{
 public:
 void remove(int value)
 {
 remove(head, value);
 }
 private:
 Node* head;
 void remove(Node*& ptr, int value)
 {
 Node* prev = NULL 
 Node* current = ptr;
 
 while(current && current->data != value)
 {
 prev = current;
 current = prev->next;
 }
 
 // If current is not NULL then we fell out of the
 // above loop because the != failed so it must be equal
 if (current /*&& current->data == value*/ )
 {
 // Set the value we are going to update after delete.
 // If prev == NULL its the head, otherwise we update
 // next pointer from the prev element.
 Node*& result = (prev == nullptr) ? ptr : prev->next;
 
 // Save the next value.
 // Delete the old node and update.
 Node* next = current->next;
 delete current;
 result = next;
 }
 }
};
 

• glampert: Well, the OP is tagged with C++11, so you can replace the NULLs with nullptr. Apart from that, very good answer. +1
• Sungguk Lim: nice code. I'm a little uncomfortable about Node*&. is it really necessary? anyway not to use it?
• Loki Astari: @sunglim: No. There are many ways to do this. I tried to stick close to the original. But it is not that difficult to do it without.

Answer 2

OK, this is what I see:

Node** ptr = head;

You don't really need this, you can just change the name in the function arguments or just use head later on.

while (*ptr && (*ptr)->data != value)
 ptr = &(*ptr)->next;

It may be advantageous to add curly brackets around the body, just to stop surprises later.

Then you end up with:

void Remove(Node** ptr, int value)
{
 while (*ptr && (*ptr)->data != value)
 {
 ptr = &(*ptr)->next;
 }
 if (*ptr)
 { 
 Node* next = (*ptr)->next;
 delete *ptr;
 *ptr = next;
 }
} 

There may be other improvements, but knowing the structure of a Node would be useful.

Answer 3

Issues that I see:

1. You are not making the links between the previous item of the list with the next item of the item being deleted. With your current code, the previous item's next points to a deleted Node.

2. You don't need a Node** ptr;. A Node* ptr; is sufficient. The code is more readable with the second definition.

Here's my updated version.

void Remove(Node** head, int value)
{
 // Boundary case.
 // value is the first item.
 if ( *head->data == value )
 {
 Node* temp = *head;
 *head = *head->next;
 delete temp;
 return;
 }
 Node* ptr = *head;
 Node* prev = ptr; // Need this to make sure that links are properly
 // taken care of when deleting the node containing 
 // the item.
 while ((ptr != NULL) && (ptr->data != value))
 {
 prev = ptr;
 ptr = ptr->next;
 }
 if (ptr)
 {
 // Make sure that links in the linked list are properly
 // maintained.
 prev->next = ptr->next;
 delete ptr;
 }
} 

• 200_success: Of the four answers, this is the first one to point out that the code is completely broken. (In my opinion, the question should have been closed for containing obviously broken code, but the fact that three reviewers failed to spot the bug makes me hesitant to do so.)

Answer 4

Just an observation:

1. You won't be modifying the value of head, so you do not require a double pointer (except with an overhead of a previous pointer). Keep it simple.
2. Have a return type (boolean or int) to know if the deletion was a success (found it and deleted it) or failure (null linked list, didn't find the value).