This is strange question of Space Complexity. Can someone provide any insights?

Question

I was solving this question when this approach clicked in -

Given a single linked list and an integer x. Your task is to complete the function deleteAllOccurances() which deletes all occurrences of a key x present in the linked list. The function takes two arguments: the head of the linked list and an integer x. The function should return the head of the modified linked list.

I am not sure what is the space complexity of my code.

I think since I am only using 1 extra Node space and simultaneously creating new nodes and deleting old ones, so it should be O(1).

Node* deleteAllOccurances(Node *head,int x)
{
   Node *new_head = new Node(-1);
   Node *tail = new_head;
   Node *temp = head;
   Node *q;

   while(temp != NULL) {
      if(temp->data != x) {
        tail->next = new Node(temp->data);
        tail = tail->next;
      }

       q = temp;
       delete q;
       temp = temp->next;
    }

   tail->next = NULL;
   return new_head->next;
}

Answer 1

Well, kind of.

It depends on whether you are considering total allocations as a net change (in which case you're right).

But if you are thinking about the amount of times you hit the heap for new allocations, then it's using more space and a ton of computation. (A given C++ compiler and runtime is not obliged to guarantee immediately reusing space freed in the heap, just that it's available for reuse.)

As a C++ programmer for decades, what you're doing is mildly horrifying because you're doing a lot of new allocation. That results in thrashing the heap allocation structures.

Also, the way you're doing this is pushing stuff which doesn't match to the end of the list so you are shuffling the contents down.

Hint - you should not need to create any new Nodes.