Adjacency List Representation in DSA C

Mental Model

We store each node's neighbors in a list so we can quickly see who it connects to.

Analogy: Imagine a group of friends where each person keeps a list of their close friends' names written in a notebook.

0: 2 -> 1 -> null
1: 3 -> 0 -> null
2: 0 -> null
3: 1 -> null

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0-1, 0-2, 1-3

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge from 0 to 1

0: 1 -> null
1: null
2: null
3: null

Why: We record that node 0 connects to node 1

Step 2: Add edge from 1 to 0

0: 1 -> null
1: 0 -> null
2: null
3: null

Why: Since graph is undirected, node 1 connects back to node 0

Step 3: Add edge from 0 to 2

0: 2 -> 1 -> null
1: 0 -> null
2: null
3: null

Why: Node 0 also connects to node 2

Step 4: Add edge from 2 to 0

0: 2 -> 1 -> null
1: 0 -> null
2: 0 -> null
3: null

Why: Node 2 connects back to node 0

Step 5: Add edge from 1 to 3

0: 2 -> 1 -> null
1: 3 -> 0 -> null
2: 0 -> null
3: null

Why: Node 1 connects to node 3

Step 6: Add edge from 3 to 1

0: 2 -> 1 -> null
1: 3 -> 0 -> null
2: 0 -> null
3: 1 -> null

Why: Node 3 connects back to node 1

Result:

0: 2 -> 1 -> null
1: 3 -> 0 -> null
2: 0 -> null
3: 1 -> null

Annotated Code

DSA C

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

// Node for adjacency list
typedef struct Node {
    int dest;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int V;
    Node** array;
} Graph;

// Create new adjacency list node
Node* newNode(int dest) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

// Create graph with V vertices
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (Node**)malloc(V * sizeof(Node*));
    for (int i = 0; i < V; i++)
        graph->array[i] = NULL;
    return graph;
}

// Add edge to undirected graph
void addEdge(Graph* graph, int src, int dest) {
    // Add node to src list
    Node* node = newNode(dest);
    node->next = graph->array[src];
    graph->array[src] = node;

    // Add node to dest list
    node = newNode(src);
    node->next = graph->array[dest];
    graph->array[dest] = node;
}

// Print adjacency list
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        Node* pCrawl = graph->array[v];
        printf("%d: ", v);
        while (pCrawl) {
            printf("%d -> ", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("null\n");
    }
}

int main() {
    int V = 4;
    Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);

    printGraph(graph);
    return 0;
}

node->next = graph->array[src]; graph->array[src] = node;

Insert new neighbor at head of src adjacency list

node->next = graph->array[dest]; graph->array[dest] = node;

Insert new neighbor at head of dest adjacency list for undirected edge

while (pCrawl) { printf("%d -> ", pCrawl->dest); pCrawl = pCrawl->next; }

Traverse adjacency list to print all neighbors

Output

0: 2 -> 1 -> null

1: 3 -> 0 -> null

2: 0 -> null

3: 1 -> null

Complexity Analysis

Time: O(V + E) because we create and print adjacency lists for all vertices and edges

Space: O(V + E) because adjacency lists store all vertices and their edges

vs Alternative: Compared to adjacency matrix O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Graph with no edges

All adjacency lists remain empty (NULL)

DSA C

for (int i = 0; i < V; i++) graph->array[i] = NULL;

Graph with single vertex and no edges

Single adjacency list is empty

DSA C

for (int i = 0; i < V; i++) graph->array[i] = NULL;

When to Use This Pattern

When you need to represent graph connections efficiently and want to quickly find neighbors, use adjacency lists because they store only existing edges.

Common Mistakes

Mistake: Forgetting to add edges in both directions for undirected graphs
Fix: Add edge from src to dest and also from dest to src

Mistake: Appending new nodes at the end of adjacency list causing O(n) insertion
Fix: Insert new nodes at the head of the list for O(1) insertion

Summary

Stores graph edges as lists of neighbors for each vertex.

Use when you want efficient storage and quick access to neighbors in sparse graphs.

Each vertex keeps a simple list of its connected nodes, like a friend list.