where n is the number of elements in the list. The worst case for this kind of search occurs when
r= � n/2� .
A sequence is an ADT that supports all of the methods of the deque ADT (Section 5.3), the array list ADT (Section 6.1), and the node list ADT (Section 6.2). That is, it provides explicit access to the elements in the list either by their indices or by their positions. Moreover, since it provides this dual access capability, we also include, in the sequence ADT, the following two "bridging" methods that provide connections between indices and positions:
Code Fragment 6.18: The Sequence interface
defined via multiple inheritance. It includes all the
Implementing a Sequence with an Array