Usually used to store graphs Each row/index/key corresponds to a vertex and it’s value is a list of all vertices directly connected (adjacent) to it.
If Node A connects to B and C, the list for A would contain (B, C)
Key characteristics
- Space Efficiency: Excellent for sparse graphs (few edges) because it doesn’t waste space storing non-existent connections, unlike an adjacency matrix.
- Time Complexity:
- Finding all neighbors of a vertex: Fast (proportional to the number of neighbors).
- Checking if an edge exists between two nodes: Can be slower (requires traversing the list).