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.
Q → P → S
R → P → S
S → Q → R
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.
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?

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.
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.
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
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
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
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.
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.
The Graph is dense or frequent direct edge checks are needed.
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
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.
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.
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.
#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
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
- Open VS Code with GCC installed.
- Create
adjacency_comparison.c. - Copy and paste the program.
- Open the integrated terminal.
- Compile using GCC.
- Run the executable.
gcc -std=c11 -Wall -Wextra adjacency_comparison.c -o adjacency_comparison
.\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.
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
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.
1. Define Adjacency Matrix.
An Adjacency Matrix is a V × V array used to represent connections between Graph vertices.
2. Define Adjacency List.
An Adjacency List stores the neighbours of each vertex using a list-based representation.
3. Which Representation Is Better for Sparse Graphs?
Adjacency List is generally more memory-efficient for sparse Graphs.
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.
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
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
