Data Structures

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|)

Heaps

Storing information in a way that is quick to retrieve, add, and search on, is a very important technique to master. Here is what you need to know about heap data structures:

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Sorted Linked List-O(1)O(1)O(n)O(n)O(1)O(m+n)
Unsorted Linked List-O(n)O(n)O(1)O(1)O(1)O(1)
Binary HeapO(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)
Binomial Heap-O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))
Fibonacci Heap-O(1)O(log(n))*O(1)*O(1)O(log(n))*O(1)