CODEWITHSUNDEEP
c++linked-list
Lê Trâm
Lê Trâm

Reputation: 43

Delete specific Node in Linked list

I have a linked list like this

struct product {
string ID;
double quantity;
product* next = NULL;
};

And I want to delete all products with quantity less than a number. This function returns true if at least one product are deleted, otherwise returns false. Here is my code

bool deleteProducts(product*& pHead, double quantity) {
    static int flag = 0;
    product* pTemp = pHead;
    product* prev = pHead;
    if (pTemp != NULL && pTemp->quantity <= quantity) pHead = pTemp->next;
    while (pTemp != NULL && pTemp->quantity > quantity) {
        prev = pTemp;
        pTemp = pTemp->next;
    }
    if (pTemp == NULL) return flag;
    flag = 1;
    prev->next = pTemp->next;
    deleteProducts(prev->next, quantity);
}

But when I have a list (quantities only) like this: 

7 -> 7.5 -> 2 -> 5 -> 6

And I run the function with quantity = 10, it return:

7.5 -> 5

It's not true, can anybody explain for me. Thanks in advance!

Upvotes: 1

Views: 84

Answers (2)

Praneeth Peiris
Praneeth Peiris

Reputation: 2088

Your approach has several issues.

  1. You're using a static flag. (See the other comments to know why it's bad.)
  2. You're using recursion. Since you're using a static flag, it screws up the recursion.
  3. You can delete the element while iterating itself, then the runtime would be O(n).
  4. You can use a doubly linked-list to avoid using the pPrev in the loop.

Here is the proper solution I came up with.

#include <iostream>
#include <string>

using namespace std;

typedef struct product {
    string ID;
    double quantity;
    product* next = NULL;
} product;

product* deleteProducts(product*& pHead, double quantity) {
    product* pTemp = pHead;
    product* pPrev = pHead;

    while (pTemp != NULL) {
        if ( pTemp->quantity > quantity ){
            if ( pTemp == pHead ){
                cout << "Deleteing Current Head " <<  pTemp->quantity << endl;
                product* pTmp = pHead;
                pTemp = pTemp->next;
                pHead = pPrev = pTemp;
                delete pTmp;
            }
            else{
                cout << "Deleteing Node" <<  pTemp->quantity << endl;
                product* pNext = pTemp->next;
                delete pTemp;
                pTemp = pNext;
                pPrev->next = pTemp;
            }
        }
        else{        
            pPrev = pTemp;
            pTemp = pTemp->next;
        }
    }

    return pHead;
}

bool printProducts(product*& pHead) {
    product* pTemp = pHead;

    while (pTemp != NULL) {
        cout << pTemp->quantity << " ";
        pTemp = pTemp->next;
    }

    cout << endl;
}

int main()
{
   product* p1 = new product{"1", 7};
   product* p2 = new product{"2", 7.5};
   product* p3 = new product{"3", 2};
   product* p4 = new product{"4", 5};
   product* p5 = new product{"5", 6};

   p1->next = p2;
   p2->next = p3;
   p3->next = p4;
   p4->next = p5;

   if ( deleteProducts(p1, 10) ){
       cout << "Done" << endl;
   }

   printProducts(p1);

   return 0;
}

Upvotes: 1

Swift - Friday Pie
Swift - Friday Pie

Reputation: 14589

Your starting state short-circuits list onto pHead, setting local prev to address of pHead. Why not use pHead ->prev or nullptr?

And removing elements from doubly linked list is operation with time compexity O(n) operation. You have to walk through list and collapse those records that match your criteria.

Upvotes: 0

Related Questions