What Is a Linked Representation?
In this method, the graph is stored using linked lists.
For each vertex, we create a separate linked list that stores the nodes that are directly connected to it.
So:
- One vertex = one linked list
- Each node in the list = one neighbor
- All lists together = your entire graph
It’s like a directory where each person has their own contact list.
✏️ Simple Example Graph
Let’s take this small undirected graph:
A ---- B
| |
C ---- DEdges: A–B, A–C, B–D, C–D
📘 Linked Representation (Adjacency List Diagram)
Here’s how the linked representation might look:
Vertex Linked List
------- -----------------------
A → B → C → NULL
B → A → D → NULL
C → A → D → NULL
D → B → C → NULLEach row shows a vertex and the list of vertices directly connected to it.
This is clean, simple, and space-efficient.
🧠 How It Works Internally
Inside memory, each vertex has a small structure like:
struct Node {
int vertex;
Node* next;
};For each vertex:
- We create a head pointer
- That pointer leads to a chain (linked list) of its neighbors
So the entire graph becomes a bunch of small linked lists connected side-by-side.
🎯 Why Is Linked Representation Useful?
✅ 1. Saves space
You only store existing edges.
No huge matrix filled with zeros.
✅ 2. Easy to add or remove edges
Just modify the linked list.
✅ 3. Perfect for sparse graphs
If your graph has very few edges, this method is ideal.
❌ One limitation
Finding if two nodes are connected takes longer compared to a matrix, because you must search through the list.
But for most practical cases, the space savings are worth it.
🌱 Explaining It Even More Simply
Imagine each vertex as a small “homepage.”
On this homepage, it lists only the links (edges) pointing to other pages (vertices).
This structure feels natural and tidy — just like a contact list or a friend list on a social app.
About the Author
