Relation: explicitly defined linear ordering
The Abstract List
The Abstract List is defined for objects which are explicitly ordered by the programmer. The first object in the list is defined to be at the front of the list and the last is at the back of the list.
Both a linked list and an array may be used to implement the Abstract List and each of these has positive and negative features with respect to the run time of various operations. An alternate possibility may be to use a linked list of fixed-size arrays. This hybrid approach is used in the STL for the deque data structure.
The next abstract data structure discussed is the Abstract Sorted List where objects are stored in such a way that it is possible to step through the entries in order. One may claim that the Abstract Sorted List is simply a specialization of the Abstract List; however, this is not entirely true: it makes no sense to replace one object in a sorted list unless there is some guarantee that it correctly fits into that position. Defining a Abstract List which then has two specializations of Abstract Unsorted List and Abstract Sorted List may be elegant; however, such a generalization would be essentially worthless: the number of operations relevant to each is very restricted.
In The Art of Computer Programming, Volume 1: Fundamental Algorithms, Donald Knuth begins Section 2.2 with a list of nine operations which "we might want to perform on linear lists":
In this discussion, note that operations 4, 5, 6, 7, and 9 are classified as operations which may be performed on general containers. The last operation, searching a list, can be optimized to O(1) if a hash table is used (with no relation) or O(ln(n)) if a balanced binary search tree is used (with a linear ordering).