Sorted list
A sorted list is a sequence whose elements are arranged according to a defined ordering criterion.
Grokking Data Structures
A sorted list is a list whose elements are maintained in a defined order.
- How it is used
- Uses ordering to keep a linked list’s smallest element at its head or a priority queue’s highest-priority element at its front.
- How deep it goes
- Explains where to insert, compares operation costs, and shows why linked lists lack the binary-search advantage of sorted arrays.
- Examples
- Uses baseball cards sorted by team and name and a priority queue ordered from highest to lowest priority.
- What you can do after
- Evaluate/understand when sorted linked lists provide fast head access and when sorted arrays are better suited to fast search.
Fabulous Adventures in Data Structures and Algorithms
A sorted word list is a word collection stored in lexicographic order for ordered searching and prefix matching.
- How it is used
- Supports exact word lookup and prefix searching for typing completion and word-game word lists.
- How deep it goes
- Explains C# implementation details and derives O(m log n) lookup cost, including the additional scan cost of prefix matches.
- Examples
- Uses typing completion, word-game moves, and Scrabble bingo generation as motivating word-list searches.
- What you can do after
- Build it from scratch with C# List<string>, BinarySearch, insertion-point handling, and lazy prefix enumeration.
Read how Fabulous Adventures in Data Structures and Algorithms explains sorted list →
Advanced Algorithms and Data Structures
A sorted list is a sequence of elements maintained in an order that supports locating an element's position by comparison.
- How it is used
- Supports fast ordered lookup when collections are small or updates are infrequent.
- How deep it goes
- Explains binary-search lookup and linear update costs, but stops short of implementation code or internal proofs.
- Examples
- Uses alphabetical indexes, phone books, and sorted arrays used as dictionaries.
- What you can do after
- Evaluate sorted-list suitability by comparing lookup speed against insertion, removal, memory, and collection-size costs.
Read how Advanced Algorithms and Data Structures explains sorted list →
Related concepts
- binary searchused by · Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
- sorting algorithmproduced by · A sorting algorithm is a procedure that rearranges elements of a collection into an order determined by an ordering criterion.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.