Recursive singly linked list removal

[4ET0pfjN]

I sort of understand the use of &(*front)->next which would mean the address of the actual front pointer's next node, I'm not sure. Also, the function works to remove a node at front or somewhere else, BUT when I'm trying to find a non-existent node, the program crashes.

struct sll_node//singly linked list node
{
   string date;
   sll_node *next;
};

sll_node* r_remove(string node_data, sll_node** front, sll_node* prev_)//returns updated list (so front ptr) or NULL (reached end of list and not found)
{
	sll_node* prev = prev_;
	sll_node* cur = *front;//pts to what front ptr points to initially
	
	if ( prev == NULL && cur == NULL ) return NULL;//Base case:if empty list
	
	else if ( cur->data == node_data && prev == NULL )//base case: else if node to remove is first node, update front to point to next node in line
	{
	   *front = (*front)->next;
	   delete cur; cur = NULL;
	   return *front;
	}
	// if we find node to remove somewhere else, return updated list (=>return ptr front (front pts to list)
	//node could either be first node or somewhere else in list (need to update relink w/ prev and delete cur)
	else if ( cur->data == node_data && prev != NULL )
	{
	   prev->next = cur->next;
	   delete cur; cur = NULL;
	   return *front;
	}
	
	//if EOL (reached end of list), => node not on list since we always compare w/ cur ptr and once cur pts to NULL, of course no more items to compare with!
	else if ( cur == NULL && prev != NULL ) return NULL;
	
	else return r_remove(node_data, &(*front)->next, *front);//keep traversing
}

int main()
{
   sll_node *front = NULL;
   sll_node *end = NULL;
	
   insert_at_end("j", &front, &end);//I have this working
   insert_at_end("d", &front, &end);
	
   insert_at_front("h", &front);//I have this function working
   insert_at_front("g", &front);

   if ( !r_remove("jad", &front, NULL) )
      cout << "No node found to be removed" << endl;
   else
      cout << "Removed" << endl;

   return 0;
}

So the list is: g->h->j->d

[naraku9333]

Why are you complicating things with pointer to pointer to a node? This line *front = (*front)->next; for example would be front = front->next; if front was just a pointer to a node.

[SirSmilesaLot]

else if ( cur == NULL && prev != NULL ) return NULL;
modify to

else if ( cur->next ==  NULL ) return NULL;

Post ur insertion code as well.

[naraku9333]

It looks like you are actually making two lists, one named front and one named end, they do not appear to be connected in any way. Also in the remove function prev doesn't point to the previous node which is necessary to remove a node in a singly linked list. I would also suggest doing the remove iteratively if possible, it is usually faster and definitely easier to follow.

[4ET0pfjN]

I thought we need to use a pointer to a pointer whenever we need to modify the original pointer and since I want the actual front pointer (i.e. from the singly linked list declared in main), I need to repoint that front pointer.


Here is the my insert_at_end (I've tested it and works):
=======================================

void insert_at_end(string node_data, sll_node **front, sll_node **end)tr
{
	sll_node *newNode = new sll_node;
	newNode->data = node_data;
	newNode->next = NULL;
	
	//If list is empty, then head and tail pts to the newNode
	if ( *front == NULL && *end == NULL )	
	{
		*front = newNode;
		*end = newNode;
	}
	
	//Else the list is not empty, so just update tail ptr and leave head ptr alone!
	else
	{
		(*end)->next = newNode;
		*end = newNode;
	}
}

Here is my insert_at_front (I've tested it and it works btw):
==========================================

void insert_at_front(string node_data, sll_node **front)
{
	sll_node *newNode = new sll_node;
	newNode->data = node_data;
	
	//If our list is empty, then make front ptr just point to node newNode
	if ( *front == NULL )
	{
		newNode->next = NULL;
		*front = newNode;
		return;//BAD PRACTICE as it could be easily missed but I jus want to use it for small code (SO use if-else instead)
	}
	
	newNode->next = *front;
	*front = newNode;
}

[4ET0pfjN]

Thanks anirudh sn for the reply. It's working now, but I'm cursious as to why it cannot be:

else if ( cur == NULL && prev != NULL ) return NULL;

and must be:

else if ( cur->next == NULL && prev != NULL ) return NULL;

I don't understand is b/c I have pointer cur always pointing to the node to remove, and prev is used to relink w/ cur's next node, so once pointer cur points to end of list which is NULL, it should return NULL.