Adjacency List vs Matrix When to Choose Which in DSA C - Trade-offs & Analysis

Mental Model

Graphs can be stored in two main ways: adjacency lists store neighbors for each node, adjacency matrices store connections in a grid.

Analogy: Think of a city map: adjacency list is like a list of roads from each city to others, adjacency matrix is like a big table showing if two cities are connected directly.

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

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Dry Run Walkthrough

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

Goal: Show how adjacency list and matrix represent the graph and when each is better

Step 1: Create adjacency list for each node showing neighbors

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

Why: Lists show only connected nodes, saving space for sparse graphs

Step 2: Create adjacency matrix grid marking edges with 1

   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Why: Matrix shows all possible connections, easy to check if two nodes connect

Step 3: Check if node 0 connects to node 3 using list and matrix

List: 0's neighbors are 2 and 1, no 3
Matrix: cell[0][3] = 0 means no connection

Why: Both structures confirm no direct edge between 0 and 3

Step 4: Add edge 2-3 and update both structures

List:
2: 3 -> 0 -> null
3: 2 -> 1 -> null
Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

Why: Shows how adjacency list adds neighbors and matrix updates grid

Result:

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

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

Annotated Code

DSA C

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

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

// Graph with adjacency list
typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int** adjMatrix;
} Graph;

// Create node for list
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

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

    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->adjMatrix = malloc(vertices * sizeof(int*));

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

// Add edge to adjacency list and matrix
void addEdge(Graph* graph, int src, int dest) {
    // Add to list src->dest
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add to list dest->src (undirected)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;

    // Update matrix
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;
}

// Print adjacency list
void printAdjList(Graph* graph) {
    printf("Adjacency List:\n");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d: ", i);
        Node* temp = graph->adjLists[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("null\n");
    }
}

// Print adjacency matrix
void printAdjMatrix(Graph* graph) {
    printf("Adjacency Matrix:\n   ");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", i);
    }
    printf("\n");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d [", i);
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d", graph->adjMatrix[i][j]);
            if (j < graph->numVertices - 1) printf(" ");
        }
        printf("]\n");
    }
}

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

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

    printAdjList(graph);
    printAdjMatrix(graph);

    // Add edge 2-3
    addEdge(graph, 2, 3);

    printf("\nAfter adding edge 2-3:\n");
    printAdjList(graph);
    printAdjMatrix(graph);

    return 0;
}

newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode;

insert new neighbor at head of adjacency list for src

newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode;

insert new neighbor at head of adjacency list for dest (undirected)

graph->adjMatrix[src][dest] = 1; graph->adjMatrix[dest][src] = 1;

mark edge in adjacency matrix for both directions

Output

Adjacency List:

0: 2 -> 1 -> null

1: 3 -> 0 -> null

2: 0 -> null

3: 1 -> null

Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 0]

3 [0 1 0 0]



After adding edge 2-3:

Adjacency List:

0: 2 -> 1 -> null

1: 3 -> 0 -> null

2: 3 -> 0 -> null

3: 2 -> 1 -> null

Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 1]

3 [0 1 1 0]

Complexity Analysis

Time: O(V + E) to build adjacency list because we add neighbors only; O(V^2) for adjacency matrix because we fill a grid for all pairs

Space: O(V + E) for adjacency list as it stores only edges; O(V^2) for adjacency matrix as it stores all possible edges

vs Alternative: Adjacency list is better for sparse graphs with fewer edges; adjacency matrix is better for dense graphs or quick edge checks

Edge Cases

Empty graph with zero edges

Adjacency list arrays are empty; adjacency matrix is all zeros

DSA C

for (int j = 0; j < vertices; j++) { graph->adjMatrix[i][j] = 0; }

Graph with one node and no edges

Adjacency list has one empty list; matrix is 0 at [0][0]

DSA C

graph->adjLists[i] = NULL;

Adding duplicate edges

Duplicates appear in adjacency list and matrix remains 1; no check to prevent duplicates

DSA C

No explicit guard; duplicates allowed

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, think about adjacency list for saving space with few edges and adjacency matrix for fast edge lookup in dense graphs.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list to store only existing edges and save space

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

Summary

Stores graph connections either as lists of neighbors or a full grid of edges.

Use adjacency list for sparse graphs and adjacency matrix for dense graphs or quick edge checks.

Adjacency list saves space by storing only existing edges; adjacency matrix uses a grid for constant-time edge lookup.