Saturday, October 25, 2014

Array Based Implementation of LIST ADT


If you want to know about ADT, please have a look at What is Abstract Date Type?

If You want to know about LIST ADT, please have a look at What is LIST ADT? 



What is Array?


  • An Array is a data structure which can store a fixed-size sequential collection of elements of the same type.
  • An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.
  • Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to represent individual variables.
  • A specific element in an array is accessed by an index.
  • All arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element.


Array Based Implementation of LIST

List Structure::



Operations:

1. Is Empty(LIST)
2. Is Full(LIST)
3. Insert Element to End of the LIST.
4. Delete Element from End of the LIST.
5. Insert Element to front of the LIST.
6. Delete Element from front of the LIST.
7. Insert Element to nth Position of the LIST.
8. Delete Element from nth Position of the LIST.
9. Search Element in the LIST.
10. Print the Elements in the LIST.

Fresh LIST::


1. Is Empty(LIST)

     If (Current Size==0) "LIST is Empty"
     else "LIST is not Empty"



2. Is Full(LIST)

    If (Current Size=Max Size) "LIST is FULL"
    else "LIST is not FULL"


3. Insert Element to End of the LIST.


  1. Check that weather the List is full or not
    1. If List is full return error message ”List is full. Can’t Insert”.
    2. If List is not full. 
      1. Get the position to insert the new element by Position=Current Size+1
      2. Insert the element to the Position
      3. Increase the Current Size by 1 i.e. Current Size=Current Size+1



4. Delete Element from End of the LIST.


  1. Check that weather the List is empty or not
    1. If List is empty return error message ”List is Empty. Can't Delete”.
    2. If List is not Empty. 
      1. Get the position of the element to delete by Position=Current Size
      2. Delete the element from the Position
      3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1





5. Insert Element to front of the LIST.


  1. Check that weather the List is full or not
    1. If List is full return error message ”List is full. Can't Insert”.
    2. If List is not full. 
      1. Free the 1st Position of the list by moving all the Element to one position forward i.e New Position=Current Position + 1.
      2. Insert the element to the 1st  Position
      3. Increase the Current Size by 1 i.e. Current Size=Current Size+1




6. Delete Element from front of the LIST.


  1. Check that weather the List is empty or not
    1. If List is empty return error message ”List is Empty. Can't Delete”.
    2. If List is not Empty. 
      1. Move all the elements except one in the 1st position to one position backward i.e New Position= Current Position -1
      2. After the 1st step, element in the 1st position will be automatically deleted.
      3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1




7. Insert Element to nth Position of the LIST.


  1. Check that weather the List is full or not
    1. If List is full return error message ”List is full. Can't Insert”.
    2. If List is not full. 
      1. If List is Empty, Insert element at Position 1.
      2. If (nth Position > Current Size)
        1. Return message “nth Position Not available in List
      3. else
        1. Free the nth Position of the list by moving all Elements to one position forward except n-1,n-2,... 1 Position i.e move only from n to current size position Elements. i.e New Position=Current Position + 1.
        2. Insert the element to the nth  Position
        3. Increase the Current Size by 1 i.e. Current Size=Current Size+1




8. Delete Element from nth Position of the LIST.


  1. Check that weather the List is Empty or not
    1. If List is Empty return error message ”List is Empty.”
    2. If List is not Empty. 
      1. If (nth Position > Current Size)
        1. Return message “nth Position Not available in List”
      2. If (nth Position == Current Size)
        1. Delete the element from nth Position
        2. Decrease the Current Size by 1 i.e. Current Size=Current Size-1
      3. If (nth Position < Current Size)
        1. Move all the Elements to one position backward except n,n-1,n-2,... 1 Position i.e move only from n+1 to current size position Elements. i.e New Position=Current Position - 1.
        2. After the previous step, nth element will be deleted automatically.
        3. Decrease the Current Size by 1 i.e. Current Size=Current Size-1






9. Search Element in the LIST.


  1. Check that weather the list is empty or not.
    1. If List is empty, return error message “List is Empty”.
    2. If List is not Empty
      1. Find the Position where the last element available in the List by Last Position = Current Size
      2. For( Position 1 to Last Position)
        1. If(Element @ Position== Search Element)//If Element matches the search element
        2. return the Position by message  “Search Element available in Position
      3. Else return message “Search Element not available in the List




10. Print the Elements in the LIST.


  1. Check that weather the list is empty or not.
    1. If List is empty, return error message “List is Empty”.
    2. If List is not Empty
      1. Find the Position where the last element available in the List by Last Position = Current Size
      2. For( Position 1 to Last Position)
      3. Print the Position and Element available at the position of List.




Goto C Program for array implementation of LIST

Advantages of Array Implementation of LIST:


  • No need to declare Large number of variables Individually
  • Variables are not scattered in Memory, they are stored in contiguous memory.
  • Ease the handling of large number of variables of same datatype.

