Memory leaks in c++ program

Question

My problem is a memory leak somewhere in the code. I can't find it... I used valgrid and it gave information that memory leaks appers when im using method "add_connection". I thought that at the end of add_connection I should delete memory for newNode but then program crushes.

BTW. I can't use std::vector and stuff like this. Code must be really basic. Its requirement ;/

list_graph.h

#include <iostream>

struct Node{
int value;
int weight;
Node* next;
};


class List_graph
{
    static const int  MAX_SIZE =1000;
    Node* get_adj_list_node(int dest,Node * head,int weight);
    int Node_number=0;
public:

    Node** head;

    List_graph();
    ~List_graph();
    void add_connection(int source, int target, int weight);
};

list_graph.cpp

#include "../inc/list_graph.h"

Node*  List_graph::get_adj_list_node(int dest,Node * head,int weight)
{
    Node * new_node = new Node;
    new_node->value=dest;
    new_node->weight=weight;
    new_node->next = head;

    return new_node;
    delete [] new_node;
}


List_graph::List_graph()
{
    head = new Node *[MAX_SIZE]();
    for(int i =0; i<MAX_SIZE;i++)
    {
        head[i]=nullptr;
    }
}

List_graph::~List_graph()
{

    for(int i =0; i<MAX_SIZE;i++)
    {
      delete [] head[i];
    }
    delete [] head;
}

void List_graph::add_connection(int source, int target, int weight)
{
        Node* newNode = get_adj_list_node(target, head[source],weight);
        head[source] = newNode;
        Node_number++;
}

Answer 1

It looks like the problem is in this code:

void List_graph::add_connection(int source, int target, int weight)
{
        Node* newNode = get_adj_list_node(target, head[source],weight);
        head[source] = newNode;
        Node_number++;
}

Note if head[source] is already populated then you stomp that pointer, losing it forever, and leak allocations.

The fix is to delete it first:

void List_graph::add_connection(int source, int target, int weight)
{
        Node* newNode = get_adj_list_node(target, head[source],weight);
        delete head[source];
        head[source] = newNode;
        Node_number++;
}

Now in your other code:

Node*  List_graph::get_adj_list_node(int dest,Node * head,int weight)
{
    // ...
    return new_node;
    delete [] new_node;
}

The delete line never runs, and a good thing too because you'd sabotage the allocation you just made, and it's also the wrong type of delete to use.