Course contentsShow
← Computer Science
Lesson 673 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency List: Structure with Linked Lists

Implement adjacency lists using dynamically allocated linked lists for flexible edge storage.

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.