Adjacency Matrix vs Adjacency List: Differences & Examples

Data Structure / Graph Representation Chapter 51

Adjacency Matrix vs Adjacency List: Differences & Examples

Learn the difference between Adjacency Matrix and Adjacency List in Data Structure with easy examples, diagrams, C program, time complexity and space complexity.

Graph Representation Comparison Table C Program Interactive Example
Adjacency Matrix
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Adjacency List

When we learn Graph in Data Structure, we understand that a Graph contains vertices and edges. Vertices represent objects, while edges show connections between them.

But there is another important question: how do we store these connections inside computer memory?

For example, suppose five cities are connected by different roads. We know which cities are connected, but a computer needs a proper structure to store this information.

Two common methods are Adjacency Matrix and Adjacency List.

Both represent the same Graph, but they use memory differently. They also have different advantages when we need to check an edge or visit all neighbouring vertices.

Students often get confused about when to use a Matrix, when to use a List, and why their space complexities are different.

In this chapter, we will understand Adjacency Matrix vs Adjacency List in simple English with one common example, a detailed comparison, practical C programming and an interactive Graph Explorer.

Quick Answer: Adjacency Matrix vs Adjacency List

An Adjacency Matrix represents a Graph using a V × V two-dimensional array. It requires O(V²) space and allows direct edge checking in O(1) time.

An Adjacency List stores the neighbours of each vertex. It requires O(V+E) space and is generally more memory-efficient for sparse Graphs.

What Is the Difference Between Adjacency Matrix and Adjacency List?

Adjacency Matrix vs Adjacency List: Differences & Examples

The main difference is how graph connections are stored in memory.

Adjacency Matrix

An Adjacency Matrix stores connections using rows and columns.

Every vertex gets one row and one column in a two-dimensional array.

In a simple unweighted Graph, 1 means an edge exists and 0 means it does not.

Space: O(V²)

Adjacency List

An Adjacency List stores the neighbours of each vertex.

Instead of creating a complete square matrix, it records existing connections.

It can be implemented with linked lists or dynamic arrays.

Space: O(V+E)

Both methods are correct. The better choice depends on how many connections the Graph contains and what operations the program performs frequently.

One Graph Example for Both Representations

To compare both methods, we will use the same undirected Graph.

Let the five vertices be P, Q, R, S and T.

The connections are P–Q, P–R, Q–S, R–S and S–T.

Vertices: V = {P, Q, R, S, T} Edges: E = {PQ, PR, QS, RS, ST} Number of Vertices = 5 Number of Edges = 5
Original Undirected Graph

Five vertices and five edges. The same Graph will be stored using two different methods.

Neighbours of Every Vertex

Vertex Neighbours Degree
P Q, R 2
Q P, S 2
R P, S 2
S Q, R, T 3
T S 1

Now we will create the Adjacency Matrix and Adjacency List using these exact connections.

Adjacency Matrix in Data Structure with Example

An Adjacency Matrix is a two-dimensional array used to represent connections between Graph vertices.

Since our Graph contains five vertices, we need a 5 × 5 matrix.

Step 1: Create the Matrix

Make five rows and five columns. Label both using P, Q, R, S and T.

Step 2: Fill Every Cell with Zero

Initially, we assume there are no connections. Therefore, all matrix entries are zero.

Step 3: Add the Edges

Because the Graph is undirected, every edge updates two matrix positions.

For Edge P-Q: Matrix[P][Q] = 1 Matrix[Q][P] = 1 For Edge P-R: Matrix[P][R] = 1 Matrix[R][P] = 1 For Edge S-T: Matrix[S][T] = 1 Matrix[T][S] = 1

Final Adjacency Matrix

V P Q R S T
P 0 1 1 0 0
Q 1 0 0 1 0
R 1 0 0 1 0
S 0 1 1 0 1
T 0 0 0 1 0

How to Read the Matrix

Row P and column Q contain 1 because P and Q are connected.

Row P and column T contain 0 because there is no direct edge between P and T.

