List destructor in C++

Question

I've just implemented the Linked List. It works perfectly fine but even tough I've seen notation I am unable to create working destructor on Node, that's why it's unimplemented here in code.

1. I need to implement working destructor on node
2. Destructor of List but this one is simple I will just use the destructor from Node class(but I need this one).
3. Make the List friendly to Node so I will not have to use getNext(), but I think I can handle it myself(not sure how, but I'll find out).

Please look at the code it is perfectly fine, just will work if you copy it.

#include <cstdio>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Node {
public:
    Node(Node* next, int wrt) {
        this->next = next;
        this->wrt = wrt;
    }

    Node(const Node& obiekt) {
        this->wrt = obiekt.wrt;
        this->next = obiekt.next;
    }
    ~Node() {}

    void show() {
        cout << this->wrt << endl;
    }

    int getWrt(){
        return this->wrt;
    }

    Node* getNext(){
        return this->next;
    }

    void setNext(Node* node){
        this->next = node;
    }

 private:
    Node* next;
    int wrt;
};

class List{
public:
    List(int wrt){
        this->root = new Node(NULL, wrt);
    }

    List(const List& obiekt){
        memcpy(&this->root,&obiekt.root,sizeof(int));
        Node* el = obiekt.root->getNext();
        Node* curr = this->root;
        Node* next;
        while(el != NULL){
            memcpy(&next,&el,sizeof(int));
            curr->setNext(next);
            curr = next;
            next = curr->getNext();
            el = el->getNext();
    /*      curr->show();
            next->show();
            el->show(); */
        }
    }

    void add(int wrt){
        Node* node = new Node(NULL, wrt);
        Node* el = this->root;
        while(el->getNext() != NULL){
            //el->show();
            el = el->getNext();
        }
        el->setNext(node);
    }

    void remove(int index){
        Node* el = this->root;
        if(index == 0){
             //deleting old one
             this->root = this->root->getNext();
        }
        else{
            int i  = 0;
            while(el != NULL && i < index - 1){
            //  el->show();
                el = el->getNext();
                i++;
            }
            if(el!=NULL){
                Node* toRem = el->getNext();
                Node* newNext = toRem->getNext();
                el->setNext(newNext);
                //deleteing old one
            }
        }
    }

    void show(){
        Node* el = this->root;
        while(el != NULL){
            el->show();
            el = el->getNext();
        }
    }

    ~List(){}

private:
    Node* root;
};

int main(){
    List* l = new List(1); //first list
    l->add(2);
    l->add(3);
    l->show();
    cout << endl;

    List* lala = new List(*l); //lala is second list created by copy cosntructor
    lala->show();
    cout << endl;

    lala->add(4);
    lala->remove(0);
    lala->show();

    return 0;
}

Solution 1

I suggest you to start with implementing destructor of List. Since you dynamically allocated memory by using new, you should free it by using delete. (If you used new[], it would be delete[]):

~List()
{
    Node* currentNode = this->root; // initialize current node to root
    while (currentNode)
    {
        Node* nextNode = currentNode->getNext();    // get next node
        delete currentNode;                         // delete current
        currentNode = nextNode;                     // set current to "old" next
    }
}

Once you have proper destructor, you should try whether your copy constructor is correct:

List* lala = new List(*l);
delete l; // delete list that was used to create copy, shouldn't affect copy

you will find out that your copy constructor is wrong and also causes your application to crash. Why? Because purpose of copy constructor is to create a new object as a copy of an existing object. Your copy constructor just copies pointers assuming sizeof(Node*) equal to sizeof(int). It should look like this:

List(const List& list)
{
    // if empty list is being copied:
    if (!list.root)
    {
        this->root = NULL;
        return;
    }

    // create new root:
    this->root = new Node(NULL, list.root->getWrt());

    Node* list_currentNode = list.root;
    Node* this_currentNode = this->root;
    while (list_currentNode->getNext())
    {
        // create new successor:
        Node* newNode = new Node(NULL, list_currentNode->getNext()->getWrt());
        this_currentNode->setNext(newNode);
        this_currentNode = this_currentNode->getNext();
        list_currentNode = list_currentNode->getNext();
    }
}

Also your function remove is wrong since it "removes" reference to some Node but never frees memory where this Node resides. delete should be called in order to free this memory.

"I need to implement working destructor on node" - No, you don't. Node itself doesn't allocate any memory, thus it shouldn't free any memory. Node shouldn't be responsible for destruction of Node* next nor cleaning memory where it's stored. Don't implement destructor nor copy constructor of Node. You also want to read this: What is The Rule of Three?

"Make the List friendly to Node so I will not have to use getNext()" - You want to say within Node class, that class List is its friend:

class Node
{
    friend class List; // <-- that's it

Note that from these 5 headers that you include your code requires only one: <iostream>. Also note that writing using namespace std; at the beginning of the file is considered bad practice since it may cause names of some of your types become ambiguous. Use it wisely within small scopes or use std:: prefix instead.

Solution 2

The linked list destructor will be called either when delete is used with a previously allocated pointer to a linked list or when a linked list variable goes out of scope (e.g., a local variable is destroyed when returning from a function).

The destructor for the linked list should be responsible to free the memory you previously reserved for the nodes (i.e., using add operation). So, basically, you need to traverse the list of nodes and apply the delete operation on each one of them. There is a little trick: when you are about to delete a node you must be careful not to lose the pointer to the next element (when a node is deleted you cannot be sure that next member will still be valid).

Comments

[betabandido]

Actually, it would be just better to define Node as an inner private struct in List. Then you can avoid using friend.

[Yoda]

I really thank You for sharing that knowledge with me. By the way you've presented it to me I assume that you probably would be a good teatcher(academic). Great.

[LihO]

@RobertKilar: I'm glad it helped you :)

[jbcoe]

I think this will cause a stack overflow for a big enough list due to the recursive destructor calls.