CODEWITHSUNDEEP
c++recursionlinked-list
umarqattan
umarqattan

Reputation: 509

Why isn't my remove node function working?

I've checked the boards and could not find any help with this. I find it easy to implement recursive functions given base and general cases, but this doesn't work the way I do it. I'm supposed to iterate down a list until I reach the tail of a linked list. If the next node is NULL, then I have to store the value at the last node, remove that node, and return the value. So it's similar to a dequeue method, except it's performed recursively. What am I doing wrong? 

int LinkedList::removeTailRec(Node *n)
{
    // check for the base case(s)
    if(n->next == NULL)
    {
        Node *tmp = new Node();
        tmp = n;
        int val = n->value;
        tmp = NULL;
        return val;
    }
    else
        return removeTailRec(n->next);

    // else call the recursive method
}

Upvotes: 3

Views: 408

Answers (4)

JBL
JBL

Reputation: 12907

First, I recommend you use nullptr instead of NULL.

Then, onto your code. You're actually not removing anything from your list.

if(n->next == NULL)
{
    Node *tmp = new Node();
                ^^^^^^^^^^
    //Useless, and dangerous. This memory is never free'd

    tmp = n;
    int val = n->value;
    tmp = NULL;
    ^^^^^^^^^^
    //You just set a local variable to NULL, you're not deleting anything

    return val;
}

If you want to remove the node, you'll have to keep a reference to the previous node (e.g. having a doubly linked list, that is, having a pointer to the next element and a pointer to the previous element in each node, or working on the previous node directly).

Set this previous node's next to nullptr, store the node's value and then delete the Node pointer.

One way to do this is to work with the pointer to the next node :

int LinkedList::removeTailRec(Node *n)
{
    //EDIT: Adding a check for n validity
    if(!n){
        //Here, you should have a way of detecting 
        //a call to your method with a null pointer
        return 0;
    }

    Node* nextNode = n->next;
    // check for the base case(s)
    if(nextNode->next == nullptr)
    {
        //Get the next node value
        int val = nextNode->value;

        //Set the current node next member to nullptr
        n->next = nullptr;

        //Free the last node
        delete nextNode;

        return val;
    }
    else{
        return removeTailRec(n->next);
    }

    // else call the recursive method
}

Upvotes: 5

Peter K
Peter K

Reputation: 1807

You are not removing last node in your code, and you leak another (temporary) node here. To remove last node you have to zero the link in the previous node. Your code should look like

...
if (n == NULL || n->next == NULL)
    throw std::out_of_range("node");
if(n->next->next == NULL)
{
    int val = n->next->value;
    delete n->next;
    n->next = NULL;
    return val;
}
else ...

Be aware of the fact that c++ is not a functional language and has no optimizations for tail recursion, so in real application as your lists grow big enough you'll eventually have failure with stack overflow =) use Haskell or Erlang for this style of programming, in c++ use for or while.

Upvotes: 1

Dineshkumar
Dineshkumar

Reputation: 4245

You are storing the result but not deleting it from linked list. You can return result in another variable (pointer : result).

Node* getTail(Node *n,int *result){
    //u can even free the memory
    if(!n->next)
    {
       result=n->value;
       return NULL;
    }
    n->next=getTail(n->next,result);
}

or you can do it other way

int getTail(Node *n)
{
    if(!n) return 0;
    if(n->next)
    {
        if(!n->next->next)
        {
            Node *frnode=n->next;
            int result=n->next->value;
            n->next=NULL;
            delete frnode;
            return result;
        }
     getTail(n->next);
}

Upvotes: 1

Xiaotian Pei
Xiaotian Pei

Reputation: 3260

You should set the Node n's previous Node's next field to NULL when n is the tail Node.

Upvotes: 0

Related Questions