Delete elements conditionally in a Singly Linked List in C++

Question

I'm having a problem in a function that deletes an element in a singly linked list. The element needs to be deleted conditionnaly with the function ShouldDelete().

I haven't found a similar request in C++ in the forums so any help would be appreciated. It seems that the following code does not work 100% of the time.

void SinglyLinkedList::DeleteObjects(Node *pStartPtr)
{
    Node *pPtr = pStartPtr;
    Node *temp;
    while(pPtr != nullptr)
    {
        temp = pPtr->next;
        if (pPtr->ShouldDelete())
        {
            delete pPtr;
            pPtr = temp;
            if(temp != nullptr)
            {
               pPtr->next = temp->next;
            }
        }
        pPtr = temp;
    }
}

Any thoughts ?

Thanks!

BTW.: Im always passing the head of the list as an argument. — George Vital, Jan 22 '19 at 04:05
`pPtr->next = temp->next;` this won't do anything since `pPtr = temp;` And then to delete any node you need a pointer to previous node which you don't have. Maybe you want to delete `temp` as `pPtr` can serve as the previous pointer — Gaurav Sehgal, Jan 22 '19 at 04:15
You can't delete the head pointer with this code unless you allow for the head pointer to change. if this was `c++` you could change `void SinglyLinkedList::DeleteObjects(Node* pStartPtr)` to `void SinglyLinkedList::DeleteObjects(Node* & pStartPtr)` to fix this. There would be different methods for `c`. — drescherjm, Jan 22 '19 at 04:17
*BTW.: Im always passing the head of the list as an argument.* this raises the question "Why?" Is the list head not a member of `SinglyLinkedList`? If not, new question: "Why not?" — user4581301, Jan 22 '19 at 05:08
Sidenote: deleting nodes from singly linked lists is almost laughably easy when you use a pointer to a pointer to a `Node` (`Node **`) and point it to the the address of the `next` pointer. This `Node**` provides an updatable link to the last `Node` and to the `Node` you're investigating. [Great example here](https://stackoverflow.com/a/22122095/4581301). — user4581301, Jan 22 '19 at 05:18

score 0 · Answer 1 · answered Jan 22 '19 at 07:28

As a general C++ advice, I would use std::list instead of a DIY list implementation, but since I wrote quite some list logic myself in the old C-days, I'll give it a go.

There are 2 essential problems with your code.

First of all, whenever removing an element from a single-linked list, you should set the next pointer of the previous element to the next of the deleted one. You can do something like this:

Node *previousNode = …;
while(pPtr != nullptr)
   {
   Node *nextNode = pPtr->next;
   if (pPtr->ShouldDelete())
      {
      delete pPtr;
      previousNode->next = nextNode;
      }
   else
      {
      previousNode = pPtr;
      }
   pPtr = nextNode;
   }

Notice that no specific if-tests within the for-loop on nullptr are needed. You should tell the previous node that it now points to the next of the deleted one. If there is no next one, the previous->next will just point to a nullptr, indicating the end of the list.

The second problem is that you don't have any clear 'start of the list'. In my example code above, it becomes quite hard to indicate what the previousNode is. Is it a nullptr? But what if we remove the first element?

You could easily add logic here to indicate keep track of the first element, initialize previousNode to nullptr, and if the first is deleted, just don't set previousNode->next' and keep previousNode equal tonullptr` in that case, but what about the caller? How can the caller know that the first element has been deleted and the list now starts later.

My preferred solution is to have a separate List struct/class, and keep the start of the list (the first Node) as a member in the List struct/class. Instead of passing the startNode to the function, you should pass the List instance. The code in the while-loop now becomes a bit longer, since you need to adapt previousNode->next=nextNode to this:

if (previousNode)
   previousNode->next = nextNode;
else
   list->firstNode = nextNode;

If you don't want to introduce a new List struct/class, you could also return the new firstNode as return value from your function, like this:

if (previousNode)
   previousNode->next = nextNode;
else
   startNode  = nextNode;
…
return startNode;

Notice that this second approach only works if the caller if the function is also the one maintaining the list, and there are no other places pointing to the startNode. In any case, if multithreading is involved, you probably want a decent List class with a kind of mutex (ideally std::list decorated with a mutex).

Delete elements conditionally in a Singly Linked List in C++

1 Answers1