The matrix is symmetric because this is an undirected Graph.

Space Complexity of Adjacency Matrix

Number of Vertices = V Matrix Size = V × V Space Complexity = O(V²) For V = 5: 5 × 5 = 25 entries

Advantages of Adjacency Matrix

  • Easy to understand and implement using arrays.
  • Direct edge checking takes O(1) time.
  • Useful for dense Graphs.
  • Convenient for matrix-based Graph algorithms.

Disadvantages of Adjacency Matrix

  • Requires O(V²) memory.
  • Many cells remain zero in sparse Graphs.
  • Finding all neighbours requires scanning a complete row.

Adjacency List in Data Structure with Example

An Adjacency List stores the neighbours of each vertex.

We do not need to store a complete square matrix.

Instead, we keep a separate list of neighbours for each vertex.

Step 1: Create Vertex Entries

Create entries for P, Q, R, S and T.

Step 2: Add Neighbouring Vertices

P connects with Q and R. Therefore, Q and R are stored in P's list.

S connects with Q, R and T. Therefore, these three vertices appear in S's list.

Final Adjacency List

P → Q → R → NULL
Q → P → S → NULL
R → P → S → NULL
S → Q → R → T → NULL
T → S → NULL

How to Read the Adjacency List

The list of P contains Q and R because both are directly connected to P.

The list of T contains only S because T has one neighbour.

In an undirected Graph, each edge normally appears in both endpoints' adjacency lists.

Space Complexity of Adjacency List

Vertex List Heads = V Undirected Edge Entries = 2E Total Storage = O(V + E) For V = 5 and E = 5: Vertex Heads = 5 Neighbour Entries = 10

Advantages of Adjacency List

  • Memory-efficient for sparse Graphs.
  • Uses O(V+E) space.
  • Efficient for visiting neighbours.
  • Commonly used with BFS and DFS.

Disadvantages of Adjacency List

  • Checking one specific edge may require searching a list.
  • Linked-list implementations need pointers.
  • Implementation can be slightly more difficult for beginners.

Important: The order of neighbours in an Adjacency List can change depending on how the list is created. The Graph remains the same.

Difference Between Adjacency Matrix and Adjacency List in Data Structure

The following comparison is useful for university exams, coding interviews and practical programming.

Feature Adjacency Matrix Adjacency List
Definition Stores edges in a V × V matrix Stores neighbours of every vertex
Data Structure 2D Array Linked Lists or Dynamic Arrays
Space Complexity O(V²) O(V+E)
Edge Lookup O(1) O(deg(u)) using an unsorted simple neighbour list
Find All Neighbours O(V) O(deg(u))
Edge Insertion O(1) O(1) with head insertion if duplicates need not be checked
Edge Deletion O(1) Requires locating the edge in the list
Sparse Graph Often wastes space Usually efficient
Dense Graph Often suitable Can also be used, with entry overhead
BFS / DFS O(V²) O(V+E)
Implementation Usually simpler Needs neighbour management

Exam Shortcut: Matrix = Complete square storage and fast edge lookup. List = Store neighbours and save memory for sparse Graphs.

Sparse Graph vs Dense Graph: Which Representation Is Better?

What Is a Sparse Graph?

A Sparse Graph contains relatively few edges compared with the maximum possible number.

An Adjacency List is usually preferred because it stores actual connections.

What Is a Dense Graph?

A Dense Graph contains many possible edges.

An Adjacency Matrix can be convenient, especially when the program checks connections frequently.

Memory Storage Example

Suppose an undirected Graph contains 100 vertices and 120 edges.

Adjacency Matrix: 100 × 100 = 10,000 matrix cells Adjacency List: 100 vertex list heads 2 × 120 neighbour entries = 100 heads + 240 entries

The Adjacency Matrix reserves space for every possible pair of vertices.

The Adjacency List stores the actual connections plus one list head per vertex.

These counts describe storage entries, not exact bytes. Actual memory also depends on data types, pointers and implementation.