Disadvantages of Array Implementation of LIST:


  • Rigid Structure
  • Can be hard to add/remove elements.
  • Cannot be dynamically re-sized in most Languages.
  • Memory Loss 



C Program:::



#include <stdio.h>

int MAXSIZE=10;   //MAXSIZE of List
int CURRENTSIZE=0;//CURRENTSIZE 0f List Initially Zero

int isEmpty()
{
    if(CURRENTSIZE==0)
    {
      return 1;       //If (Current Size==0) "LIST is Empty" return 1
    }                 //else "LIST is not Empty" return 0
    else return 0;
    
}

int isFull()
{
    if(CURRENTSIZE==MAXSIZE)
    {
      return 1;   // If (Current Size==Max Size) "LIST is FULL" return 1
    }             //else "LIST is not FULL" return 0
    else return 0;
}

void insertToEOL(int *Listptr)
{
     if(isFull())
     {
       printf("List is Full Can’t Insert\n");//If List is full return error message ”List is full. Can’t Insert”.
     }                                       
     else                                    //else
     {                                       //
         int element;
         printf("Enter the Element to Insert\n");//Get the element to insert
         scanf("%d",&element);//Get the position/index to insert new Element
         int index=CURRENTSIZE;//by index=CurrentSize i.e POsition=CurrentSize+1
         Listptr[index]=element;//insert element to position
         CURRENTSIZE=CURRENTSIZE+1;//increase the current size by 1
     }
    
}

void deleteFromEOL(int *List)
{
     if(isEmpty())
     {
       printf("List is Empty. We cant Delete\n"); //If List is empty return error message ”List is empty. Can’t delete”.
     }
     else                                         //else
     {
         int element;
         int index=CURRENTSIZE-1;//Get the position/index to delete element
         element=List[index];//index =currentsize-1 i.e Position=currentSize
         printf("Element %d deleted from postion %d\n",element,index+1);
         CURRENTSIZE=CURRENTSIZE-1;//Decrease the CurrentSize by 1
     }
   
}

void insertToFOL(int *List)
{
     
     if(isFull())
     {
      printf("List is Full... cant insert\n");//If List is full return error message ”List is full. Can’t Insert”.
     }
     else  //else
     {
         int index=0,element;//Get the Element
         printf("Enter the element to insert\n");
         scanf("%d",&element);
         
         for(index=CURRENTSIZE;index>0;index--)   //Free the 1st Position by moving all the elements to one position
         {//forward by New Postion=CurrentPosition +1
              List[index]=List[index-1];
         }
         List[0]=element;//insert the element to Position 1 i.e index 0
         CURRENTSIZE=CURRENTSIZE+1;//increase the current size by 1
     }
    
}

void deleteFromFOL(int *List)
{
     if(isEmpty())
     {
        printf("List is Empty... cant delete\n"); //If List is empty return error message ”List is empty. Can’t delete”.
     }
     else//else
     {
          int index=0,element;
          element=List[0]; //
         for(index=0;index<CURRENTSIZE;index++)
         {//Move all the elements except one in 1st position
           List[index]=List[index+1];//element in 1st Position automatically deleted
         }
         CURRENTSIZE=CURRENTSIZE-1;
         printf("Element %d from Position 1\n",element);
     }
   
}

void insertToNthPos(int *List)
{
     if(isFull()) //If List is Full Cant Insert
     {
       printf("List is Full... Cant insert\n");
     } //else
     else
     {                                                  
         int i,index=0,element,pos;
         printf("Available Postion in LIst\n");
         if(isEmpty())//If List is empty We can insert at Postion 1 only
         {
            printf("List is Empty... only Available Position is 1\n");
            printf("Enter the Element to insert\n");//Get the element to insert
            scanf("%d",&element);
            List[0]=element;//Insert the element at index Zero i.e @ Position 1
            CURRENTSIZE=CURRENTSIZE+1; //Increase the CURRENTSIZE by 1
         }
         else //If List is not empty
         {
           do
            {
             printf("Enter the Position(within %d from 1) in which you want to insert Element\n",CURRENTSIZE);
             scanf("%d",&pos);//We can insert the element only at the Position1 to CURRENTSIZE
            }while(pos>CURRENTSIZE || pos<0); //Continue do loop until get the available position i.e from 1 to CURRENTSIZE
            
            printf("Enter the Element to insert\n");
            scanf("%d",&element);//Get the element
             for(index=CURRENTSIZE;index>pos-1;index--)
             {
              List[index]=List[index-1]; //Move the elements of nth postion to CURRENTSIZE Position to one step forward
             }
          List[pos-1]=element;//Insert the element at Nth Postion
          CURRENTSIZE=CURRENTSIZE+1; //Increase the CURRENTSIZE by 1
         }
        
        
        
     }
    
}

