Adjacency List Representation in Data Structure

A graph is a collection of nodes (called vertices) connected by links (called edges), and representing it efficiently is key to solving real-world problems like navigation, networking, or social connections. They help model relationships between objects, like cities connected by roads, friends in a social network, or web pages linked to each other. But before we apply graph algorithms, we need an efficient way to represent a graph in memory.

There are two popular methods to store a graph:

• Adjacency Matrix
• Adjacency List

Here we will learn the Adjacency List Representation, a memory-efficient way to store graphs, especially when the number of edges is low compared to the number of vertices (i.e., sparse graphs).

What is an Adjacency List?

An Adjacency List is a collection of lists or arrays. Each list represents a vertex in the graph and contains all the vertices that are adjacent (i.e., directly connected) to it.

In Simple Words:

If there are V vertices, the adjacency list contains V entries.
Each entry i contains a list of all vertices connected to vertex i.

Understanding the Key Concepts of Adjacency List Representation

Term	Description
Vertex	Node or point in the graph
Edge	Connection between two vertices
Directed Graph	Edge from vertex A to vertex B is not the same as B to A
Undirected Graph	Edge between A and B connects both ways
Weighted Graph	Edge has a weight or cost

Example : Adjacency List for an Unweighted Undirected Graph

Consider the graph:

Vertices: 4
Edges: (0–1), (0–2), (1–2), (2–3)

Adjacency List Representation:

0 → 1 → 2  
1 → 0 → 2  
2 → 0 → 1 → 3  
3 → 2

• Each line shows a node and its adjacent nodes.
• This representation is memory efficient for sparse graphs.

Advantages and Disadvantages of Adjacency List

Advantages

Advantage	Description
Efficient Memory	Uses O(V + E) space (less than matrix for sparse graphs)
Faster Iteration	Easy to iterate through neighbors of a vertex
Flexible	Good for graphs with large number of vertices and fewer edges

Disadvantages

Disadvantage	Description
Edge Lookup Time	Checking if an edge exists takes O(V) time in worst case
More Complex to Implement	Especially for weighted graphs and deletion of edges
Less Cache Friendly	Unlike matrix, may cause cache misses in traversal

Adjacency List vs Adjacency Matrix

Feature	Adjacency List	Adjacency Matrix
Space Complexity	O(V + E)	O(V²)
Edge Lookup	O(degree of node)	O(1)
Suitable For	Sparse Graphs	Dense Graphs
Memory Efficient?	Yes	No
Easy to Implement?	Slightly Complex	Easy

Read Full Article here: Adjacency Matrix vs Adjacency List

C Program: Adjacency List Using Linked List

#include <stdio.h>
#include <stdlib.h>

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

struct Graph {
    int vertices;
    struct Node** adjList;
};

// Create a node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->vertices = vertices;

    graph->adjList = malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL;

    return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
    // Add dest to src's list
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    // Add src to dest’s list (undirected)
    newNode = createNode(src);
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

// Print graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->vertices; v++) {
        struct Node* temp = graph->adjList[v];
        printf("%d → ", v);
        while (temp) {
            printf("%d ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    int vertices = 4;
    struct Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    return 0;
}

Output

0 → 2 1 
1 → 2 0 
2 → 3 1 0 
3 → 2 

Java Program : Adjacency List

import java.util.*;

public class AdjacencyList {
    private int vertices;
    private LinkedList<Integer>[] adjList;

    AdjacencyList(int v) {
        vertices = v;
        adjList = new LinkedList[v];

        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList<>();
    }

    void addEdge(int src, int dest) {
        adjList[src].add(dest);  // For directed graph
        adjList[dest].add(src);  // For undirected graph
    }

    void printGraph() {
        for (int i = 0; i < vertices; ++i) {
            System.out.print(i + " → ");
            for (Integer node : adjList[i]) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyList g = new AdjacencyList(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);

        g.printGraph();
    }
}

Output

0 → 1 2 
1 → 0 2 
2 → 0 1 3 
3 → 2

Real-World Applications of Adjacency List

The adjacency list is widely used in many real-world systems where relationships or connections need to be stored efficiently. Here are some common and easy-to-understand examples:

1. 👥 Social Networks

• Use Case: Represent people and their friendships.
• How it works: Each person is a node, and if two people are friends or follow each other, there’s a connection (edge) between them.
• Example: Facebook or Instagram friend/follow relationships.

2. 🗺️ Navigation and Maps

• Use Case: Show how different places are connected.
• How it works: Each city/location is a node, and roads or paths between them are edges.
• Example: Google Maps uses similar structures to show and calculate routes.

3. 🌐 Web Crawlers

• Use Case: Track how websites link to each other.
• How it works: Each web page is a node, and hyperlinks are edges.
• Example: Search engines like Google use this to crawl and index websites.

4. 🌍 Computer Networks

• Use Case: Manage how devices are connected in a network.
• How it works: Devices (like routers or computers) are nodes, and cables or wireless connections are edges.
• Example: Internet routing and data transfer paths.

5. 🤖 Recommendation Systems

• Use Case: Suggest similar items or users.
• How it works: Items or users are nodes, and similar behaviors (like purchases or views) create edges.
• Example: Netflix recommending movies or Amazon showing related products.

❓ FAQs: Adjacency List Representation

Q1: Is Adjacency List better than Adjacency Matrix?

It depends:

• For sparse graphs, adjacency list is better (memory efficient).
• For dense graphs, adjacency matrix is faster for lookups.

Q2: Can we use adjacency list for weighted graphs?

Yes, we store pairs like (vertex, weight) in each list instead of just vertex.

Q3: What is the space complexity of adjacency list?

O(V + E), which is very efficient for large, sparse graphs.

Q4: Is it possible to represent a self-loop in adjacency list?

Yes, just add the node to its own list.

Example: For a self-loop on vertex 2 → 2 → 2

Summary

Feature	Adjacency List
What it is	List of neighbors for each vertex
Space Efficiency	O(V + E)
Lookup Time	Slower than matrix (O(degree))
Best Use Case	Sparse graphs
Real-World Use	Social networks, maps, routers

Final Words

The Adjacency List is one of the most efficient and scalable ways to represent a graph — especially when you’re dealing with sparse graphs where most possible connections are missing.

It allows better memory usage, easy traversal, and supports extensions like weighted or directed graphs. Whether you’re preparing for coding interviews or building network models in real applications, mastering the adjacency list is a must.