Remove node from singly linked list

[4ET0pfjN]

Hi, for my remove node, I return boolean. I assume I need to use pointers to pointers since there is potential to update original pointer in the form of prev, but it's not running (it compiles)...

struct sll_node//Singly linked list node
{
  string data;
  sll_node *next;
};

bool remove(string node_data, sll_node **front)
{
  bool isFound = false;
  sll_node **cur = front;//Repointer CUR points to ptr that points to node to //delete
  sll_node **prev = NULL;//Repointer PREV to repoint actual linked list end ptr
  //*prev = NULL;
  //*prev = NULL; **prev = "0";
	
  while ( *cur != NULL )
  {
    //IF front of list, update front ptr to pt to next or null (if just one  //elem in list)
   //NB: if *prev is NULL => *cur is pointing to our node and node found
   if ( (*cur)->data == node_data && *prev == NULL )
   {
	//advance to next node
	*front = (*front)->next;//NB: if just one item in list and this item is to be deleted, (*front)->next points to NULL
			
	delete cur;
	cur = NULL;
	return (isFound = true);
	}
		
	//ELSE IF somewhere in the middle of list, update prev ptr->next to be cur ptr->next, delete cur, set cur to NULL
	else if ( (*cur)->data == node_data && *prev != NULL )
	{
		(*prev)->next = (*cur)->next;
		delete cur;
		cur = NULL;
		return (isFound = true);
	}
		
	*prev = *cur;
	(*cur) = (*cur)->next;
		
  }//END WHILE LOOP
	
  //if empty list, while loop never runs since *cur == NULL
  if ( *cur == NULL && *prev == NULL )//*prev is NULL b/c empty list so it stays as same val it was initialized to
  {
	return isFound;//isFound is false
  }
	
  //IF we reached end of list (i.e. *cur == NULL ) and found, otherwise isFound is false still when returned
  if ( (*cur)->data == node_data && *cur == NULL && *prev != NULL )
  {
	(*prev)->next = (*cur)->next;
	delete cur;
	return (isFound = true);	
  }
  else
	return isFound;//isFound is false
}

int main()
{
  sll_node *front = new sll_node;
  sll_node *end = new sll_node;
  front = NULL; end = NULL;
 	
  insert_at_end("A", &front, &end);//This is working btw

  bool isFound = remove("hello", &front);
	
  cout << isFound << endl;
  return 0;
}

[Disch]

Very interesting code.


EDIT: to clarify (and to be less of a wiseguy), are you showing us this just to show it to us? Or did you have a question about it? Because I don't see you asking a question anywhere, so I'm not sure what you want.

[4ET0pfjN]

It doesn't work...my remove function

[Disch]

"it doesn't work" is about as vague as you can get. What isn't working? What do you expect it to do and what is it actually doing?

We're not mindreaders. Give us details.

[4ET0pfjN]

it's supposed to find a node node_data and remove it. I assume I can use pointers to pointers in function declaration since there is potential to modify original pointer in linked list created in main function. Is my use of delete cur correct too? I'm sure my logic is right for deleting, but I think it's my use of pointers that's messing up...

[vlad from moscow]

here

  sll_node *front = new sll_node;
  sll_node *end = new sll_node;
  front = NULL; end = NULL;

you allocate memory and at the same time you reassign the pointers to NULL. So you have leak of memory.

[4ET0pfjN]

That's not it, I changed to

sll_node *front = NULL;
sll_node *end = NULL;

it's still crashing...I know it's my remove function as I have tried with my insert_at_end function and traversed it to output it's node and it's fine.

[vlad from moscow]

You should show the real code. Otherwise there is no any great sense to discuss it.

[4ET0pfjN]

here's my insert_at_end, but it's my remove function that crashes:

