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?
Thanks
:)
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:
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.
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."
http://analyser.oli.tudelft.nl/