Adjacency List

Adjacency list is a graph representation where each node stores a list of the nodes it is connected to.

For example:

A: B, C
B: A, D
C: A
D: B

This represents a graph where A is connected to B and C, and B is connected to D.

Adjacency lists are useful because they store sparse graphs efficiently. A sparse graph has relatively few edges compared with the maximum possible number of edges.

Common operations:

• Finding the neighbors of a node: usually O(degree of node)
• Checking whether a specific edge exists: often O(degree of node), unless a hash set is used
• Iterating over all edges: O(V + E)

Adjacency lists are commonly used for graph traversal algorithms such as breadth-first search and depth-first search.

flowchart LR
    A["A: B, C"] --> B["B: A, D"]
    A --> C["C: A"]
    B --> D["D: B"]

Anki

id: adjacency-list-definition deck: Computer Science::Data Structures tags: data-structures graph adjacency-list

Q: In a graph stored as an adjacency list, where do you look to find a node’s neighbors? A: Look up the node’s list of connected nodes.

id: adjacency-list-tradeoff deck: Computer Science::Data Structures tags: data-structures graph adjacency-list

Q: Why is an adjacency list a good fit for a social network with millions of users but only some friendships? A: It stores only the connections that actually exist, instead of reserving space for every possible pair of users.