Adjacency List Representation in DSA Typescript - Deep Dive

Overview - Adjacency List Representation

What is it?

An adjacency list is a way to represent a graph using a list where each item corresponds to a node and contains a list of its neighbors. It shows which nodes are connected directly to each node. This method is memory efficient for graphs with fewer connections. It helps us quickly find all nodes connected to a given node.

Why it matters

Without adjacency lists, storing and working with graphs would be slow and wasteful, especially when many nodes have few connections. This would make tasks like finding routes or connections in maps, social networks, or games much harder and slower. Adjacency lists make these operations faster and use less memory, improving performance in real applications.

Where it fits

Before learning adjacency lists, you should understand what graphs are and basic data structures like arrays and lists. After mastering adjacency lists, you can learn about graph algorithms like depth-first search, breadth-first search, and shortest path algorithms that use this representation.

Mental Model

Core Idea

An adjacency list represents a graph by storing each node with a list of its directly connected neighbors.

Think of it like...

Imagine a group of friends where each person keeps a list of their close friends. Instead of writing down every possible pair of friends, each person only notes who they directly hang out with.

Graph:
  A --- B
  |     |
  C --- D

Adjacency List:
  A: B -> C
  B: A -> D
  C: A -> D
  D: B -> C

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Introduce what a graph is and what nodes represent.

A graph is a collection of points called nodes or vertices. These nodes can be connected by lines called edges. For example, a map with cities (nodes) connected by roads (edges) is a graph.

Result

You know what nodes and edges are and can identify them in simple examples.

Understanding nodes and edges is essential because adjacency lists store connections between these nodes.

2

Foundation

Basic List and Array Structures

Concept: Learn how lists or arrays can store collections of items.

A list is a simple way to keep items in order. For example, a shopping list stores items you want to buy. Arrays are similar but have fixed size and fast access by position.

Result

You can create and use lists or arrays to hold multiple values.

Knowing lists and arrays helps you understand how adjacency lists store neighbors for each node.

3

Intermediate

Building an Adjacency List for Graphs

🤔Before reading on: do you think adjacency lists store all edges twice or just once? Commit to your answer.

Concept: Learn how to represent a graph by listing neighbors for each node.

For each node, create a list of nodes it connects to. For example, if node A connects to B and C, store B and C in A's list. For undirected graphs, connections go both ways, so B's list includes A too.

Result

You can write an adjacency list showing each node and its neighbors.

Knowing adjacency lists store neighbors per node helps you quickly find connections without scanning the whole graph.

4

Intermediate

Implementing Adjacency Lists in TypeScript

🤔Before reading on: do you think adjacency lists are best stored as arrays or objects in TypeScript? Commit to your answer.

Concept: Use TypeScript objects or arrays to store adjacency lists for graphs.

Use a Map or object where keys are node names and values are arrays of neighbors. Example: const graph: Record = { A: ['B', 'C'], B: ['A', 'D'], C: ['A', 'D'], D: ['B', 'C'] };

Result

You have a working adjacency list in TypeScript representing the graph.

Using objects or maps lets you access neighbors by node name quickly and clearly.

5

Intermediate

Handling Directed and Undirected Graphs

🤔Before reading on: do you think adjacency lists differ for directed vs undirected graphs? Commit to your answer.

Concept: Understand how adjacency lists change depending on edge direction.

In undirected graphs, edges go both ways, so each connection appears in both nodes' lists. In directed graphs, edges go one way, so only the start node lists the end node as neighbor.

Result

You can represent both directed and undirected graphs correctly with adjacency lists.

Knowing edge direction affects adjacency lists helps avoid mistakes in graph algorithms.

6

Advanced

Optimizing Adjacency Lists for Large Graphs

🤔Before reading on: do you think adjacency lists always use less memory than adjacency matrices? Commit to your answer.

Concept: Learn when adjacency lists save memory and how to optimize them for big graphs.

Adjacency lists use less memory when graphs are sparse (few edges). For very large graphs, use efficient data structures like typed arrays or linked lists to store neighbors. Avoid storing duplicate edges in undirected graphs.

Result

You understand memory benefits and can optimize adjacency lists for performance.

Knowing when and how to optimize adjacency lists prevents slow or memory-heavy graph operations.

7

Expert

Internal Mechanics and Edge Cases in Adjacency Lists

🤔Before reading on: do you think adjacency lists can represent weighted edges directly? Commit to your answer.

Concept: Explore how adjacency lists handle weights, self-loops, and disconnected nodes.

To store weights, adjacency lists can hold pairs like [neighbor, weight]. Self-loops appear as a node listing itself as neighbor. Disconnected nodes have empty neighbor lists. Handling these correctly is key for advanced algorithms.

Result

You can represent complex graphs with weights and special cases using adjacency lists.

Understanding these details helps build robust graph models and avoid subtle bugs.

Under the Hood