void insert_at_end(string node_data, sll_node **front, sll_node **end)
{
	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;//NB: repointer will change the content of our actual front pointer (remember it stores an address) to point to another node
		*end = newNode;//NB: repointer will change the content of our actual front pointer (remember it stores an address) to point to another node
	}
	
	//Else the list is not empty, so just update tail ptr and leave head ptr alone!
	else
	{
		(*end)->next = newNode;
		*end = newNode;
	}
}

[4ET0pfjN]

I've removed the pointers to pointers, and changed to more meaningful pointer return type and it's all good...

The reason why I thought using pointers to pointers would be proper is b/c I thought we have to modify the original pointer for front of the list, so now I'm confused why I can just use front = front->list, b/c I thought I had to use a pointer to actual front pointer in my list in main function...this pointers stuff really gets me....

sll_node *remove(string node_data, sll_node *front)//NB: just use search fcn to know if node exists before we call remove fcn
{
	//bool isFound = false;
	sll_node *cur = front;//Repointer CUR points to ptr (that in turn points to node to delete)
	sll_node *prev = NULL;//Repointer PREV to repoint actual linked list end ptr
	//*prev = NULL;
	//*prev = NULL; **prev = "0";
	
	while ( cur != NULL )//NB: cleaner with for loop
	{
		//IF front of list, update front ptr to pt to next or null (if just one elem in list)
		//NB: if *prev is NULL => *cur is pointing to our node and node found
		if ( (cur)->data == node_data && prev == NULL )
		{
			//advance to next node
			front = (front)->next;//NB: if just one item in list and this item is to be deleted, (*front)->next points to NULL
			delete cur; cur = NULL;
			return front;
		}
		
		//ELSE IF somewhere in the middle of list, update prev ptr->next to be cur ptr->next, delete cur, set cur to NULL
		else if ( (cur)->data == node_data && prev != NULL )
		{
			(prev)->next = (cur)->next;
			delete cur; cur = NULL;
			return front;
		}
		
		prev = cur;
		cur = cur->next;//if *cur->next, then we reached end of list so stop here and delete cur and set *prev->next = NULL and make
		//	end repoint to prev...
		
	}//END WHILE LOOP
	
	//if empty list, while loop never runs since *cur == NULL
	if ( cur == NULL && prev == NULL )//*prev is NULL b/c empty list so it stays as same val it was initialized to
		return front;
	
	return front;//return NULL otherwise if not found somewhere else in list (could be in middle or reached end of list )	
}

[4ET0pfjN]

how would i use pointers to pointers for my remove function above and why does it work WITHOUT using pointers to pointers since we could potentially modify original front pointer to the list in main function...anyone?

[D80DSL3A]

Your remove() could also potentially modify end (if the node to be deleted is the last one in the list) so you need to also pass a pointer to end.

The method should work. I think you ran into trouble using sll_node**'s in the function for prev and cur. This isn't necessary.

I just wrote this remove() and found that it works fine:

