Ordered sequence

General Information

Representation invariant:

1. The abstract data structure ordered sequence implements sorted sequences as defined here.
2. This abstract data structure is generic and parameterized by a fixed key type [math]\displaystyle{ \mathcal{K} }[/math].

Insert at position

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math] and a nonnegative integral position [math]\displaystyle{ \ell }[/math].

Output: a Boolean value, which is true if, and only if, [math]\displaystyle{ \ell\in\{0,\ldots,n\} }[/math], where [math]\displaystyle{ n }[/math] is the length of the list.

Precondition: None.

Postcondition: If the output ist true, a new element with the key [math]\displaystyle{ K }[/math] is inserted at position [math]\displaystyle{ \ell }[/math]. If [math]\displaystyle{ \ell=0 }[/math], this means the new element is attached before the prior first element. Otherwise, this means it is inserted between the [math]\displaystyle{ (\ell-1) }[/math]-th element and the prior [math]\displaystyle{ \ell }[/math]-th element.

Find

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently contained in the sequence.

Precondition: None.

Postcondition: None.

Remove

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently stored in the sequence.

Precondition: None.

Postcondition: If the output is true, one occurrence of [math]\displaystyle{ K }[/math] is removed.

Known Implementations

1. Linked list
2. Doubly-linked list
3. Array list