Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Data Structures

Time complexity of the basic operations (from the Nov 2023 crash course):

Data structureInsert (avg)Delete (avg)Search (avg)Insert (worst)Delete (worst)Search (worst)
Array, stack, queue
Linked list
Doubly linked list
Hash table
Binary search tree

A BST has worst case because it can degenerate into a single chain when values arrive in sorted order.

Heap operations:

  • siftdown, insert and delete root:
  • heapify (build a maxheap from an array):

Graphs

For a graph with vertex set and edge set (Graph Representations):

OperationAdjacency listAdjacency matrix
Storage
Add vertex
Add edge
Remove vertex
Remove edge
Query (is there an edge?)

Sorting

Algorithm (on an array)BestAverageWorst
Bubble sort
Selection sort
Insertion sort
Mergesort
Heapsort
Quicksort

Quicksort has the worst worst case of the three fast sorts, but it is often the best practical choice because the constant hidden in its average is very small.

Searching

AlgorithmData structureWorst case
Sequential searchArray or linked list
Binary searchSorted array or BST
Depth-first searchGraph with vertices, edges
Breadth-first searchGraph with vertices, edges