Choose Matrix When

The Graph is dense or frequent direct edge checks are needed.

Choose List When

The Graph is sparse or neighbour traversal is important.

Adjacency Matrix vs Adjacency List: Time and Space Complexity

The performance of a Graph representation depends on both storage and the operation being performed.

1. Space Complexity

Adjacency Matrix: Space = O(V²) Adjacency List: Space = O(V + E)

2. Checking Whether an Edge Exists

An Adjacency Matrix can directly inspect matrix[u][v].

Therefore, edge lookup takes O(1) time.

In a basic Adjacency List, we may need to search the neighbours of u.

For an unsorted simple undirected neighbour list, this takes O(deg(u)) time.

3. Finding All Neighbours

An Adjacency Matrix must scan the row corresponding to the selected vertex.

This takes O(V) time.

An Adjacency List directly contains the neighbouring vertices.

Visiting these entries takes O(deg(u)) time.

4. BFS and DFS Complexity

Breadth-First Search and Depth-First Search are common Graph traversal algorithms.

Using Adjacency Matrix: BFS = O(V²) DFS = O(V²) Using Adjacency List: BFS = O(V + E) DFS = O(V + E)

These bounds are for standard Graph traversal implementations.

Important: The best representation is not always the one using less memory. We must also consider which operations the application performs most often.

Adjacency Matrix and List for Directed and Weighted Graphs

Directed Graph Representation

In a Directed Graph, an edge has a direction.

If P → Q exists, it does not automatically mean Q → P exists.

In an Adjacency Matrix, only matrix[P][Q] is marked unless the reverse edge also exists.

In an Adjacency List, Q appears in P's outgoing neighbour list.

Weighted Graph Representation

In a Weighted Graph, each edge has a weight such as distance or cost.

A matrix may store weights instead of simple 1 values.

A list may store a pair containing the neighbouring vertex and edge weight.

Weighted Adjacency List Example: P → (Q, 5) → (R, 8) Meaning: Edge P-Q has weight 5 Edge P-R has weight 8

Remember: If zero-weight edges are valid, a weighted matrix should not use zero alone to mean an absent edge. A separate marker or presence matrix may be needed.

Adjacency Matrix and Adjacency List in C with Output

The following C program represents the same undirected Graph using both methods.

The Adjacency Matrix uses a two-dimensional array.

The Adjacency List uses dynamically allocated linked list nodes.

This makes it easier to compare how both structures actually store the Graph.

adjacency_comparison.c — Complete C Program
#include <stdio.h>
#include <stdlib.h>

#define V 5
#define E 5

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

/* Add an undirected edge */

int addUndirected(Node *head[], int u, int v) {

    Node *a = malloc(sizeof(*a));
    Node *b = malloc(sizeof(*b));

    if (a == NULL || b == NULL) {

        free(a);
        free(b);

        return 0;
    }

    a->vertex = v;
    a->next = head[u];
    head[u] = a;

    b->vertex = u;
    b->next = head[v];
    head[v] = b;

    return 1;
}

/* Release adjacency-list memory */

void freeGraph(Node *head[]) {

    for (int i = 0; i < V; i++) {

        Node *current = head[i];

        while (current != NULL) {

            Node *next = current->next;

            free(current);
            current = next;
        }

        head[i] = NULL;
    }
}

