deleting even nodes from a doubly link list c++

Question

I'm trying to delete the nodes that are even in a doubly linked list by recursion. The problem is that it deletes the nodes but still show garbage in the deleted nodes space.

This is the output:

Here is the original list: 2 -> 2 -> 23 -> 2 -> 78 -> 5 -> 2

This list contains 7 number of items

The Number of even numbers is: 5

The number of even nodes removed was: 5

The resulting list is... 23 -> 5

***************After the even numbers are removed I get this back, Are you getting the same problem?***************************************

Now backwards: 5 -> 27303024 -> 27302960 -> 23 -> 27302928 -> 0

This list contains 2 number of items

The sum of all data is: 28

int removeEven(node*& head) {
    // double pointer to use the address of pointer head
    node ** deleteNode = &head;
    //if is the end of the list stop
    if(head==NULL)
        return 0;
    //if is even
    if((*deleteNode) -> data %2==0)
    {
        node * helper = *deleteNode;
        *deleteNode = helper -> next;
        delete helper;

        return 1+ removeEven(helper -> next);
    }   
    //but if is an odd number
    else if ((*deleteNode) -> data %2)
    {
        //traverse to the next node
        deleteNode = &(*deleteNode)->next;
        //calls itself so that we can start againg to check in the new node.
        return removeEven(head -> next);
    }
}

I was told that changing the function like this will help but Im getting a lot of errors please help

//Remove even numbers
node* recfunremoveEven(node *head,node *prevnode, int* count) //helper function for remove even nodes
{
    if(head==NULL)
        return NULL;
    if(head->data %2 == 0) //data is even
    {
        *count+=1;
        free(head);
        node* next = recfunremoveEven(head->next,head,&count); //recursive call
        if(prevnode)
        {
            prevnode->next = next;
            next->previous = prevnode;
        }
        return next;
    }
    return recfunremoveEven(head->next,&count);
}

int removeEven(node*& head)
{
    int count=0;
    recfunremoveEven(head,&count);
    return count;
}

When compiling I get the following errors:

g++ -g -std=c++11 -o proftest dlist.h dlist.cpp main.cpp supplied.o

dlist.cpp: In function ‘node* recfunremoveEven(node*, node*, int*)’:

dlist.cpp:30:53: error: cannot convert ‘int**’ to ‘int*’ for argument ‘3’ to ‘node* recfunremoveEven(node*, node*, int*)’ node* next = recfunremoveEven(head->next,head,&count); //recursive call ^

dlist.cpp:38:42: error: cannot convert ‘int**’ to ‘node*’ for argument ‘2’ to ‘node* recfunremoveEven(node*, node*, int*)’ return recfunremoveEven(head->next,&count); ^

dlist.cpp: In function ‘int removeEven(node*&)’: dlist.cpp:45:29: error: cannot convert ‘int*’ to ‘node*’ for argument ‘2’ to ‘node* recfunremoveEven(node*, node*, int*)’ recfunremoveEven(head,&count);

This is the .h file in case someone need to see it

//doubly linked list
#include <iostream>
#include <cstring>
#include <cctype>
#include <cstdlib>


struct node
{
    int data;
    node * previous;
    node * next;
};

/* These functions are already written and can be called to test out your code */
void build(node * & head);  //supplied
void display(node * head);  //supplied
void destroy(node * &head); //supplied
//Recursively compute and return the number of nodes that contain even number
//in the doubly linked list
int countEven(node *head);
//Recursively remove all the nodes that contain even number in the doubly linked list
//and return the number of nodes removed 
int removeEven(node*& head);

yes I have been working on it for a lot of hours because tomorrow its my test and I want to be able to understand why is not working and learn from my mistakes so that Im prepare for my upcoming test and exercises — josh Pradera
In your removeEven you do not touch previous pointer from Node which seems to be very suspicious... — PiotrNycz
would I be able to say for example in the case that the first node is even the set head->previous = head then move head and previous to the next node and set a temp pointer and delete the pointer but in the case that the even node is in the middle??? — josh Pradera
this is a past assignment Im here asking for help to learn no to do the assignment — josh Pradera
Make a drawing of your pointers, where they are now, and where you want them to be after the delete, then I think it will be quite clear what you should do. — thorsan

molbdnilo molbdnilo · Accepted Answer · 2016-06-09T11:11:44

After free(head), you're not allowed to dereference head, but you do.

You've also added some &s where you shouldn't (when recursing) and you left out a parameter on a couple of function calls.

But I think you're overcomplicating matters by passing around the "previous" node.

There are three cases to handle:

The list is empty,
The first node is odd,
The first node is even.

The first case is trivial.
The second and third are very similar:

Remove the even nodes recursively from the rest of the list.
Adjust the previous pointer of the result of that removal.
If head is even, delete it and increment the count.
Return either head (if it's odd) or the result of the recursion (if head was even).

I believe this should do it (beware - untested):

node* removeEvenWorker(node* head, int* count)
{
    // Case 1
    if (head == nullptr)
    {
        *count = 0;
        return head;
    }

    // Recurse
    node* rest = removeEvenWorker(head->next, count);

    // Cases 2 & 3: Set up the first node.
    if (head->data % 2 != 0)
    {
        // Keep 'head'; link the recursive result to it.
        if (rest != nullptr)
        {
            rest->previous = head;
        }
        head->next = rest;
        return head;
    }
    else
    {
        // Discard 'head'
        if (rest != nullptr)
        {
            rest->previous = nullptr;
        }
        free(head);
        *count += 1;
        return rest;
    }

}

And calling it:

int removeEven(node*& head)
{
    int count = 0;
    head = removeEvenWorker(head, &count);
    return count;
}

deleting even nodes from a doubly link list c++

1 Answers