Next:2.2.2 Pointer Implementation of ListsUp:2.2 Implementation of ListsPrevious:2.2 Implementation of Lists

## 2.2.1 Array Implementation of Lists

• Here, elements of list are stored in the (contiguous) cells of an array.
• List is a structure with two members.

• member 1 : an array of elements

member 2 : last -- indicates position of the last element of the list

Position is of type integer and has the range 0 to maxlength-1

# define maxlength 1000

typedef int elementtype; /* elements are integers */

typedef struct list-tag {

elementtype elements [maxlength];

int last;

} list-type;
end(L)
int end (list-type *p)
{
return ( last + 1)
}

Insert (x, p,L)

void insert (elementtype x ; int p ; list-type *p) ;

{

int v; /* running position */

if ( last >= maxlength-1)

error (list is full'')

elseif ((p < 0) || (p >  last + 1))

error (position does not exist)

else

for (q =  last ; q <= p, q-)

elements [q + 1] =  elements [q] ;

last =  last + 1 ;

elements [p] = x

}

Delete (p, L)

void delete (int p ; list-type *p)

{

int q ; /* running position */

if ((p >  last) || (p < 0))

error (position does not exist'')

else /* shift elements */ {

last - ;

for (q = p ; q <=  last; q ++)

elements [q] =  elements [q+1]

}

}

Locate (x, L)

int locate (element type *x ; list-type *p)

{

int q ;

for (q = 0 ; q <=  last ; q++)

if ( elements [q] = = x]

return (q) ;