April 15th, 2003, 05:26 AM
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?
April 15th, 2003, 09:49 AM
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:
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.
/* 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];
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.
April 15th, 2003, 05:07 PM
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.
April 15th, 2003, 05:25 PM
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."