Why is there a memory error in this adjacency list?

Question

In the code, I create an adjacency list with an array and each element of the array makes a list with it's adjacent nodes.

To access the array I needed to use ints; however, my vertex names were strings, so I mapped each vertex name to an int counting up from 0. As you can see in the nextNode() function the when a new node is created the'next'node should always be null.

An example result of the adjacency list will look something like this

• inputVertices: a,b,c,d

• inputEdges: (a,b), (a,d), (b,c) (d,b)

• mapping: a<->0, b<->1, c<->2, d<->3

• adjacency list:

  arr elements| linked lists connected to elements

  • 0 |->b->d

  • 1 |->c

  • 2 |

  • 3 |->b

---

struct Node {
    string vert;
    int weight;
    Node *next;
};

struct List {
    struct Node *head;
};


class Graph {
    int vertices;
    int edges;
    struct List *vertexArray;
    int count = 0;
    map<string, int> vertList;

public:

Graph(int vertices) {
    this->vertices = vertices;
    vertexArray = new List[vertices];
    for (int i = 0; i < vertices; i++) {
        vertexArray[i].head = NULL;
    }
}

~Graph() {
    vertList.clear();
}

Node *nextNode(string vert) {
    Node *newNode = new Node;
    newNode->vert = vert;
    newNode->weight = 0;
    newNode->next = NULL;
    return newNode;
}

void addVertex(string vert) {
    vertList[vert] = count; //maps Vertex to an integer in the order the Vertex is added
    count++;
}

void addEdge(string head, string vert, int weight) {
    Node *newNode = nextNode(vert);
    newNode->weight = weight;
    newNode->next = vertexArray[vertList.at(head)].head;
    vertexArray[vertList.at(head)].head = newNode;
}

I stumbled upon my problem while trying to print my adjacency list here and the program always crashes in the while loop below. It gets through the first list of nodes fine, but crashes during the second list.

I figured out the reason is the first list points to everything fine array[0].head->next = node1 node1->next = node2...noden->next = null(this exits the loop), however for the second list something different happens: array[1].head->next = node1 node1->next = node2...noden->next = 0xabababab. The last node should be null, but it is not. I set all new nodes to null. This causes a seg fault and crashes the program.

void print() {
       for (int i = 0; i < vertices; i++) {
           Node *n = vertexArray[i].head;
           for (auto it = vertList.cbegin(); it != vertList.cend(); ++it) {
               if ((*it).second == i) { // true if second type in map (aka int) == current array position
                   cout << (*it).first; //corresponding first type in map
                   while (n) {
                          cout << "-> " << n->vert;
                         n = n->next;
                    }
                    cout << endl;
                }
           }

       }
 }