time complexities

Insert at head

Best Case: O(1), Worst Case: O(1), Why: Only update head

Remove head

Best Case: O(1), Worst Case: O(1), Why: Only update head

Insert at tail (with tail ref)

Best Case: O(1), Worst Case: O(1), Why: Direct pointer

Insert at tail (no tail ref)

Best Case: O(n), Worst Case: O(n), Why: Must traverse

Remove tail

Best Case: O(n), Worst Case: O(n), Why: Need previous node

Search

Best Case: O(1), Worst Case: O(n), Why: First node vs last/not found

Count nodes

Best Case: O(n), Worst Case: O(n), Why: Must traverse

Access root

Best Case: O(1), Worst Case: O(1), Notes: Always direct

Traverse tree

Best Case: O(n), Worst Case: O(n), Notes: All nodes visited

Search in Binary Search Trees (BST)

Best Case: O(log n), Worst Case: O(n), When: Balanced vs skewed

Insert in Binary Search Trees (BST)

Best Case: O(log n), Worst Case: O(n), When: Sorted input causes skew

Remove in Binary Search Trees (BST)

Best Case: O(log n), Worst Case: O(n), When: Same reasoning

Search in AVL Trees

Best Case: O(log n), Worst Case: O(log n), Why: Tree stays balanced

Insert in AVL Trees

Best Case: O(log n), Worst Case: O(log n), Why: Rotations are O(1)

Remove in AVL Trees

Best Case: O(log n), Worst Case: O(log n), Why: Rebalancing up tree

Push in Stacks

Best Case: O(1), Worst Case: O(1), Notes: Array or linked list

Pop in Stacks

Best Case: O(1), Worst Case: O(1), Notes: Remove top

Peek in Stacks

Best Case: O(1), Worst Case: O(1), Notes: No removal

Search in Stacks

Best Case: O(n), Worst Case: O(n), Notes: Must scan

Enqueue in Queues

Best Case: O(1), Worst Case: O(1), Notes: With circular array / linked list

Dequeue in Queues

Best Case: O(1), Worst Case: O(1), Notes: Remove front

First in Queues

Best Case: O(1), Worst Case: O(1), Notes: No removal

Search in Queues

Best Case: O(n), Worst Case: O(n), Notes: Must scan

Hash Tables - Search

O(1) best / O(n) worst case due to many collisions

Hash Tables - Insert

O(1) best / O(n) worst case due to table full or collisions

Hash Tables - Remove

O(1) best / O(n) worst case due to same reasoning

Priority Queues - Unsorted List Insert

O(1) best / O(1) worst case

Priority Queues - Unsorted List min

O(n) best / O(n) worst case

Priority Queues - Unsorted List remove_min

O(n) best / O(n) worst case

Priority Queues - Sorted List Insert

O(n) best / O(n) worst case

Priority Queues - Sorted List min

O(1) best / O(1) worst case

Priority Queues - Sorted List remove_min

O(1) best / O(1) worst case

Priority Queues - Heap Insert

O(1)* best / O(log n) worst case

Priority Queues - Heap min

O(1) best / O(1) worst case

Priority Queues - Heap remove_min

O(log n) best / O(log n) worst case

Selection Sort

O(n²) best / O(n²) worst case, always scans entire list

Insertion Sort

O(n) best / O(n²) worst case, fast on nearly-sorted data

Heap Sort

O(n log n) best / O(n log n) worst case, guaranteed

BST-based sort

O(n log n) best / O(n²) worst case, unbalanced tree risk

Exam-Day Memory Rule - Insert

Upheap

Exam-Day Memory Rule - Remove

Downheap

Exam-Day Memory Rule - Queue

FIFO

Exam-Day Memory Rule - Stack

LIFO

Exam-Day Memory Rule - Heap height

O(log n)

Exam-Day Memory Rule - Hash tables

O(1) expected, O(n) worst

Exam-Day Memory Rule - Insertion sort best case

O(n)