Adjacency lists work by storing, for each node, a list of references to its neighbors. Internally, this is often a hash map or array where keys are node identifiers and values are arrays or linked lists of neighbors. This allows quick access to neighbors without scanning unrelated nodes. Memory is allocated only for existing edges, making it efficient for sparse graphs.

Why designed this way?

Adjacency lists were designed to save memory and speed up neighbor lookups compared to adjacency matrices, which store all possible edges including non-existent ones. Early graph problems showed that many real-world graphs are sparse, so adjacency lists became the preferred structure. Alternatives like adjacency matrices were rejected for large sparse graphs due to high memory use.

Graph Nodes and Adjacency List Structure:

  +-------+       +----------------+
  | Node  | ----> | Neighbors List |
  +-------+       +----------------+
      |                 |
      |                 v
  +-------+       +-------+ +-------+
  |   A   |       |   B   | |   C   |
  +-------+       +-------+ +-------+

Each node points to a list of neighbors, enabling fast traversal.

Myth Busters - 4 Common Misconceptions

Quick: Does an adjacency list always store edges twice for undirected graphs? Commit yes or no.

Common Belief: Adjacency lists always store each edge twice, once for each node it connects.

Reality: While undirected graphs usually store edges twice, some implementations store each edge once with special handling to save space.

Why it matters: Assuming edges are always stored twice can lead to double counting in algorithms and inefficient memory use.

Quick: Can adjacency lists represent weighted edges directly? Commit yes or no.

Common Belief: Adjacency lists cannot store edge weights; they only show connections.

Reality: Adjacency lists can store weights by saving neighbor and weight pairs together.

Why it matters: Believing weights can't be stored limits the use of adjacency lists in weighted graph problems.

Quick: Is adjacency list always better than adjacency matrix? Commit yes or no.

Common Belief: Adjacency lists are always more efficient than adjacency matrices.

Reality: Adjacency matrices can be better for dense graphs or when constant-time edge checks are needed.

Why it matters: Choosing adjacency lists blindly can cause performance issues in dense graphs.

Quick: Does an empty neighbor list mean a node is disconnected? Commit yes or no.

Common Belief: If a node has an empty adjacency list, it is disconnected from the graph.

Reality: An empty list means no outgoing edges, but the node might still be reachable via incoming edges in directed graphs.

Why it matters: Misunderstanding this can cause incorrect assumptions about graph connectivity.

Expert Zone

1

Adjacency lists can be implemented with linked lists or dynamic arrays, each with tradeoffs in insertion and traversal speed.

2

In weighted graphs, storing weights alongside neighbors requires careful data structure choices to maintain performance.

3

Handling graph mutations (adding/removing edges) efficiently requires balancing adjacency list structure and update costs.

When NOT to use

Avoid adjacency lists for very dense graphs where most nodes connect to many others; adjacency matrices or edge lists may be better. For constant-time edge existence checks, adjacency matrices are preferable. For dynamic graphs with frequent edge insertions and deletions, specialized data structures like balanced trees might be more efficient.

Production Patterns

Adjacency lists are widely used in social network analysis to represent user connections, in routing algorithms for maps to store road networks, and in recommendation systems to model item relationships. They enable efficient traversal algorithms like BFS and DFS in real-world systems.

Connections

Adjacency Matrix Representation

Alternative graph representation with different tradeoffs

Understanding adjacency lists helps grasp why adjacency matrices use more memory but allow faster edge checks.

Hash Maps

Data structure used to implement adjacency lists efficiently

Knowing how hash maps work clarifies how adjacency lists provide quick neighbor lookups by node keys.

Social Networks

Real-world application domain of adjacency lists

Seeing adjacency lists as friend lists in social networks helps understand their practical use in modeling connections.

Common Pitfalls

#1 Confusing directed and undirected edges in adjacency lists.

Wrong approach:

const graph = { A: ['B'], B: [] }; // Missing B->A edge for undirected graph

Correct approach:

const graph = { A: ['B'], B: ['A'] }; // Both directions included

Root cause:

Not realizing undirected edges must be stored in both nodes' lists.

#2 Storing duplicate edges in adjacency lists.

Wrong approach:

const graph = { A: ['B', 'B'], B: ['A'] }; // Duplicate B in A's list

Correct approach:

const graph = { A: ['B'], B: ['A'] }; // No duplicates

Root cause:

Not checking for existing neighbors before adding edges.

#3 Using arrays for node keys instead of objects or maps.

Wrong approach:

const graph = [['A', ['B']], ['B', ['A']]]; // Hard to access neighbors by node

Correct approach:

const graph = { A: ['B'], B: ['A'] }; // Easy neighbor lookup by node name

Root cause:

Not choosing the right data structure for fast access.

Key Takeaways

Adjacency lists store each graph node with a list of its direct neighbors, making graph traversal efficient.

They are memory efficient for sparse graphs because they only store existing edges, not all possible connections.

Adjacency lists can represent both directed and undirected graphs by adjusting how edges are stored.

Implementing adjacency lists with objects or maps allows quick access to neighbors by node name.

Understanding adjacency lists is essential before learning graph algorithms like BFS and DFS.