Array - based implementation

 

Insertion

 

Data Declaration as pseudo code in the following algorithm :

constant SIZE = maximum number of elements integer count

DataType theList [SIZE]

 

Input

none

Precondition

none

Operation

the variable count is set to zero

Postcondition

an empty list is created

Return value

none

 

 

Data Declaration as C++ code (program)

const int SIZE = 10;

int list [SIZE];

int count = 0;

 

Insertion to the front requires the array elements to be shifted one position to the right , and the new element stored at the first position.

 

fig 4.3 + fig 4.2 + fig 4.4 (p50+51)

 

Deletion

 

The easiest deletion method is to delete the list elements . The count is simply decremented by one, and the element at that location is simply overwritten at the next insertion.

 

DeleteSpecific (DeleteByKey) finds the position in the list of the element to be deleted and if found calls Deletion.

 

Traverse the list is reading the elements one by one and and the appropriate operation is performed on each. Two common operations are to retrieve an item or update an item.

 

fig 4.5 + fig 4.6 + fig 4.7 (55,56)

 

class List {

                      private:

                                     itemType    items[SIZE];

                                     int count;                         

                      public:

                                    //Constructors

                                    List() {count==0};

                                    List (const List&)    

                                   

                                    //Returns the value of count

                                    int getCount() {return count;};

 

                                    //Returns the address of the array items

                                    const itemType *getAddress(){ return items;};

 

                                    //Insertion Functions

                                   void insertPos ( int newdata , int pos )

                                    int insertFront ( itemType newdata)

                                    int insertBack ( itemType newdata)

                                    int insertConditional ( itemType newdata)

 

                                    //Deletion Operations

                                     void deletePos ( int pos)

                                     int deleteFront ( )

                                     int deleteBack ( )

                                     int deleteSpecific ( int deldata )       

 

                                    void traverse(); // Traversal

                       }

                                     

What if the size of the list increase than the initial size?

Solution : set the highest expected size .

Drawback : High possibility of wasting space.

Solution : Use dynamic storage as a pointer linked list .