Delete specific Node in Linked list

Question

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!

Why is flag static? Once you have deleted one node, the function will always return true. — molbdnilo
– molbdnilo, Commented Sep 19, 2018 at 10:47
@molbdnilo cause after every recursive loop flag will be 0 although there's deleted node — Lê Trâm
– Lê Trâm, Commented Sep 19, 2018 at 10:51
It's static, so it's only initialised once, which is the first time the function is called. — molbdnilo
– molbdnilo, Commented Sep 19, 2018 at 10:52
What made you use recursion here. Removing elements in LList is always O(n). Just traverse the list and delete that matches the delete condition. — Rizwan
– Rizwan, Commented Sep 19, 2018 at 10:53
To debug it, sit down with a pad of paper and a pencil and draw your list and all the pointers. This is the best method for debugging pointer-oriented algorithms and structures. — molbdnilo
– molbdnilo, Commented Sep 19, 2018 at 10:58

Praneeth Peiris · Accepted Answer · 2018-09-19 11:27:36Z

Your approach has several issues.

You're using a static flag. (See the other comments to know why it's bad.)
You're using recursion. Since you're using a static flag, it screws up the recursion.
You can delete the element while iterating itself, then the runtime would be O(n).
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;
}

Swift - Friday Pie · Accepted Answer · 2018-09-19 10:53:23Z

0

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.

edited Sep 19, 2018 at 10:53

answered Sep 19, 2018 at 10:48

Swift - Friday Pie

15.6k3 gold badges26 silver badges53 bronze badges

Collectives™ on Stack Overflow

Delete specific Node in Linked list

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related