Ordered sequence: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 35: Line 35:


== Known Implementations ==
== Known Implementations ==
# [[LinkedList]]
# [[Linked list]]
# [[DoublyLinkedList]]
# [[Doubly linked list]]
# [[ArrayList]]
# [[Array list]]

Revision as of 14: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

Input: A key [math]\displaystyle{ K \in \kappa }[/math] and a nonnegative integral position <mth>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