0

When ever I read differences between linked lists & arrays, I always saw on lot of sites that insertion of an element in to an array is very costly because we need to do lot of data moving. But one thing I always didn't understand is how we can create space for one more element while inserting, as the size of the array (or number of the elements in array) is fixed at compile time. Can any one please let me know how we can insert element into a fixed size array. And is there any concept called Dynamic array in C?

kadina
  • 5,042
  • 4
  • 42
  • 83
  • http://stackoverflow.com/questions/2937409/resizing-an-array-with-c – Niloct Apr 11 '14 at 18:04
  • 1
    Either there is already extra space in the array or it will have to be resized before the insertion. – ooga Apr 11 '14 at 18:05
  • [Here](http://happybearsoftware.com/implementing-a-dynamic-array.html) is a tutorial about Implementing a dynamically sized array in C – cycopepe Apr 11 '14 at 18:05

4 Answers4

1

In C, there is no "native" concept of a dynamic array. You can create fixed length arrays via declaration:

int myArray[10];

Or dynamically via malloc/calloc:

int* myArray = malloc(10, sizeof(int));

The reason that "inserting" into a fixed array is so costly, is because you need to:

  1. Create a new, bigger array.
  2. Copy the old data into the new array.
  3. Insert the new element into the appropriate spot in the new array.

Your options are to create your own storage mechanism (ie: stack, queue, linked list), or implement an existing implementation of such.

Cloud
  • 18,753
  • 15
  • 79
  • 153
1

There is, indeed, the concept of a dynamic array. You just need a pointer and to reserve memory of the size you want with malloc. You need also to keep track of the number of elements you have.

int* my_array = malloc(10 * sizeof(int));
int n_used_elements = 0; // Need to keep track of the used elements and the size
int my_array_size = 10;  // reserved size

However, when you exceed the number of elements in your array, you need to reserve the whole thing again and copy it again to the new reserved memory, which is also costly.

Usually, when using arrays for dynamically increasing and shrinking amounts of data, one of the most typical approaches goes with the following idea: when you exceed the size of your array, you double the size (i.e. you do not just add one more, but reserve for an extra number of elements in prevision you might need to increase the size of your array again), copy the elements of the old small one and keep going. Whenever you exceed, you double the size. On the other hand, to avoid wasting memory, if you have less than a certain amount of elements occupied, sometimes you half the size of the array.

Inserting a new element in an array is very costly because you have to shift all the elements after the inserted index one position to the right. The bigger the array, the bigger the cost of it (i.e. it is proportional to the size of an array). And you always need to consider the possibility of exceeding the size of the vector.

cnluzon
  • 1,054
  • 1
  • 11
  • 22
  • 1
    Note that on PC hardware, doing linear memory copy can be quite fast, so if you need to iterate through a linked list from start, following pointers through many cache misses, it's quite possibly faster to insert to array with memory copy. So I'd hesitate to say *"it is usually more efficient to use lists."* – hyde Apr 11 '14 at 18:24
  • you're right about that, it might be a little misleading, since it totally depends on what you want _exactly_ you want to do. I will edit that. – cnluzon Apr 11 '14 at 18:25
  • This is not a dynamic array, it is a **dynamically allocated** array. A dynamic array can grow/shrink in the number of elements within the array. What you're proposing is exactly what I noted, which is a dynamically allocated array, which must be completely copied into another dynamically allocated array. – Cloud Apr 11 '14 at 20:44
  • I was talking about a possible implementation of what was asked. See, a dinamically allocated array can be used to *implement* a dynamic array. I thought @kadina got the concept but wanted some idea of how this could be implemented. – cnluzon Apr 11 '14 at 21:47
0

There's no built-in dynamic array in C. If you need a dynamic array, you can't escape pointers.

typedef struct {
  int *array;
  size_t used;
  size_t size;
} Array;

void insertArray(Array *a, int element) {
  if (a->used == a->size) {
    a->size *= 2; // double the size when exceeding the size of the array
    a->array = (int *)realloc(a->array, a->size * sizeof(int));
  }
  a->array[a->used++] = element;
}

Check out this post for more details and examples.

Community
  • 1
  • 1
herohuyongtao
  • 49,413
  • 29
  • 133
  • 174
0

If you have an array like int a[10]; (and you use all 10 elements) it is not possible to resize it to fit another element.

For dynamic size you have to use a pointer int* a;, allocate memory youself with a = malloc(10*sizeof(int)); and take care of moving around elements when you insert in the middle.

Danvil
  • 22,240
  • 19
  • 65
  • 88