Difference Between Adjacency Matrix and Adjacency List
💡 Concept Name
Adjacency Matrix vs. Adjacency List – These are two main ways to represent graphs. One uses a grid-like matrix for all possible connections; the other stores only actual connections for each node.
📘 Quick Intro
Whenever you work with graphs, you have to decide how to store the edges. An adjacency matrix uses a two-dimensional array to keep track of every possible link, while an adjacency list keeps a simple list for each node’s neighbors. The best choice depends on the graph’s size and how it’s used.
🧠 Analogy / Short Story
Picture a class register: an adjacency matrix is like having a giant chart where you check a box for every possible pair of classmates who are friends—even if most aren’t! An adjacency list is more like each student jotting down only their actual friends in a notebook. The first wastes space but is easy to search; the second saves space and feels more natural when there aren’t many connections.
🔧 Technical Explanation
-
Adjacency Matrix:
- Represents the graph as a V x V 2D array (V = number of vertices)
- Every cell [i][j] holds 1 (or weight) if there’s an edge from i to j, else 0
- Space complexity: O(V²) — not efficient for large, sparse graphs
- Edge lookup is instant (O(1)), but finding all neighbors takes O(V)
-
Adjacency List:
- Stores a list of neighbors for each vertex (using lists, arrays, or maps)
- Space complexity: O(V + E) (E = number of edges), so much more compact for sparse graphs
- Finding a specific edge: O(degree of vertex)
- Iterating all neighbors is fast—no empty space scanned
- Matrix shines for dense graphs or frequent edge checks. Lists are best for most real-world, sparse graphs.
🎯 Purpose & Use Case
- ✅ Use adjacency matrix if you need to check edge existence constantly, or for small, dense graphs
- ✅ Use adjacency list for most applications, especially when your graph isn’t “fully connected”
- ✅ Most algorithms like BFS and DFS are simpler and faster on adjacency lists for large, real-world graphs
💻 Real Code Example
// Adjacency Matrix Example
int[,] adjMatrix = new int[4, 4];
adjMatrix[0, 1] = 1;
adjMatrix[1, 2] = 1;
adjMatrix[2, 3] = 1;
// Adjacency List Example
List<int>[] adjList = new List<int>[4];
for (int i = 0; i < 4; i++) adjList[i] = new List<int>();
adjList[0].Add(1);
adjList[1].Add(2);
adjList[2].Add(3);
❓ Interview Q&A
Q1: When does an adjacency matrix become inefficient?
A: When the graph is very large and most nodes are not connected—too much wasted space.
Q2: Which is easier to modify—matrix or list?
A: Adjacency list, especially when adding or removing edges.
Q3: What’s the main space advantage of adjacency list?
A: It only stores actual edges, not empty possibilities.
Q4: If you want to quickly check for an edge, which is best?
A: Adjacency matrix—checking [i][j] is instant.
Q5: Can you represent weighted graphs with both?
A: Yes—store weights instead of 1s in the matrix, or store (neighbor, weight) pairs in lists.
Q6: Why do most coding competitions prefer adjacency lists?
A: They save space and are faster for traversals in most typical problems.
Q7: How do you find all neighbors using a matrix?
A: Scan the entire row—can be slow for large graphs.
Q8: When is a matrix unavoidable?
A: For certain algorithms that need fast edge lookup, like Floyd-Warshall for all-pairs shortest path.
Q9: Can adjacency lists have duplicate edges?
A: No, unless you allow it by design (for multigraphs).
Q10: What’s a common mistake when implementing adjacency lists?
A: Forgetting to initialize each list—leads to null reference errors.
📝 MCQs
Q1. Which data structure uses O(V²) space?
- Adjacency List
- Adjacency Matrix
- Hash Map
- Stack
Q2. Which is best for sparse graphs?
- Adjacency List
- Adjacency Matrix
- Binary Heap
- Array
Q3. How do you check for edge between nodes in a matrix?
- Scan row
- Index lookup
- BFS
- Hash lookup
Q4. Which is faster for finding all neighbors?
- Adjacency List
- Adjacency Matrix
- Queue
- Stack
Q5. Which one can have many empty entries?
- Adjacency Matrix
- Adjacency List
- Set
- Tree
Q6. Space usage of adjacency list?
- O(V)
- O(E)
- O(V + E)
- O(V²)
Q7. Edge existence in adjacency list is?
- O(1)
- O(V)
- O(degree)
- O(V²)
Q8. What’s a drawback of adjacency matrix?
- Slow
- Uses lots of memory for sparse graphs
- Hard to code
- Limited to trees
Q9. Which is more natural for real-world networks?
- Adjacency Matrix
- Adjacency List
- Array
- Heap
Q10. Which structure is easier to expand dynamically?
- Adjacency Matrix
- Adjacency List
- Stack
- Tree
💡 Bonus Insight
If you’re building social networks, web crawlers, or any large real-world graph, adjacency lists keep your code scalable and fast. But when you need to know about every possible connection instantly—like dense graphs in circuit design—an adjacency matrix is a solid choice.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!