int main(void) {

    /* Edges: PQ, PR, QS, RS, ST */

    const int edges[E][2] = {
        {0,1},
        {0,2},
        {1,3},
        {2,3},
        {3,4}
    };

    int matrix[V][V] = {0};

    Node *head[V] = {NULL};

    /*
       Process in reverse order
       for readable neighbour lists.
    */

    for (int k = E - 1; k >= 0; k--) {

        int u = edges[k][0];
        int v = edges[k][1];

        matrix[u][v] = 1;
        matrix[v][u] = 1;

        if (!addUndirected(head, u, v)) {

            puts("Memory allocation failed.");

            freeGraph(head);

            return 1;
        }
    }

    puts("Adjacency Matrix:");

    printf("    P Q R S T\n");

    for (int i = 0; i < V; i++) {

        printf("%c : ", 'P' + i);

        for (int j = 0; j < V; j++) {

            printf(
                "%d%s",
                matrix[i][j],
                j == V-1 ? "\n" : " "
            );
        }
    }

    puts("\nAdjacency List:");

    for (int i = 0; i < V; i++) {

        printf("%c", 'P' + i);

        for (
            Node *cur = head[i];
            cur != NULL;
            cur = cur->next
        ) {

            printf(
                " -> %c",
                'P' + cur->vertex
            );
        }

        puts(" -> NULL");
    }

    freeGraph(head);

    return 0;
}

Output of C Program

Verified Program Output
Adjacency Matrix:
    P Q R S T
P : 0 1 1 0 0
Q : 1 0 0 1 0
R : 1 0 0 1 0
S : 0 1 1 0 1
T : 0 0 0 1 0

Adjacency List:
P -> Q -> R -> NULL
Q -> P -> S -> NULL
R -> P -> S -> NULL
S -> Q -> R -> T -> NULL
T -> S -> NULL

Explanation of the C Program

1. Define the Graph

The program defines five vertices and five edges.

2. Create the Adjacency Matrix

The matrix is initially filled with zeros.

When an edge is added, both symmetric positions become 1.

3. Create the Adjacency List

The Node structure contains a neighbour index and a pointer to the next node.

For every undirected edge, two list nodes are created.

4. Display Both Representations

The program prints the matrix first and then the adjacency lists.

5. Release Memory

Finally, the dynamically allocated list nodes are freed.

Program Verification: The program was compiled using GCC with the C11 standard. Its Matrix and List output matches the five-vertex example.

How to Run This C Program in VS Code

  1. Open VS Code with GCC installed.
  2. Create adjacency_comparison.c.
  3. Copy and paste the program.
  4. Open the integrated terminal.
  5. Compile using GCC.
  6. Run the executable.
Compile
gcc -std=c11 -Wall -Wextra adjacency_comparison.c -o adjacency_comparison
Run in Windows PowerShell
.\adjacency_comparison.exe

Interactive Adjacency Matrix vs Adjacency List Visualizer

Now let us understand the difference practically.

In the following interactive example, you can add or remove edges and watch both representations change automatically.

Graph Representation Studio

Select a Graph type and two vertices. Add or remove an edge to compare the Matrix and List.

Live Graph Diagram

Starting edges: PQ, PR, QS, RS, ST.

Adjacency Matrix

V P Q R S T
P 0 1 1 0 0
Q 1 0 0 1 0
R 1 0 0 1 0
S 0 1 1 0 1
T 0 0 0 1 0

Adjacency List

  • P→ Q → R
  • Q→ P → S
  • R→ P → S
  • S→ Q → R → T
  • T→ S
5 Vertices
5 Edges
25 Matrix Cells

Example Graph loaded. Both representations are ready.

Practice: Remove edge S–T and observe how T becomes isolated. Then add P–T. See how one new edge changes two entries of the undirected Matrix and both endpoints' adjacency lists.

Common Mistakes in Adjacency Matrix and Adjacency List

Common Mistake Correct Explanation
Using O(V+E) for Matrix Adjacency Matrix uses O(V²) space.
Using O(V²) for basic List Standard Adjacency List uses O(V+E) space.
Adding only one entry for an undirected edge Update both directions.
Ignoring isolated vertices They still have rows and list heads.
Assuming a List always gives O(1) edge lookup Basic unsorted lists may require searching neighbours.
Confusing Graph representation with traversal Representation stores the Graph; traversal visits its vertices.

Important Questions on Adjacency Matrix vs Adjacency List

These original exam-style questions are useful for BCA, MCA and Data Structure revision.

2 MARKS

1. Define Adjacency Matrix.

An Adjacency Matrix is a V × V array used to represent connections between Graph vertices.

