Array list: remove

Algorithmic problem: Ordered sequence: remove

Prerequisites:

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to array list item of type [math]\displaystyle{ \mathcal{K} }[/math]".

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

1. The pointer [math]\displaystyle{ p }[/math] points to the array list item at position [math]\displaystyle{ i+1 }[/math] (or is void if no such item exists).
2. None of the arrays at positions [math]\displaystyle{ 1,...,i+1 }[/math] contains [math]\displaystyle{ K }[/math].

Variant: The pointer [math]\displaystyle{ p }[/math] is moved one step forward to the next array list item.

Break condition: Either it is [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void or, otherwise, it is [math]\displaystyle{ K=p }[/math].next.A[math]\displaystyle{ [j] }[/math] for some [math]\displaystyle{ j \in \{1,...,p }[/math].next.n [math]\displaystyle{ \} }[/math].

Induction basis

Abstract view: If the list is empty, the algorithm terminates. Otherwise, if the key to be removed is in the first array, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).

Implementation:

1. If first[math]\displaystyle{ = }[/math]void, terminate the algorithm and return false.
2. Otherwise, if [math]\displaystyle{ K \in \{ }[/math]first.A [math]\displaystyle{ [1],..., }[/math]first.A[first.n] [math]\displaystyle{ \} }[/math]:
   1. If first.n[math]\displaystyle{ =1 }[/math], set first[math]\displaystyle{ = }[/math]first.next.
   2. Otherwise:
      1. Let [math]\displaystyle{ j \in\{1,..., }[/math]first.n [math]\displaystyle{ \} }[/math] such that first.A[math]\displaystyle{ [j]=K }[/math].
      2. For [math]\displaystyle{ h=j,..., }[/math]first.n[math]\displaystyle{ -1 }[/math] (in this order): Set first.A [math]\displaystyle{ [h]:= }[/math]first.A[math]\displaystyle{ [h+1] }[/math].
      3. Set first.A[math]\displaystyle{ [ }[/math]first.n[math]\displaystyle{ ]:= }[/math]void.
      4. Set first.n:=first.n[math]\displaystyle{ -1 }[/math].
   3. Terminate the algorithm and return true.
3. Otherwise (that is, first[math]\displaystyle{ \neq }[/math]void and [math]\displaystyle{ K \notin\{ }[/math]first.A [math]\displaystyle{ [1],..., }[/math]first.A[first.n][math]\displaystyle{ \} }[/math]), set [math]\displaystyle{ p:= }[/math]first.

Proof: If [math]\displaystyle{ p }[/math].first[math]\displaystyle{ = }[/math]void or [math]\displaystyle{ K \notin\{ }[/math]first.A[math]\displaystyle{ [1],..., }[/math]first.A[first.n][math]\displaystyle{ \} }[/math], correctness is obvious. So consider the case that first[math]\displaystyle{ \neq }[/math]void and [math]\displaystyle{ K \in \{ }[/math]first.A[1],...,first.A[first.n][math]\displaystyle{ \} }[/math]. If first.n[math]\displaystyle{ =1 }[/math], the array would be empty after removing [math]\displaystyle{ K }[/math], so Step 2.1 is right to decouple the first list item from the list. Otherwise (that is, first.n[math]\displaystyle{ \gt 1 }[/math]), [math]\displaystyle{ K }[/math] is removed and the array is rearranged accordingly in Steps 2.2.2-2.2.4.

Induction step

Abstract view: If [math]\displaystyle{ p }[/math] has reached the tail of the array list, the algorithm terminates. Otherwise, if the key to be removed is in the array of the very next array list item, it is removed and the algorithm terminates again (if this was the only element of the array, that array list item is removed as well).

Implementation:

1. If [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void, terminate the algorithm and return false.
2. Otherwise, if [math]\displaystyle{ K \in \{p }[/math].next.A[[math]\displaystyle{ 1 }[/math]],...,[math]\displaystyle{ p }[/math].A.next.A[[math]\displaystyle{ p }[/math].next.n][math]\displaystyle{ \} }[/math]:
   1. If [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ =1 }[/math], set [math]\displaystyle{ p }[/math].next[math]\displaystyle{ := }[/math].next.next.
   2. Otherwise:
      1. Let [math]\displaystyle{ j \in \{1,...,p }[/math].next.n[math]\displaystyle{ \} }[/math] such that [math]\displaystyle{ p }[/math].next.A.[math]\displaystyle{ [j]=K }[/math].
      2. For [math]\displaystyle{ h=j,..,p }[/math].next.n[math]\displaystyle{ -1 }[/math] (in this order): Set [math]\displaystyle{ p }[/math].next.A[math]\displaystyle{ [h]:=p }[/math].next.A[math]\displaystyle{ [h+1] }[/math].
      3. Set [math]\displaystyle{ p }[/math].next.A[math]\displaystyle{ [p }[/math].next.n[math]\displaystyle{ ]:= }[/math]void.
      4. Set [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ :=p }[/math].next.n [math]\displaystyle{ -1 }[/math].
   3. Terminate the algorithm and return true.
3. Otherwise (that is, [math]\displaystyle{ p }[/math].next[math]\displaystyle{ \ne }[/math]void and [math]\displaystyle{ K\notin\{p }[/math].next.A[math]\displaystyle{ [1],..., }[/math].next.A[p.next.n][math]\displaystyle{ \} }[/math]), set [math]\displaystyle{ p:=p }[/math].next.

Correctness: If [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void or [math]\displaystyle{ K\notin\{p }[/math].next.A[math]\displaystyle{ [1],...,p }[/math].next.A[first.n][math]\displaystyle{ \} }[/math], correctness is obvious. So consider the case that [math]\displaystyle{ p }[/math].next[math]\displaystyle{ = }[/math]void and [math]\displaystyle{ K\in\{p }[/math].next.A[math]\displaystyle{ [1],...,p }[/math].next.A[[math]\displaystyle{ p }[/math]next.n][math]\displaystyle{ \} }[/math]. If [math]\displaystyle{ p }[/math].next.n[math]\displaystyle{ =1 }[/math], the array would be empty after removing [math]\displaystyle{ K }[/math], so Step 2.1 is right to decouple this list item from the list. Otherwise, it is removed and the array is rearranged accordingly in Step 2.2.

Complexity

Statement: Linear in the length of the sequence in the worst case.

Proof: Obvious.