A data structure stores and organizes data to support operations such as insertion, search, deletion, and update. Each structure makes different performance tradeoffs, so choosing one can simplify an algorithm and improve its runtime. section 4.1 section 1.5.1
Common structures and their implementation roles include:
- Fixed-size arrays provide constant-time O(1) element access when the size is known. section 4.1.1
- Dynamically resizable arrays, such as Python lists or C++ vectors, handle unknown or changing sizes. section 1.5.1 section 4.1.1
- Maps and sets provide nonlinear organization; ordered variants use self-balanced binary search trees with O(n log n) insertion, search, and deletion. section 1.5.1
- Hash tables or unordered maps offer expected O(1) access when collisions do not undermine the assumption. section 1.5.1
- Stacks support O(1) push and pop operations in last-in, first-out order, while linked lists require linear-time search. section 4.1.1
Choosing an array operation
A linear scan searches an array in O(n). If the array is sorted, binary search reduces the search to O(log n). Naive selection and insertion sorts take O(n²), whereas merge sort, heap sort, and quicksort generally take O(n log n). section 4.1.1