void deleteFromNthPos(int *List)
{
     int element,pos,index;
      if(isEmpty())
     {
        printf("List is Empty... cant delete\n");  //If List is empty return error message ”List is empty. Can’t delete”.
     }
     else //else
     {
          do
            {
             printf("Enter the Position(within %d from 1) from which you want to Delete Element\n",CURRENTSIZE);
             scanf("%d",&pos);//We can delete element at position 1 to CURRENTSIZE
            }while(pos>CURRENTSIZE || pos<0); //Continue do loop until get the available position i.e from 1 to CURRENTSIZE
            element=List[pos-1];
          if(pos==CURRENTSIZE)//If Nth Position=CURRENTSIZE
          { //Decrease the CURRENTSIZE by 1
           CURRENTSIZE=CURRENTSIZE-1;//Element at the Nth Position will be automatically deleted
          }
          else//If Nth Postion not equal to CURRENTSIZE
          {
              for(index=pos-1;index<CURRENTSIZE;index++)
             {//Move the elements of nth postion to CURRENTSIZE Position to one step backward     
              List[index]=List[index+1];
             }
             CURRENTSIZE=CURRENTSIZE-1;//Decrease the CURRENTSIZE by 1
          }
          printf("Element %d deleted from postion %d\n",element,pos);
     }
    printf("deleteFromNthPos\n");
}

void searchInList(int *List)
{
     int element,index,i,found=0;//Initially found=0
     if(isEmpty())//If list is empty retun List is empty
     {
      printf("List is empty\n");
     }
     else //If list is not empty
     {
     printf("Enter the Element to search\n");
     scanf("%d",&element);//Get the element to search
     for(i=0;i<CURRENTSIZE;i++)
     {//Look for elements in the Positions 1 to CURRENTSIZE
      if(List[i]==element)//If Searching element available in List[Postion]
      {
       found=1;//found=1
       break;
      }
     }
     if(found) printf("Element %d available in Position %d\n",element,i+1);//If found=1 element available in List
     else printf("Element %d not available in List\n",element);//If found=0 element not available
     }

}

void printList(int List[])
{
     int i=0;
     if(isEmpty())//If List is Empty return List is Empty
     {
        printf("List is Empty\n");
     }
     else  //If List is not empty
     {
         printf("***Position--->Value***\n");
         for(i=0;i<CURRENTSIZE;i++)          //for Postion 1 to CURRENTSIZE
         {
         printf("   %d--------->%d\n",i+1,List[i]); //Print the element in the Postion
         }
     }
     printf("***List Current Status***\n");
     printf("MAXSIZE    =%d\n",MAXSIZE);
     printf("CURRENTSIZE=%d\n",CURRENTSIZE);

    
}
int main()
{
    int List[MAXSIZE];//List array
    int iChoice=0,r=0;
    do
    {
      printf("--------------Array Implementation Of List-----------\n");
      printf("\t\t1. is Empty\n\t\t2. is Full\n\t\t3. Insert Element to End of LIST\n\t\t4. Delete Element from End of LIST\n\t\t5. Insert Element to Front of LIST\n\t\t6. Delete Element from Front of LIST\n\t\t7. Insert Element to nth Position of LIST\n\t\t8. Delete Element from Nth Postion of LIST\n\t\t9. Search Element in LIST\n\t\t10. print LIST\n\t\t11. Exit\n");
      printf("------------------------------------------------------------\n");
      printf("Please Enter Ur Choice\n");
      scanf("%d",&iChoice);
      switch(iChoice)
      {
       case 1:
             r=isEmpty();
             //printf("r=%d\n",r);
             r==0?printf("List is Not Empty\n"):printf("List is Empty\n");
              printf("------------------------------------------------------------\n");
             break;
       case 2:
            r=isFull();
            r==0?printf("List is Not Full\n"):printf("List is Full\n");
             printf("------------------------------------------------------------\n");
            break;
       case 3:
            insertToEOL(List);
             printf("------------------------------------------------------------\n");
            break;
       case 4:
            deleteFromEOL(List);
             printf("------------------------------------------------------------\n");
            break;
       case 5:
            insertToFOL(List);
             printf("------------------------------------------------------------\n");
            break;
       case 6:
            deleteFromFOL(List);
             printf("------------------------------------------------------------\n");
            break;
       case 7:
            insertToNthPos(List);
             printf("------------------------------------------------------------\n");
            break;
       case 8:
            deleteFromNthPos(List);
             printf("------------------------------------------------------------\n");
            break;
       case 9:
            searchInList(List);
             printf("------------------------------------------------------------\n");
            break;
       case 10:
            printList(List);
             printf("------------------------------------------------------------\n");
            break;
       case 11:
            break;
      
       default:
          printf("===============================================================\n");
          printf("\t\tHi Dude You are not entered the right choice\n");
          printf("===============================================================\n");
          }
       }while(iChoice!=11);
       system("PAUSE");
    }
    

Output::


1. Array Implementation Of List Menu



2. Insert to End of LIST

3. Delete From End of LIST

4. Insert to Front Of List

5. Delete from Front Of List

6. Insert to Nth Position of List
7. Delete from Nth Position of List

8. List is Full

9. List is Empty

References::

5 comments: