In this tutorial, you will learn what an adjacency list is. Also, you will find working examples of adjacency list in C, C++, Java and Python.

An adjacency list represents a graph as an array of linked lists.

The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

A graph and its equivalent adjacency list representation are shown below.

An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.

The simplest adjacency list needs a node data structure to store a vertex and a graph data structure to organize the nodes.

We stay close to the basic definition of a graph - a collection of vertices and edges `{V, E}`. For simplicity, we use an unlabeled graph as opposed to a labeled one i.e. the vertices are identified by their indices 0,1,2,3.

Let's dig into the data structures at play here.

``````struct node
{
int vertex;
struct node* next;
};

struct Graph
{
int numVertices;
};``````

Don't let the `struct node** adjLists` overwhelm you.

All we are saying is we want to store a pointer to `struct node*`. This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

It is the same structure but by using the in-built list STL data structures of C++, we make the structure a bit cleaner. We are also able to abstract the details of the implementation.

``````class Graph
{
int numVertices;

public:
Graph(int V);
};``````

We use Java Collections to store the Array of Linked Lists.

``````class Graph
{
private int numVertices;
}``````

The type of LinkedList is determined by what data you want to store in it. For a labeled graph, you could store a dictionary instead of an Integer

There is a reason Python gets so much love. A simple dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you want.

``````graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}``````

Python, Java and C/C++ Examples

``````# Adjascency List representation in Python

def __init__(self, value):
self.vertex = value
self.next = None

class Graph:
def __init__(self, num):
self.V = num
self.graph = [None] * self.V

node.next = self.graph[s]
self.graph[s] = node

node.next = self.graph[d]
self.graph[d] = node

# Print the graph
def print_agraph(self):
for i in range(self.V):
print("Vertex " + str(i) + ":", end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")

if __name__ == "__main__":
V = 5

# Create graph and edges
graph = Graph(V)

graph.print_agraph()``````
``````// Adjascency List representation in Java

import java.util.*;

class Graph {

static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) {
}

public static void main(String[] args) {

// Create the graph
int V = 5;
ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V);

for (int i = 0; i < V; i++)

printGraph(am);
}

// Print the graph
static void printGraph(ArrayList<ArrayList<Integer>> am) {
for (int i = 0; i < am.size(); i++) {
System.out.println("\nVertex " + i + ":");
for (int j = 0; j < am.get(i).size(); j++) {
System.out.print(" -> " + am.get(i).get(j));
}
System.out.println();
}
}
}``````
``````// Adjascency List representation in C

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

struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);

struct Graph {
int numVertices;
};

// 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* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));

int i;
for (i = 0; i < vertices; i++)

return graph;
}

void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);

// Add edge from d to s
newNode = createNode(s);
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

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

printGraph(graph);

return 0;
}``````
``````// Adjascency List representation in C++

#include <bits/stdc++.h>
using namespace std;

}

// Print the graph
void printGraph(vector<int> adj[], int V) {
for (int d = 0; d < V; ++d) {
cout << "\n Vertex "
<< d << ":";
cout << "-> " << x;
printf("\n");
}
}

int main() {
int V = 5;

// Create a graph