Ordered sequence: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 10: Line 10:
'''Input:''' A key <math>K \in \kappa</math> and a nonnegative integral position <math>p</math>.
'''Input:''' A key <math>K \in \kappa</math> and a nonnegative integral position <math>p</math>.


'''Output:''' a Boolean value, which is true if, and only if, <math>p\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list.
'''Output:''' a Boolean value, which is '''true''' if, and only if, <math>p\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list.


'''Precondition:'''
'''Precondition:'''

Revision as of 16:05, 16 May 2015


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{ \kappa }[/math].

Insert at position

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

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

Precondition:

Postcondition: If the output ist true, a new element with the key [math]\displaystyle{ K }[/math] is inserted at position [math]\displaystyle{ p }[/math].

Find

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

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

Precondition:

Postcondition:

Remove

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

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

Precondition:

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