#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    2
    Rep Power
    0

    deletion from an array in C


    Hey... I am newbie and have a question.
    How do you delete any element from an array? Is shuffling every element along the only way... or is there more of an efficient method?
    Thanks
    :)
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,254
    Rep Power
    2222
    In an array, that's about the size of it. Of course, you can do it in a for-loop, so coding it is not so painful:
    Code:
    /* index is the index of the item to be deleted
        ARY_SIZE is the array size; indices run from 0 to ARY_SIZE-1
    */
    for (i=index; i < (ARY_SIZE-1); i++)
        ary[i] = ary[i+1];
    And to insert an item, you do the reverse: shift the elements to the right to make room for the new item. But be sure to start from the end and work to the left.

    For small collections of small data (no humungous structs), this is not too inefficient. When your list gets much larger, then a linked list would be preferable. Of course, the code for that is more complex, so you need to consider the trade-offs. Though if you move on to C++, the Standard Template Library (STL) would be available to help you create the more complex data structures.

    BTW, even if you are working with arrays of huge structs, there's a more efficient way than shifting all that data left or right. Declare the array as an array of pointers to structs. Then create the structs dynamically (with malloc in C or new in C++) and insert the pointer into the array. Now when you are shifting the array's elements around, you're only moving the pointers and not the data itself.
  4. #3
  5. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    A faster way to shuffle the elements during delete / insert is to use pointers, so the CPU doesn't have to recompute the index each time.

    Basically, a linked list would be faster for inserting / deleting elements, at the trade off for a random access to one. An array is very quick at a random index access in comparison to a linked list. So, you have to think about which operation is performed more often, if you are worried about speed.
  6. #4
  7. *bounce*
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2002
    Location
    Delft, The Netherlands
    Posts
    514
    Rep Power
    42
    Another approach involves the use of "markers". Instead of re-arranging the array when you delete an element, you just mark the spot as being unused.

    Of course, there's a chance that there's no value that can be used as a marker. For instance, with an array of chars, you might actually need all 256 distinct values, and not have one left to use as a marker.

    Arrays of pointers don't have this problem, since you can always use the NULL value for that.

    Just my $0.02.
    "A poor programmer is he who blames his tools."
    http://analyser.oli.tudelft.nl/

IMN logo majestic logo threadwatch logo seochat tools logo