2 MARKS

2. Define Adjacency List.

An Adjacency List stores the neighbours of each vertex using a list-based representation.

2 MARKS

3. Which Representation Is Better for Sparse Graphs?

Adjacency List is generally more memory-efficient for sparse Graphs.

5 MARKS

4. Differentiate Adjacency Matrix and Adjacency List.

Adjacency Matrix uses a V × V two-dimensional array and requires O(V²) memory.

Adjacency List stores only the neighbouring vertices along with the vertex list structure. It requires O(V+E) space.

Matrix edge lookup takes O(1) time, while a basic Adjacency List may require searching the neighbour list.

10 MARKS

5. Explain Both Graph Representations with Examples and Complexity.

A Graph can be stored using an Adjacency Matrix or an Adjacency List.

An Adjacency Matrix creates a square array with V rows and V columns. In an unweighted Graph, a value of 1 normally represents an existing edge.

An Adjacency List stores the neighbours of every vertex.

For example, if P connects with Q and R, the list for P contains Q and R.

An Adjacency Matrix requires O(V²) space and provides O(1) direct edge checking.

An Adjacency List requires O(V+E) space and allows efficient neighbour traversal.

Therefore, Matrix is useful for dense Graphs or frequent edge lookups, while List is commonly suitable for sparse Graphs.

Adjacency Matrix vs Adjacency List Practice Questions

Question 1: What Is the Matrix Size for 7 Vertices?

Show Solution

7 × 7 = 49 cells. Therefore, the matrix contains 49 entries.

Question 2: Which Representation Uses O(V+E) Space?

Show Answer

Adjacency List.

Question 3: What Happens If Edge S–T Is Removed?

Show Answer

T becomes isolated because it has no remaining neighbour.

Both representations must remove the S–T connection.

Question 4: Which Representation Checks an Edge in O(1)?

Show Answer

Adjacency Matrix, because matrix[u][v] can be accessed directly.

Question 5: Why Is an Adjacency List Useful for BFS?

Show Answer

It allows BFS to visit the actual neighbours of a vertex without scanning an entire matrix row.

FAQs About Adjacency Matrix and Adjacency List

What is the main difference between Adjacency Matrix and Adjacency List?

An Adjacency Matrix stores connections in a square array. An Adjacency List stores neighbours of each vertex.

Which representation uses less memory?

Adjacency List generally uses less memory for sparse Graphs. Actual memory depends on the implementation.

What is Adjacency Matrix space complexity?

O(V²).

What is Adjacency List space complexity?

O(V+E).

Which is better for a dense Graph?

An Adjacency Matrix is often convenient, especially when direct edge checking is common.

Can both represent directed Graphs?

Yes. Both Adjacency Matrix and Adjacency List can represent directed Graphs.

Which representation is commonly used in BFS and DFS?

Adjacency List is commonly used because it provides efficient access to neighbours.

Adjacency Matrix vs Adjacency List: Quick Revision Notes

ADJACENCY MATRIX Structure: 2D Array Space: O(V²) Edge Lookup: O(1) Find Neighbours: O(V) Best for: Dense Graphs ADJACENCY LIST Structure: Neighbour Lists Space: O(V+E) Basic Edge Lookup: O(deg(u)) Find Neighbours: O(deg(u)) Best for: Sparse Graphs GRAPH TRAVERSAL Matrix BFS/DFS: O(V²) List BFS/DFS: O(V+E)

Memory Trick: Matrix = More reserved cells, faster direct lookup. List = Stores neighbours, useful for sparse Graphs.

Conclusion

Adjacency Matrix and Adjacency List are two important methods used to store Graphs in Data Structure.

Both represent the same vertices and edges, but their storage methods are different.

An Adjacency Matrix offers fast direct edge lookup but requires O(V²) space.

An Adjacency List uses O(V+E) space and is generally better for sparse Graphs.

For university examinations, practise drawing both representations from the same Graph and remember their time and space complexities.

Chapter 51 — Completed

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources