Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

The next type of searchable container that we consider is a
*sorted list* .
A sorted list is like an ordered list:
It is a searchable container that holds a sequence of objects.
However, the position of an item in a sorted list is not arbitrary.
The items in the sequence appear in order, say,
from the smallest to the largest.
Of course, for such an ordering to exist,
the relation used to sort the items must be a *total order*.

Program defines the `SortedList` interface.
Like its unsorted counterpart, the `SortedList` interface
extends the `SearchableContainer` interface defined
in Program .

**Program:** `SortedList` interface.

In addition to the basic repertoire of operations supported by all searchable containers, sorted lists provide the following operations:

`this[int]`- used to access the object at a given position in the sorted list; and
`FindPosition`-
used to find the position of an object in the sorted list.

Sorted lists are very similar to ordered lists.
As a result, we can make use of the code for ordered lists
when implementing sorted lists.
Specifically, we will consider an array-based implementation of
sorted lists that is derived from the `OrderedListAsArray` class
defined in Section ,
and a linked-list implementation of sorted lists
that is derived from the `OrderedListAsLinkedList`
class given in Section .

- Array Implementation
- Linked-List Implementation
- Performance Comparison:
`SortedListAsArray`vs.`SortedListAsList` - Applications

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.