Why do I need double pointers?

Question

I don't understand why I need double pointers inside 'struct graph'. Is it because it allows me to access one of the nodes that I made inside the function makeGraph()?

If I use one pointer (struct node *adjList) then I can't set the nodes to NULL that I made inside makeGraph().

I got the code frome programiz.com and in the article that explains this code it says: Don't let the struct node** adjList overwhelm you. All we are saying is we want to store a pointer to struct node*. This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

If I do: graph->adjList[1] does it go to the address of the second node or goes it inside the node? (I'm talking about the nodes that I create inside makeGraph())

I understand the rest of the code. If anyone can help me it would be appreciated.

#include <stdlib.h>
#include <stdio.h>

struct node
{
    int vertex;
    struct node *next;
};

struct graph
{
    int numVertices;
    struct node **adjList; // <--- THIS ONE
};

struct graph *makeGraph(int vertices) // Creating a Graph
{
    struct graph *graph = malloc(sizeof(struct graph));
    graph->numVertices = vertices;
    graph->adjList = malloc(sizeof(struct node) * vertices); // creating the nodes

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL; // Setting all nodes to NULL

    return graph;
}

void addEdge(struct graph *graph, int src, int dest) // Add Edge
{
        struct node *newNode = makeNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        struct node *newNode2 = makeNode(src);
        newNode2->next = graph->adjList[dest];
        graph->adjList[dest] = newNode2;
        return;

int main()
{
    struct graph *graph1 = makeGraph(4);
    addEdge(graph1, 0, 1);
    addEdge(graph1, 0, 2);
    addEdge(graph1, 0, 3);
}

Answer 1

An adjacency list is being represented as a linked list of struct node. The list is accessed by a pointer to the first element of the list. (The pointer will be NULL when the list is empty.) The pointer has type struct node *.

The graph has a number of vertices as set in the numVertices member of struct graph. Each vertex needs an adjacency list, and each adjacency list needs a struct node *. So the graph needs an array of struct node * of length numVertices. The authors of the code chose to allocate the array dynamically as a separate memory block pointed to by the adjList member. The type of the adjList member is a pointer to the element type. The element type is struct node * so the type of the adjList member is struct node **.

---

There is another way to allocate the memory for the struct graph and its adjacency list. They could be allocated as single block by changing the adjList member to be a flexible array member, as shown below:

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>

struct node
{
    int vertex;
    struct node *next;
};

struct graph
{
    int numVertices;
    struct node *adjList[]; // <--- FLEXIBLE ARRAY MEMBER
};

struct graph *makeGraph(int vertices) // Creating a Graph
{
    struct graph *graph = malloc(offsetof(struct graph, adjList[vertices]));
    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL; // Setting all nodes to NULL

    return graph;
}

offsetof(struct graph, adjList[vertices]) is the offset in bytes from the address of a struct graph to the address of the adjList[vertices] array member element. Allocating a block of memory of that size is just large enough to hold a struct graph plus the array of pointers. Another way to specify the size is sizeof(struct graph) + vertices * sizeof(struct node *) or alternatively sizeof(struct graph) + vertices * sizeof(graph->adjList[0]), but I think using the offsetof macro is a more succinct way to specify the size.