Ordered sequence: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 8: Line 8:


== Insert at position ==
== Insert at position ==
'''Input:''' A key <math>K \in \Kappa</math> and a nonnegative integral position <math>p</math>.
'''Input:''' A key <math>K \in \mathcal{K}</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.
Line 17: Line 17:


== Find ==
== Find ==
'''Input:''' A key <math>K \in \kappa </math>.
'''Input:''' A key <math>K \in \mathcal{K} </math>.


'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently contained in the sequence.
'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently contained in the sequence.
Line 26: Line 26:


== Remove ==
== Remove ==
'''Input:''' A key <math>K \in \kappa</math>.
'''Input:''' A key <math>K \in \mathcal{K}</math>.


'''Output:''' A Boolean value, which is ''''true'''' if, and only if, <math>K</math> is currently stored in the sequence.
'''Output:''' A Boolean value, which is ''''true'''' if, and only if, <math>K</math> is currently stored in the sequence.

Revision as of 09:24, 17 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{ \mathcal{K} }[/math].

Insert at position

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/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 \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:

Postcondition:

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:

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