Object type Null pointers

[Lowenstein]

Hello, I am new here.

I've been having a very specific problem that I haven't found an answer to online. I am trying to implement an adjacency list for a graph so that I can practice BFS and DFS.

The way I have my code set up is that an array cell is a vertex that points to an adjacency endpoint (I called it an edge) which points to another endpoint etc. The final adjacency endpoint points to NULL; however, since I guess its an edge type, it tries to point to another NULL endpoint etc. This causes my lists to be crowded with Null pointers and causes the program to consume a ton of memory and time when trying to destruct said objects. Why are my Null pointers pointing to other Null pointers? Is there a way to fix this? Please let me know.

Here is my code:

////////////HEADER//////////////

#ifndef __Graph__graph__
#define __Graph__graph__

#include <stdio.h>


struct edge {
    size_t v;
    edge* next_edge;
};

struct vertex {
    size_t u;
    bool visited;
    edge* first_edge;
};

class adj_list {
    vertex* array;
    size_t sz;
    size_t lim;
public:
    adj_list();
    ~adj_list();
    void clear_vertex(size_t);
    void add_edge(size_t, size_t);
    void add_vertex();
    vertex* index(size_t u)
    {
        if(u>=sz) return NULL;
        else return &array[u];}
    size_t size() {return sz;}
    
};

#endif /* defined(__Graph__graph__) */


//////////SOURCE////////////////

#include "graph.h"

adj_list::adj_list() {
    lim=1000; sz=0;
    array=new vertex[lim];
}

void adj_list::clear_vertex(size_t v)
{
    if(array[v].first_edge==NULL) return;
    if(array[v].first_edge->next_edge==NULL) {
        delete array[v].first_edge;
        array[v].first_edge=NULL;
    }
    edge* temp1=array[v].first_edge;
    edge* temp2=array[v].first_edge->next_edge;
    array[v].first_edge=NULL;
    while(temp2->next_edge!=NULL) {
        temp1->next_edge=NULL;
        delete temp1;
        temp1=temp2;
        temp2=temp2->next_edge;
    }
    temp1->next_edge=NULL;
    delete temp1;
    temp2->next_edge=NULL;
    delete temp2;
    return;
}

adj_list::~adj_list() {
    size_t i=0;
    while(i!=sz) clear_vertex(i);
    delete[] array; array=NULL;
    return;
}


void adj_list::add_vertex() {
    vertex* nvert=new vertex;
    nvert->u=sz+1;
    nvert->first_edge=NULL;
    nvert->visited=false;
    array[nvert->u]=*nvert;
    sz++;
    return;
    
}

void adj_list::add_edge(size_t i, size_t j) {
    if(sz<i || sz<j) return;
    
    edge* npair=new edge;
    npair->v=j;
    
    if(array[i].first_edge==NULL) {
        
        npair->next_edge=NULL;
        array[i].first_edge=npair;
    }
    else {
        edge* temp=array[i].first_edge;
        if (npair->v<=temp->v) {
            npair->next_edge=temp;
            array[i].first_edge=npair;
            return;
        }
        while(temp->next_edge!=NULL && npair->v>=temp->next_edge->v) {
            temp=temp->next_edge;
        }
        if(temp->next_edge==NULL) {
            npair->next_edge=NULL;
            temp->next_edge=npair;
        }
        else {
            npair->next_edge=temp->next_edge;
            temp->next_edge=npair;
        }
    }
    return;
}

//////////MAIN//////////

#include <iostream>
#include "graph.h"

int main() {
    adj_list graph;
    graph.add_vertex();
    graph.add_vertex();
    graph.add_vertex();
    graph.add_edge(0,1);
    graph.add_edge(1,2);
    graph.add_edge(2,0);
    graph.add_edge(0,2);
    
    for(size_t i=0;i!=graph.size();i++) {
        if(i<graph.size()) {
            std::cout<<graph.index(i)->u<<': ';
            if(graph.index(i)->first_edge!=NULL) {
                edge* temp=graph.index(i)->first_edge;
                while(temp->next_edge!=NULL) {
                    std::cout<<temp->v<<',';
                    temp=temp->next_edge;
                    
                }
            }
            std::cout<<std::endl;
        }
    }
    
    
    return 0;
}

Thank you for your help.

[cire]

The final adjacency endpoint points to NULL; however, since I guess its an edge type, it tries to point to another NULL endpoint etc. This causes my lists to be crowded with Null pointers and causes the program to consume a ton of memory and time when trying to destruct said objects. Why are my Null pointers pointing to other Null pointers?

NULL is a pointer value which cannot be dereferenced, therefore a NULL pointer cannot, by definition, point to anything. Your NULL pointers are not pointing to other NULL pointers.

The actual problem: your code leaks memory and you delete things that are not allocated with new which results in undefined behavior.

Take

void adj_list::add_vertex() {
    vertex* nvert=new vertex;       // nvert points to a dynamically allocated vertex object.
    nvert->u=sz+1;      
    nvert->first_edge=NULL;
    nvert->visited=false;
    array[nvert->u]=*nvert;         // The contents of *nvert are copied to array[nvert->u]
    sz++;
    return;                         // The value contained by nvert is lost: memory leak.
}

for example.

Do you understand what's happening here with the comments I added?

[Lowenstein]

Yes, your comments make a lot of sense to me. I completely forgot that the assignment operator copies content over and does not directly assign the contents of *nvert to the array.

In terms of deleting objected not allocated with new, are you talking about this for example:

*vertex temp= new vertex; //has an initialized pointer to an edge type
delete temp->first_edge;

If so, how exactly do I delete the contents of this pointer?

Thank you for your help.

edit: currently, I'm thinking about turning the structs into classes so that I can dynamically allocate all initialized objects; however, this seems like a work around and I think it would be helpful to know how exactly one deletes memory that wasn't allocated with new.