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 *$\ell$p)
        {
            return ($\ell$p $\rightarrow$ last + 1)
        }

 
 

Insert (x, p,L)

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

        {

            int v; /* running position */

            if ($\ell$p $\rightarrow$ last >= maxlength-1)

                    error (``list is full'')

            elseif ((p < 0) || (p > $\ell$p $\rightarrow$ last + 1))

                    error (position does not exist)

                    else

                    for (q = $\ell$p $\rightarrow$ last ; q <= p, q-)

                        $\ell$p $\rightarrow$ elements [q + 1] = $\ell$p $\rightarrow$ elements [q] ;

                    $\ell$p $\rightarrow$ last = $\ell$p $\rightarrow$ last + 1 ;

                    $\ell$p $\rightarrow$ elements [p] = x

}
 
 

Delete (p, L)

void delete (int p ; list-type *$\ell$p)

{

                int q ; /* running position */

                if ((p > $\ell$p $\rightarrow$ last) || (p < 0))

                    error (``position does not exist'')

                else /* shift elements */ {

                    $\ell$p $\rightarrow$ last - ;

                    for (q = p ; q <= $\ell$p $\rightarrow$ last; q ++)

                        $\ell$p $\rightarrow$ elements [q] = $\ell$p $\rightarrow$ elements [q+1]

                }

}
 
 

Locate (x, L)

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

            {

                int q ;

                for (q = 0 ; q <= $\ell$p $\rightarrow$ last ; q++)

                    if ($\ell$p $\rightarrow$ elements [q] = = x]

                        return (q) ;

                    return ($\ell$p $\rightarrow$ last + 1) /* if not found */

}