Skip to content
Back to Data StructuresAll lessons

Data Structures

Graph (Adjacency List)

Add a connection: O(1) · Visit every node and connection once (a full traversal): O(V + E), where V is the number of nodes and E is the number of connections.

The idea, in plain English

A graph is like a map of friendships. Each person is a dot, called a node. Each friendship is a line connecting two dots, called an edge. An 'adjacency list' is like a phone book. For every person, it lists their direct friends.

How it works

  1. 1Store the graph as a lookup. Each node maps to a list of its direct neighbors.
  2. 2Adding a connection means adding each node to the other's neighbor list.
  3. 3To explore from a starting point, visit a node, then visit its unvisited neighbors, and keep going. This process is called a traversal.

When you'd use it

Use a graph to model anything with connections, like social networks, road maps, recommendation systems, or which tasks must finish before others.

Common beginner mistakes

  • Remember a graph can have cycles. A traversal must track which nodes it already visited, or it can loop forever.
  • Don't mix up directed and undirected connections. In an undirected friendship graph, adding one edge must update both people's neighbor lists.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Visit order: Amy -> Bo -> Cy -> Dee
Amy's friends: Bo, Cy

See it in motion

Build the graphAdjacency listAdd a connection: O(1) · Visit every node and connection once (a full traversal): O(V + E), where V is the number of nodes and E is the number of connections.
ABCD
adjacency
A[ ]
B[ ]
C[ ]
D[ ]

4 nodes, no connections yet. Each node's neighbour list starts empty.

4
Nodes
0
Connections
1/10
Step
0.0s
Time
Adding connectionNeighbour listExisting edgeIdle node

Not sure this is the right topic? See the learning paths → or where this leads →