Data Structures Final Big-O

ArrayList | add(index, val) / remove(index)

Best-case: O(1), Worst-case: O(n)

ArrayList | add(val) at end (amortized)

Best-case: O(1), Worst-case: O(1)

ArrayList | get(index) / set(index, val)

Best-case: O(1), Worst-case: O(1)

ArrayList | contains(val)

Best-case: O(1), Worst-case: O(n)

LinkedList (Singly/Doubly) | add/remove at head or tail

Best-case: O(1), Worst-case: O(1)

LinkedList (Singly/Doubly) | add/remove/search at index

Best-case: O(1), Worst-case: O(n)

LinkedList (Singly/Doubly) | get(index)

Best-case: O(1), Worst-case: O(n)

Stack (array or linked list) | push, pop, peek, isEmpty

Best-case: O(1), Worst-case: O(1)

Queue | enqueue, dequeue, peek

Best-case: O(1), Worst-case: O(1)

Deque | add/remove at both ends

Best-case: O(1), Worst-case: O(1)

BST (unbalanced) | insert, delete, contains

Best-case: O(log n), Worst-case: O(n)

AVL Tree | insert, delete (with rotations)

Best-case: O(log n), Worst-case: O(log n)

AVL Tree | contains, findMin, findMax

Best-case: O(log n), Worst-case: O(log n)

Tree Traversals | in-order, pre-order, post-order

Best-case: O(n), Worst-case: O(n)

Expression Tree Evaluation | build & evaluate from postfix

Best-case: O(n), Worst-case: O(n)

Hash Table - Chaining | insert, delete, contains

Best-case: O(1), Worst-case: O(n)

Hash Table - Chaining | Average-case (with good hash & load factor < 1)

Best-case: O(1), Worst-case: O(1)

Hash Table - Linear Probing | insert, delete, contains

Best-case: O(1), Worst-case: O(n)

Heap (Binary Min/Max Heap) | insert (percolate up)

Best-case: O(1), Worst-case: O(log n)

Heap (Binary Min/Max Heap) | deleteMin / deleteMax (percolate down)

Best-case: O(log n), Worst-case: O(log n)

Heap (Binary Min/Max Heap) | buildHeap (array)

Best-case: O(n), Worst-case: O(n)

Heap (Binary Min/Max Heap) | peek

Best-case: O(1), Worst-case: O(1)

Selection Sort | All operations

Best-case: O(n²), Worst-case: O(n²)

Insertion Sort | All operations

Best-case: O(n), Worst-case: O(n²)

Merge Sort | All operations

Best-case: O(n log n), Worst-case: O(n log n)

Quick Sort | All operations (median-of-three)

Best-case: O(n log n), Worst-case: O(n²)

Heap Sort | All operations

Best-case: O(n log n), Worst-case: O(n log n)

Dijkstra's (w/ Min Heap) | Full run

Best-case: O((V + E) log V), Worst-case: O((V + E) log V)

Topological Sort | DFS or in-degree queue

Best-case: O(V + E), Worst-case: O(V + E)

Kruskal's (with union-find) | Full run

Best-case: O(E log E), Worst-case: O(E log E)

Prim's (w/ min-heap) | Full run

Best-case: O((V + E) log V), Worst-case: O((V + E) log V)

Hash Table Quadratic Probing 'insert, delete, contains"

Best-case: O(1), Worst-case: O(n)