I've seen this exact bug more times than I can count. You've spent an hour carefully defining your structs, you've allocated your memory, and you've written a loop to add all your edges. But when you go to print the graph, it's completely empty. No nodes, no edges—just a blank screen or a segmentation fault.

The Disappearing Edge

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = graph->adjLists[src]; 
    // The bug is right here. We've linked the new node to the list, 
    // but we haven't told the graph that this new node is now the head.
}

If you run this, the newNode is created and it correctly points to whatever was previously at the head of the list for that vertex. However, graph->adjLists[src] still points to the old head (or NULL). The new node just floats in memory, unreferenced, until the function returns and you've effectively leaked memory and lost your data.

Updating the Head Pointer

To fix this, you have to actually update the pointer stored in the array. You aren't just rearranging the chain; you're changing where the chain starts.

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    if (!newNode) return; // Always check your mallocs

    newNode->dest = dest;
    newNode->next = graph->adjLists[src]; 
    
    // The Fix: Update the array to point to the new head
    graph->adjLists[src] = newNode;
}

Now, the adjLists array correctly tracks the most recently added node for every vertex. By inserting at the head, we keep the addEdge operation at O(1) time complexity, which is why this is the preferred way to build the list.

Managing the Array of Lists

Remember that adjLists is a Node**. This is often where people trip up. It's a pointer to an array of pointers. When you initialize the graph, you need two distinct allocation steps: one for the array itself and one for each individual node you add later.

I usually recommend initializing the array to NULL immediately. If you leave it uninitialized, newNode->next = graph->adjLists[src] will assign a random garbage memory address to your first node's next pointer, and your program will crash the moment you try to traverse the list.

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(Node*));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

The Memory Cleanup Burden

C doesn't clean up after you. With adjacency lists, you can't just free(graph->adjLists). If you do, you've leaked every single Node you allocated. You have to iterate through every index of the array and free the entire linked list at that index before you can finally free the array and the graph struct itself.

It's tedious, but if you're building a long-running application—like a routing service or a game engine—this is the difference between a professional tool and a memory leak that crashes a server every six hours.

📋 Practical Task

Build a Small-World Social Connection Map

Your task is to implement a basic social network graph using adjacency lists. In this scenario, vertices represent users and edges represent "friendships" (undirected).

• Create a Graph structure and a Node structure as discussed in the lesson.
• Implement a createGraph function that initializes a graph with a specific number of users.
• Implement an addEdge function. Since friendships are mutual, ensure that adding an edge from User A to User B also adds an edge from User B to User A.
• Implement a printNetwork function that iterates through the adjacency lists and prints every user's friends in the format: User 0: 1 -> 2 -> NULL.
• Implement a freeNetwork function that correctly cleans up all allocated nodes and the graph structure to ensure zero memory leaks.

Test your implementation by creating a network of 5 users and adding the following friendships: (0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4).