List ADT array-based implementation

LIST ADT ARRAY-BASED IMPLEMENTATION

List Abstract Data Type

A list is a sequence of zero or more elements of a given type a₁, a₂,..., a_n (n 0)

n        :  length of the list

a₁       :         first element of the list

a_n       :         last element of the list

n = 0 :         empty list

elements can be linearly ordered according to their position in the list

We say ai precedes a_i + 1, a_i + 1 follows ai, and ai is at position i

Let us assume the following:

L       :         list of objects of type element type

x        :         an object of this type

p       :         of type position

END(L)       :         a function that returns the position following the

last position in the list L

Define the following operations:

1.Insert (x, p, L)

Insert x at position p in list L

If p = END(L), insert x at the end

If L does not have position p, result is undefined

2. Locate (x, L)

returns position of x on L

returns END(L) if x does not appear

3.Retrieve (p, L)

returns element at position p on L

undefined if p does not exist or p = END(L)

4.Delete (p, L)

delete element at position p in L

undefined if p = END(L) or does not exist

5.Next (p, L)

returns the position immediately following position p

6.Prev (p, L)

returns the position previous to p

7.Makenull (L)

causes L to become an empty list and returns position END(L)

8. First (L)

returns the first position on L

9.Printlist (L)

print the elements of L in order of occurrence