Relation: implicitly defined linear ordering

The Abstract Sorted List is defined for objects linearly ordered by some implicit property. In this case, operations such as front and back are defined by the ordering: the front of the sorted list is the least object in the container and the back is the greatest object in the container.

A hash table allows constant time—O(1)—access to the entries; however, operations such as given an object, find the next largest object in the container is linear in time, i.e., O(n). A hash table allows constant time determination of membership of a particular object; however, finding objects in a hash table which fall on an interval is, again, O(n).

Critical Operations for Abstract Sorted Lists

• Find the next larger and previous smaller objects of a given object which may or may not be in the container,
• Iterate through those objects in the container which fall on an interval ,
• Guarantee of an upper bound on other operations.

The last requirement is significant: a hash table will under the appropriate circumstances be O(1); however, there is no guarantee that an operation could not be linear in time if multiple objects hashed into the same cell.

A hash table using open addressing cannot be more than 60% full for reasonable expected run times; however, with a sorted list, it should be possible to have optimal results for all operations other than insertion.

Example Data Structures

The most obvious data structure for storing a sorted list is the array; however, insertions and removals can be as bad as O(n) for an insertion or removal from the centre of the array. (A two-ended array can reduce the run times for operations near both the front and back.)

Linked lists are not suited to storing sorted data; however, skip lists do contain characteristics which allow for optimal performance; however, in this case, the run time depends upon random number generation.

Balanced search trees, including balanced binary search trees such as AVL trees, red-black trees, and BB(α) trees; and balanced M-way trees such as the B-trees, B+-trees, B*-trees, 2-3-trees, and 2-3-4-trees both guarantee that most operations will run in O(ln(n)) time; however, they also require more memory than an array.