Skip to main content
Definition Website Computer and Technology

Adjacency List

Subject: Computer and Technology noun /əˈdʒeɪ.sən.si lɪst/ 1 definition

  1. Definition (noun)

    Entry #48 · Updated

    An Adjacency List is a fundamental graph data structure that represents a finite graph by associating each vertex with a collection of its directly connected neighbors (or outgoing edges in a directed graph). Rather than allocating a two-dimensional matrix for every possible pair of vertices, it stores only the edges that exist, keeping memory usage proportional to the number of vertices plus edges, or O(V + E). This compact layout makes iterating over a vertex's neighbors and running graph traversals such as breadth-first search (BFS) and depth-first search (DFS) fast on sparse graphs, while trading off constant-time lookup when testing whether a specific edge connects two arbitrary vertices.

    Common Forms

    • Array of Dynamic Arrays or Linked Lists: Indexes vertices sequentially from 0 to V - 1 in an outer array, where each slot holds a contiguous dynamic array or linked list of neighboring vertex IDs.

    • Dictionary-of-Sets or Hash-Map Form: Maps arbitrary, non-contiguous vertex keys—such as strings or UUIDs—to hash sets or lists of neighbors, simplifying dynamic node insertion and accelerating edge-existence checks.

    • Weighted and Labeled Adjacency List: Stores tuples pairing each neighbor identifier with edge metadata—such as numeric weights, capacities, or relationship labels—to support shortest-path and network-flow computations.

    • Compressed Sparse Row (CSR) Representation: Packs all neighbor lists contiguously into a single flat edge array paired with a per-vertex offset array, minimizing pointer overhead and improving CPU cache locality for large static graphs.

    Example

    A navigation backend models a city road network of 500,000 intersections and 1.2 million one-way street segments as a weighted adjacency list, mapping each intersection ID to tuples of (destination_id, travel_seconds). When computing the fastest route with Dijkstra's algorithm, the router iterates only over the outgoing edges of each visited intersection rather than scanning hundreds of thousands of empty entries in a sparse matrix.