Adjacency list
A linked list representation of graphs where each vertex maintains a list of adjacent vertices. Adjacency lists are space-efficient for sparse graphs. Traversals iterate through adjacency lists rather than entire matrices.
Formula
Space = O(V + E); Edge lookup = O(degree of vertex)
Real World
Facebook stores its 3 billion user friendships as adjacency lists — each user has a list of friends rather than a 3-billion-column table, saving enormous amounts of memory on sparse connections.
Exam Focus
When comparing with adjacency matrices, always reference space complexity and state which graph density each representation suits.
How well did you know this?