Removing 3D points from an array in constant time in c

Question

I have a function here which removes 3D points from an array in O(n). But when I ran the code, once it got to around 16000 points in the array, it ended up taking way too long to remove. I want to make my remove code faster. How would I go about changing my code so that it would remove in constant time?

Here is the struct that I've created:

typedef struct point
{
  double x, y, z;
} point_t;

typedef struct 
{
  size_t len;
  point_t* points;
  size_t reserved; 

} point_array_t;

Here is my function to remove the 3D points in the array:

int point_array_remove( point_array_t* pa, unsigned int i )
{
    assert( pa );
    if( i >= pa->len )
        return 1;
    pa->points[i] = pa->points[pa->len-1];
    while( i < pa->len-1 )
    {
        pa->points[i] = pa->points[i+1];
        i++;
    }
    pa->len--;
    return 0;
}

Answer 1

The problem is you're moving a linear number of items to close the gap. If that's necessary, you can't avoid the linear time requirement.

However, if the order of the elements in the array isn't important, you could just move the last element directly into the gap. This means you're only moving one element - a constant amount of work that can be done in constant time.

There's still a problem, though, as you'd still need to search for that last element and that would take linear time. But if you knew the size of the array you could go directly to that last item in constant time - so you need to keep track of that size. Store it in an integer variable, update it when the array size changes etc.

One little issue to watch out for - what if the item you delete is the last item.

EDIT

If the above isn't acceptable, all you can do is replace the array with a different data structure. The classic data structure for constant-time inserts and deletes (provided you have already found the correct item/location, and preserving the order of the remaining items) is a linked list.

Linked lists have costs compared to arrays, so if when you're ready for it, one option is to combine linked lists and arrays - have a linked list of small arrays. The small arrays will have some fixed maximum size, and will know how many elements they contain. Inserts and deletes are constant time because each small array has (at most) some constant number of elements to move - the maximum size of that array (in this case not cheating).

So your node type might look like...

typedef struct
{
  chain_node_t *next;
  chain_node_t *prev;
  unsigned      num_in_this_chunk;
  point_t point [CHAIN_CHUNK_MAX];

} chain_node_t;

I've probably got this slightly wrong due to being too used to C++ rather than C, but it should be easy to fix.