c linked list, removing element disconnects the rest of the list-CodePudding

I was trying to implement this simple linked list project for my homework. When I tried to implement the removeByKey function, I ran into the problem that it disconnects the rest of the list entirely when it finds the key to be removed.

Here's the class:

class LancElem
{
private:
    int key;
    LancElem* next;
public:
    LancElem(){next = nullptr;}
    LancElem(int keyy, LancElem* nextt){key = keyy;next = nextt;}
    LancElem* getNext(){return next;}
    int getKey(){return key;}
    void setNext(LancElem* nextt){next = nextt; }
    void setKey(int keyy){key = keyy;}
};

The remove fucntion:

void removeByKey(LancElem& head, int key){
    LancElem* n = head.getNext();
    while(n->getNext()!=nullptr){
        if(n->getNext()->getKey()==key){
            n->setNext(n->getNext()->getNext());
            delete n->getNext();
            break;
        }
        n=n->getNext();
    }
}

When I try to remove the biggest element:

The original linked list: 4 1 9 8 2 7 3 6 3

Expected output: 4 1 8 2 7 3 6 3

The real output: 4 1 0

The problem is probably where I connect the current element to the next->next element but I can't figure out why my implementation isn't good.

CodePudding user response：

Ask yourself:

What is n->next after the line n->setNext(n->getNext()->getNext()); ? What does the line delete n->getNext(); delete?

You don't want to delete the just updated next but you want to delete the to be removed element:

        auto to_be_deleted = n->getNext(); 
        n->setNext(to_be_deleted->getNext());
        delete to_be_deleted;

CodePudding user response：

It seems your list has a dummy head node that does not have a value.

The function removeByKey can invoke undefined behavior when head.getNext() returns a null pointer due to using the expression n->getNext()

LancElem* n = head.getNext();
while(n->getNext()!=nullptr){

Also within the if statement

    if(n->getNext()->getKey()==key){
        n->setNext(n->getNext()->getNext());
        delete n->getNext();
        break;
    }

you are trying to delete a node after the node to be deleted due to preceding assignment of the data member next by using the function setNext.

        n->setNext(n->getNext()->getNext());
        delete n->getNext();

Pay attention to that your function is unable to delete the node after the dummy head node due to using by you two times the call of getNext()

LancElem* n = head.getNext();  // the first call of getNext
while(n->getNext()!=nullptr){
    if(n->getNext()->getKey()==key){   // the second call of getNext.
    //...

The function can be defined like

void removeByKey( LancElem &head, int key )
{
    if ( head.getNext() != nullptr )
    {
        if ( head.getNext()->getKey() == key )
        {
            LancElem *current = head.getNext();
            head.setNext( head.getNext()->getNext() );
            delete current;
        }
        else
        {
            LancElem *n = head.getNext();

            while( n->getNext() != nullptr && n->getNext()->getKey() != key )
            {
                n = n->getNext();
            }

            if ( n->getNext() != nullptr )
            {
                LancElem *current = n->getNext();
                n->setNext( n->getNext()->getNext() );
                delete current;
            }                
        }
    }
}

Now try to use this function to delete the first node with the value 4 of your list and the function you currently have and compare their results.