Linked Representation of a Graph

---

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 ---- D

Edges: 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 → NULL

Each 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.

---