bool remove( string Data, sll_node** pFront, sll_node** pBack )
{
    if( pFront && pBack && *pFront && *pBack )
    {
        // check first node explicitly
        if( (*pFront)->data == Data )
        {
            sll_node* temp = *pFront;// save pointer to node to be deleted
            *pFront = (*pFront)->next;// front is modified
            delete temp;// delete old front
            return true;
        }
        // now check the remaining nodes
        if( (*pFront)->next )
        {
            sll_node* prev = *pFront;
            sll_node* cur = prev->next;

            while( cur )// iterate through the list
            {
                if( cur->data == Data )// found it!
                {
                    prev->next = cur->next;// link across node to be deleted
                    if( cur == *pBack )// check if at end of list
                        *pBack = prev;// back is modified

                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->next;
            }
        }
    }
    return false;
}// end of remove() 

Notice that returning a single pointer from the function wouldn't be adequate anyways since either front or end may be modified.

Another method is to pass front by reference (instead of passing a pointer to it). This method may be deemed "cleaner" because it eliminates the need for the multiple dereferencing of pointers in the function.

[4ET0pfjN]

I was right about front = front->back not making sense to me since a pointer just in function argument is passed by value (a copy of the address only so the real front pointer never gets modified as I just ran my remove function and it crashes, but it works fine when trying to remove a node in middle or last node in list...I will look into your code, thanks for reply.

Actually it doesn't need pointer to end pointer since cur will always point to the node to delete, so once it reaches NULL (end of list), it returns NULL.

Also, my remove function w/ sll_node pointer return type returns the updated list (which is essentially pointer front which points to front of the list or else NULL, not returning the node I want to remove.

I'm not sure about passing by reference, I will also have to look into this. Right now I'm trying to learn properly pointers/pointer to pointers...

[4ET0pfjN]

Well, I've fixed my pointer return remove function as such:

sll_node *remove(string node_data, sll_node *front)
{
	sll_node *cur = *front;//Repointer CUR points to ptr (that in turn points to node to delete)
	sll_node *prev = NULL;//Repointer PREV to repoint actual linked list end ptr
	
	while ( cur != NULL )
	{
		//IF front of list, update front ptr to pt to next or null (if just one elem in list)
		//NB: if *prev is NULL => *cur is pointing to our node and node found
		if ( (cur)->data == node_data && prev == NULL )
		{
			//advance front pointer to next node
			*front = (*front)->next;//NB: if just one item in list and this item is to be deleted, (*front)->next points to NULL
			delete cur; cur = NULL;
			return *front;
		}
		
		//ELSE IF somewhere in the middle of list, update prev ptr->next to be cur ptr->next, delete cur, set cur to NULL
		else if ( (cur)->data == node_data && prev != NULL )
		{
			(prev)->next = (cur)->next;
			delete cur; cur = NULL;
			return *front;
		}
		
		prev = cur;
		cur = cur->next;
		
	}//END WHILE LOOP
	
	//if empty list, while loop never runs since *cur == NULL
	if ( cur == NULL && prev == NULL )//*prev is NULL b/c empty list so it stays as same val it was initialized to
		return *front;
	
	return *front;//return NULL otherwise if not found somewhere else in list (could be in middle or reached end of list )	
}

[D80DSL3A]

Glad you got your function working. I see you gave up on using pointers to pointers. Your approach seems fine though as long as only one pointer must be changed.

About the need to modify the end pointer:

mx760 wrote:

Actually it doesn't need pointer to end pointer since cur will always point to the node to delete, so once it reaches NULL (end of list), it returns NULL.

It's true that the last node can be deleted by iterating to it with cur, but it appears that you are trying to maintain a pointer to the last node in your sll list.
I see a sll_node* end in your main() and it is passed to your insert_at_end().
If the last node is deleted and the end pointer is not modified in the remove() then it will be left pointing to a node which has been deleted.

EDIT: Are you sure your new function compiles ok? Line 13 looks wrong.

[4ET0pfjN]

Typo, the argument front should be a pointer to a pointer. Thanks for tha, fun2code. Here is correct code that works like a charm and it's shorter and cleaner :)

sll_node *remove(string node_data, sll_node **front)
{
	sll_node *cur = *front;//Repointer CUR points to ptr (that in turn points to node to delete)
	sll_node *prev = NULL;//Repointer PREV to repoint actual linked list end ptr
	
	if ( cur == NULL && prev == NULL ) return *front;//if empty list

        if ( (cur)->data == node_data && prev == NULL )//if new node is smaller than current front node in list
        {
		*front = (*front)->next;
		delete cur; cur = NULL;
		return *front;
	}
	
         for ( ;cur != NULL; prev = cur; cur = cur->next)
		if ( (cur)->data == node_data && prev != NULL )//new node goes somewhere else in list
		{
			(prev)->next = (cur)->next;
			delete cur; cur = NULL;
			return *front;
		}
	
	return *front;
}

Also, regarding:

I see a sll_node* end in your main() and it is passed to your insert_at_end().

I actually wrote another insert_at_end function. You see, I'm just trying to get real comfortable with pointers and singly linked lists as a comp sci student graduating very soon...I need that good job :)