Graphs

Graphs are an integral part of computer science. Mastering them is necessary to become an accomplished software developer. Here is the data structure analysis of graphs:

Node/Edge ManagementStorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
Adjacency ListO(|V|+|E|)O(1)O(1)O(|V| + |E|)O(|E|)O(|V|)
Incidence ListO(|V|+|E|)O(1)O(1)O(|E|)O(|E|)O(|E|)
Adjacency MatrixO(|V|^2)O(|V|^2)O(1)O(|V|^2)O(1)O(1)
Incidence MatrixO(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|E|)