Adjacency List

Overview

An adjacency list provides a mechanism for representing a graph as a collection of unordered lists, one for each vertex in the graph. The main alternative to the adjacency list for graph representation is the adjacency matrix.

Concept

The adjacency list works by listing each vertex in the graph, followed by a collection of each of the edges that vertex is connected to.

Algorithmic Complexity

Big-O

Node/Edge ManagementStorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
Adjacency ListO(|V|+|E|)O(1)O(1)O(|V| + |E|)O(|E|)O(|V|)

Implementation

Java Implementation

This is an example Java program to implement an adjacency list data structure.  This program was compiled and successfully tested under Java version 1.8.

Coming soon!

References

Wikipedia: Adjacency list