How can I delete a linked list without memory leak?

Question

I'm trying to make a phone book, and I store my data in a linked list. However, when I try to delete it, I either get memory leak or some ugly exit status with some value from the memory. I guess this exit status signals some problems during the deletion of my list, because the program won't proceed to the next line.

I've tried messing with the destructors back and forth, but it seems I'm unable to solve this on my own.

I have three important classes. One for the Phonebook, one for a Contact, and one for a Data member of a Contact. The Data class is abstract, and has a few derived classes. Also I have a linked list struct which I use to store Contacts in the Phonebook, and to store Data in a Contact.

The linked list struct:

#include "Data.h"
class Contact; //to avoid an "undefined reference" error

struct ListMem{
    ListMem* next=NULL;
    Contact* cont=NULL;
    Data* dat=NULL;
}; //this class can't have a destructor that calls "delete cont",
//because of the order I declared my classes in

The Phonebook class:

#include "Contact.h"
#include "ListMem.h"

class Phonebook{
    size_t cont_num; //how many contacts are already stored
    ListMem* cont; //pointer to the first member of the linked list
public:
    Phonebook(const char* filename){ //reads the Phonebook from file
        std::ifstream is;
        is.open(filename);
        size_t pb_size;
        string line;
        ListMem* tmp;
        is>>pb_size; getline(is, line);
        cont_num=0;

        for(size_t i=0; i<pb_size; i++){
            getline(is, line);
            if(i==0){
                Contact* tmp_ct=new Contact(line);
                cont=add_cont(tmp_ct);
                tmp=cont;
            }
            else {
                Contact* tmp_ct=new Contact(line);
                tmp->next=add_cont(tmp_ct);
                tmp=tmp->next;
            }
        }
    }

    ListMem* add_cont(Contact* new_ct){ //adds a new contact
        ListMem* tmp=new ListMem;
        tmp->cont=new Contact(new_ct);
        cont_num++;
        return tmp;
    }

    ~Phonebook(){
        ListMem* tmp=cont;
        while(tmp!=NULL){
            ListMem* del=tmp;
            tmp=tmp->next;
            delete del->dat;
            delete del->cont;
            delete del;
        }
    }
};

The Contact class:

#include "Name.h"
#include "ListMem.h"

class Contact{
    size_t data_num; //number of data stored
    ListMem* data; //pointer to the first data member
public:
    Contact(string line){ //converts a "line" into a Contact
        ListMem* tmp;
        int dat_count=std::count(line.begin(), line.end(), ':');
        data_num=dat_count;
        string dat, tmp_dat, tmp_type;
        int pos_1=0, pos_2=line.find(';');

        for(int i=0;i<dat_count;i++){
            dat=line.substr(pos_1, pos_2-pos_1);
            tmp_type=dat.at(0);
            tmp_dat=dat.substr(2, dat.size()-2);
            pos_1+=dat.size()+1;
            pos_2=line.find(';', pos_1);
            if(i==0){
                data=add_data(tmp_type, tmp_dat);
                tmp=data;
            }
            else {
                tmp->next=add_data(tmp_type, tmp_dat);
                tmp=tmp->next;
            }
        }
    }

    ListMem* add_data(string type, string data){ //adds a new data member
            ListMem* tmp=new ListMem;
            if(type=="1") tmp->dat=new Name(data);
            //I have more, but it's irrelevant.
            data_num++;
            return tmp;
    }

    ~Contact(){
        ListMem* tmp=data;
        while(tmp!=NULL){
            ListMem* del=tmp;
            tmp=tmp->next;
            delete del->dat;
            delete del->cont;
            delete del;
        }
    }
};

The Data class:

class Data{
    string type;
public:
    Data(){}
    void set_type(string t) {type=t;}
    virtual ~Data(){}
};

One of the derived classes, the others look basically the same:

#include "Data.h"

class Name: public Data{
    string name;
public:
    Name(string n): name(n){ set_type("1");}
    ~Name(){}
};

And of course the main:

#include "Phonebook.h"

int main(){
    Phonebook* Test=new Phonebook("test.txt");
    delete Test;

    return 0;
}

In the 'test.txt' file, I have my test phone book:

3
1:test_name_1;
1:test_name_2;
1:test_name_3;

So when I run this code, I have memory leak, and I don't know why. I made the destructor run along the linked list and deallocate the dynamic memory, or at least that's what I thought.

I know I don't deallocate the Contacts the way I should, because I used a memory leaking checker tool, and a pattern repeats the same times the Contacts I have.

I used .cpp files, but I integrated the relevant parts here to save some space. Also I didn't put here the includes other than my project system.

I strongly suspect that the problem is with the destructors, either ~Phonebook(), ~Contact() or both. I put here the other parts because I've been told to post a version anyone can replicate without much trouble. I feel like there must be a stupid error and a simple solution, but I don't know what.

Can you guys help me out a bit?

Answer 1

Phonebook constructor parses the file, creates Contact object using new operator and pass it to add_cont(). Member function add_cont() creates a copy of Contact object passed as parameter again using new operator but never deletes origin. From my point of view within add_cont() 'new_ct' just could be assigned to 'tmp->cont'.

BTW a better approach would be to use available container classes like std::list, std::vector etc. and avoid raw pointers.