Ad

Saturday, June 30, 2007

Insertion and Deletion of elements in an Array

Suppose you are storing temperature data for a few months and you forgot to store the temperature of a particular day (say 5th day) then you need to INSERT that temperature after the 4th element of the array and in the other case if you accidentally stored duplicate data then you need to DELETE the duplicate element.

Apart from these simple examples, there are many other uses of insertion and deletion

The array to which the element is to be inserted or deleted can be of two types unordered (unsorted) and ordered (sorted). Here we will be discussing about the insertion and deletion of element in an unordered or unsorted array.

For insertion in these types of arrays, we need to have two information, the element to be inserted and the position to which it will be inserted. For deletion, we only need the position.

Suppose we have the following array:

arr[5]={5,7,2,1,3}

And we need to insert the element 6 at the 2nd position, after insertion:

arr[5]={5,6,7,2,1}

Notice how the last element of the array (i.e. 3) has gone out to compensate for the insertion.

Now, suppose we wish to delete the element at position 3rd, after deletion:

arr[5]={5,6,2,1,0}

We see, all the elements after the 3rd have shifted to their left and the vacant space is filled with 0.

That’s exactly how insertion and deletion are done!

Algorithm for Insertion of an element in an array

Suppose, the array to be arr[max], pos to be the position at which the element num has to be inserted. For insertion, all the elements starting from the position pos are shifted towards their right to make a vacant space where the element num is inserted.

  1. FOR I = (max-1) TO pos
         arr[I] = arr[I-1]
  2.  arr[I] = num

Yeah it is that simple!

Algorithm for Deletion of an element in an array

Suppose, the array to be arr[max], pos to be the position from which the element has to be deleted. For deletion, all the elements to the right of the element at position pos are shifted to their left and the last vacant space is filled with 0.

  1. FOR I = pos TO (max-1)
         arr[I-1] = arr[I]
  2. arr[I-1] = 0

Now, to illustrate all this let me show you a simple example program:

  // Example Program to illustrate
  // insertion and deletion of
  // elements in an array

  #include<iostream.h>

  // array has been declared as
  // global so that other functions
  // can also have access to it
  int arr[5];

  // function prototype
  void a_insert(int, int);
  void a_delete(int);

  void main(void)
  {
   int ch;
   int num,pos;

   while(ch!=4)
   {
    cout<<"1> Insert";
    cout<<"\n2> Delete";
    cout<<"\n3> Show";
    cout<<"\n4> Quit\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;
     cout<<"enter pos.:";
     cin>>pos;

     a_insert(num,pos);
     break;

     case 2:
     cout<<"enter pos.:";
     cin>>pos;
     a_delete(pos);
     break;

     case 3:
     cout<<"\nArray:";
     for(int i=0;i<5;i++)
       cout<<arr[i]<<" ";
     break;
    }
    cout<<"\n";
   }
  }

  // insertion function
  void a_insert(int num, int pos)
  {
   for(int i=4; i>=pos;i--)
     arr[i]=arr[i-1];
   arr[i]=num;
  }
  // deletion function
  void a_delete(int pos)
  {
   for(int i=pos; i<=4;i++)
   arr[i-1]=arr[i];
   arr[i-1]=0;
  }

Good-Bye!

Related Articles:

19 comments:

  1. elaborate further thank you........

    ReplyDelete
  2. how deletion happened how exactly it happened im sorry i really dont know......is there any formula or something?......before the exact answer that you gave.thank you...

    ReplyDelete
  3. @macnasty

    Sorry for being so late.

    We have the algorithm above for deletion. To elaborate it further, consider the following example.

    suppose we've an array having the following elements in the order of increasing index:
    1,2,3,4,5

    Now suppose if we want to delete element having index 2 i.e element '3'. We just move all the elements to its right (4,5) one place to the left, as arrays are of fixed index we put 0 to the right most element.

    Thank you.

    pls don't hesitate to ask if you still have probs.

    ReplyDelete
  4. nadine5:09 PM

    hii,
    i just want to say that that article was amazing really easy and simple!

    thank you soo much!

    it will be in my favorites always!

    keep computer science coming!

    please post articles about the bubble sort
    selection sort
    big-oh notation
    the order of magnitude

    please please!
    xoxo,
    nadine

    ReplyDelete
  5. @Nadine

    It's my pleasure!

    Well, I've already written some articles on the topics you mentioned:

    http://www.learning-computer-programming.blogspot.com/2007/06/sorting-array-using-bubble-sort.html

    http://www.learning-computer-programming.blogspot.com/2007/06/sorting-array-using-selection-sort.html

    http://www.learning-computer-programming.blogspot.com/2007/07/sorting-two-dimensional-arrays.html

    Hope you'll find them useful!

    Thank You

    ReplyDelete
  6. This comment has been removed by a blog administrator.

    ReplyDelete
  7. Anonymous10:28 AM

    i was trying to run your program posted above. Coz i thought it wud help me do my assignment. How come that it terminates instantly as i enter the element and position, it doesn't show any changes at all. Can you help me on my assignment about adding and deleting an element. We only use simple syntax in the class like what u showed.

    ReplyDelete
  8. Anonymous10:38 AM

    hope you could respond to this. We are to do a program that will ensure the implementation of FIFO(the bsis of our program is like ordering a pizza that allocates 5 preparations as standby raw pizza stored in a bin. If the stocks became 2, then the crew should prepare anothe batch of raw pizza to maintain their max. standby raw pizza.) Also, the system should display the contents of the bin.. how am i gonna do it simpler way? we only use function to this, then of course array loops.. help me please! I badly need to know what to do. by the way i'm Mia

    ReplyDelete
  9. @ Anonymous,

    Just put a input-wait statement like "cin" or "getch" just after the "switch" block.

    This will halt the program until you press a key so that you can see the output.

    Hope this helps!

    ReplyDelete
  10. @ Anonymous (Mia),

    Check out this post of mine:
    Data Structures: Introduction to Queues

    Implement the stock of pizzas as in above. And every time you retrieve data from the queue check if if the stock is 2 (or whatever) and take action.

    Hope this helps! Don't hesitate to ask more if you need to.

    ReplyDelete
  11. Anonymous8:05 PM

    helpfull thanxzzzzzz :)

    ReplyDelete
  12. Anonymous10:05 PM

    Not working. theres a mistake in yo program. if i wanna put a number on 3rd position so when i show the array, its on 4th position as well as on 5th.

    ReplyDelete
  13. Anonymous9:09 PM

    how to delete the last element from an array using algo???

    ReplyDelete
  14. Anonymous2:35 AM

    rahad

    FOR I = (max-1) TO pos
    arr[I] = arr[I-1]

    arr[I] = num

    I did not anderstad this..

    ReplyDelete
  15. Anonymous5:50 PM

    thanks a lot its very helpful for the learners n it rely helped me....

    ReplyDelete
  16. hey,dude i like you post.pls, post more and more post to share imformation

    ReplyDelete
  17. awesome work arvind....... hats off... :)

    ReplyDelete
  18. it is so helpful thank you:)

    ReplyDelete
  19. It is helpful thanks a lot:)

    ReplyDelete

You are free to comment anything, although you can comment as 'Anonymous' it is strongly recommended that you supply your name. Thank You.

Please don't use abusive language.