Adjacency List: Structure with Linked Lists
You'll learn how to represent graph edges using dynamically allocated linked lists for flexible, memory-efficient storage.
The Core Idea
An adjacency list represents a graph by maintaining a collection of linked lists—one per vertex. Each vertex has a pointer to a linked list containing all vertices it connects to. Unlike arrays (which require fixed size), linked lists grow and shrink dynamically as you add or remove edges, making them ideal for graphs where the number of edges per vertex varies significantly or changes over time.
Think of it like a contact list: each person (vertex) carries a chain of business cards (linked list nodes) for everyone they know. You can easily add a new card to someone's chain without reorganizing the entire system.
Structure Overview
Each vertex maintains a pointer to the head of a linked list. Each node in that list contains:
- The adjacent vertex ID (which vertex this edge connects to)
- A pointer to the next node in the list
- Optionally, edge weight (for weighted graphs)
For example, if vertex 0 connects to vertices 1, 2, and 4, vertex 0's linked list would be: 1 → 2 → 4 → NULL
Why Linked Lists?
Linked lists excel when:
- Edge counts are unpredictable or change frequently
- The graph is sparse (few edges relative to possible connections)
- You need true dynamic memory allocation without pre-allocating large arrays
The tradeoff? Slightly more memory overhead per edge (storing pointers) and less cache-friendly memory access compared to array-based adjacency lists.
Key Takeaway: Adjacency lists with linked lists offer maximum flexibility for dynamic graphs, trading pointer overhead for the ability to add/remove edges without reallocating or wasting space.