Adjacency List for Directed Graphs

Space: O(V + E)Add Edge: O(1)Dynamic Size

📋Understanding Adjacency Lists

An adjacency list is a collection of lists used to represent a graph. Each vertex has a list containing all vertices it is connected to. This representation is particularly efficient for sparse graphs where the number of edges is much smaller than the maximum possible number of edges.

The key advantage is that it only stores existing edges, making it space-efficient for graphs with few connections relative to the total number of possible edges.

Space Usage: O(V + E) instead of O(V²) for adjacency matrix

💻Implementation

// Adjacency List for Directed/Undirected Graph
class Graph {
  constructor(numVertices, isDirected = true) {
    this.numVertices = numVertices;
    this.isDirected = isDirected;
    this.adjList = {};
    
    // Initialize adjacency list
    for (let i = 0; i < numVertices; i++) {
      this.adjList[i] = [];
    }
  }
  
  // Add an edge between vertices
  addEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      
      // Add edge from vertex1 to vertex2
      if (!this.adjList[vertex1].includes(vertex2)) {
        this.adjList[vertex1].push(vertex2);
      }
      
      // For undirected graphs, add reverse edge
      if (!this.isDirected && vertex1 !== vertex2) {
        if (!this.adjList[vertex2].includes(vertex1)) {
          this.adjList[vertex2].push(vertex1);
        }
      }
    }
  }
  
  // Remove an edge between vertices
  removeEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      
      // Remove edge from vertex1 to vertex2
      this.adjList[vertex1] = this.adjList[vertex1].filter(v => v !== vertex2);
      
      // For undirected graphs, remove reverse edge
      if (!this.isDirected && vertex1 !== vertex2) {
        this.adjList[vertex2] = this.adjList[vertex2].filter(v => v !== vertex1);
      }
    }
  }
  
  // Check if edge exists
  hasEdge(vertex1, vertex2) {
    if (vertex1 >= 0 && vertex1 < this.numVertices && 
        vertex2 >= 0 && vertex2 < this.numVertices) {
      return this.adjList[vertex1].includes(vertex2);
    }
    return false;
  }
  
  // Get all neighbors of a vertex
  getNeighbors(vertex) {
    return this.adjList[vertex] || [];
  }
  
  // Get degree of a vertex
  getDegree(vertex) {
    return this.getNeighbors(vertex).length;
  }
  
  // Create from edge list
  static fromEdgeList(numVertices, edges, isDirected = true) {
    let graph = new Graph(numVertices, isDirected);
    edges.forEach(([vertex1, vertex2]) => {
      graph.addEdge(vertex1, vertex2);
    });
    return graph;
  }
  
  // Display adjacency list
  printAdjList() {
    console.log(`Adjacency List (${this.isDirected ? 'Directed' : 'Undirected'}):`);
    for (let vertex in this.adjList) {
      console.log(`${vertex}: [${this.adjList[vertex].join(', ')}]`);
    }
  }
}

// Example usage
let directedGraph = new Graph(5, true);
directedGraph.addEdge(0, 1);
directedGraph.addEdge(0, 2);
directedGraph.addEdge(1, 3);
directedGraph.printAdjList();

let undirectedGraph = new Graph(5, false);
undirectedGraph.addEdge(0, 1);
undirectedGraph.addEdge(0, 2);
undirectedGraph.addEdge(1, 3);
undirectedGraph.printAdjList();

📊Performance Analysis

Time Complexity

• Add Edge: O(1)
• Remove Edge: O(degree)
• Check Edge: O(degree)
• Get Neighbors: O(1)

Space Complexity

• Total Space: O(V + E)
• Per Vertex: O(degree)
• Sparse Graphs: Much better than O(V²)
• Dynamic: Grows with actual edges

✅ Advantages

• Space efficient: Only stores existing edges
• Fast neighbor iteration: Direct access to adjacency list
• Dynamic size: Adapts to actual graph density
• Memory locality: Better cache performance for sparse graphs
• Easy to add vertices: Just add new list

⚠️ Disadvantages

• Slower edge queries: O(degree) vs O(1) for matrix
• Complex deletion: Need to search through lists
• No direct indexing: Can't directly access edge weights
• Memory fragmentation: Dynamic allocation overhead
• Dense graphs: May use more space than matrix

🎯Best Use Cases

Sparse Graphs

When edges << V², adjacency lists save significant space

Graph Traversal

DFS, BFS benefit from fast neighbor iteration

Dynamic Graphs

When vertices/edges are frequently added/removed