And the node list adt section

where n is the number of elements in the list. The worst case for this kind of search occurs when

r= � n/2� .

6.4.3 Sequences

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

sequence ADT.

354