A sorted list maintains its elements in comparison order, making position-based lookup efficient. It suits small collections or workloads where insertion, removal, and modification are infrequent. section 2.3 section 4.4.2
For an array-backed sorted list, the main operations trade search speed against update cost:
- Find an insertion position with binary search in O(log n), then shift subsequent elements; insertion takes O(n) on average. section 2.3
- Look up an entry in O(log n) using binary search and use no extra memory. section 4.4.2
- Add or remove an entry in O(n), because maintaining order can require many elements to change position. section 2.3 section 4.4.2
Alphabetical index
An alphabetical index lets you locate a rare word without scanning every page. Open near the expected position, compare the current entry, and continue before or after it—binary search in practice. section 4.4.2
Table 4.2 Using sorted arrays as dictionaries (view table figure)
Compare construction, lookup, insertion, removal, and memory costs for sorted arrays used as dictionaries. section 4.4.2
