2.1 List Abstract Data Type

A list is a sequence of zero or more elements of a given type 

a₁, a₂,..., a_n  (n$$\geq$$ 0)

 

$\bullet$	n	:	length of the list
$\bullet$	a1	:	first element of the list
$\bullet$	an	:	last element of the list
$\bullet$	n = 0	:	empty list
$\bullet$	elements can be linearly ordered according to their position in the list

We say a_i precedes a_{i + 1}, a_{i + 1} follows a_i, and a_i 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