How do you insert and delete elements from an array in dynamic memory allocation?

Answer 1

To delete an array element you must create a new array with one less element, then traverse both arrays, copying elements from one to the other, but skipping over the element you want to delete. Once all elements are copied, you can release the original array. A slightly more efficient method would be to move the empty element to the end of the array and then re-allocate the entire array with one less element, using the realloc() command.

To insert a new element, create a new array with one additional element. Then traverse both arrays, copying elements from one to the other. The original array can then be deleted, and the new data can be placed at the end of the new array. Again, the realloc() command is the most efficient method of doing so. However, if the array must be sorted, you must compare the new data with each element prior to copying, and insert at the appropriate point. Once inserted, the remaining elements can be copied into place and then the original array can be released.

Due to the reallocation and copying of elements, this approach is highly inefficient. You can alleviate some of the re-allocations by allocating several empty elements at a time, and keeping track of how many empty elements there are available for insertions. This can be achieved by keeping all empty elements at the end of the array, and maintaining a count of those elements. To delete an existing element, shunt data to the right one place to the left to remove the gap. And if the number of empty elements exceeds a given minimum, re-allocate the array to remove redundancy.

Although this is a better approach, it is still quite inefficient, particularly if the array is large. If the array is small and there are few insertions and deletions, then it probably won't matter too much, but for larger arrays with many insertions and deletions to cater for, a far better approach would be to use a linked list. This makes better use of memory, as the list can expand and contract dynamically without the need to copy any elements (or nodes) whatsoever. Some additional memory is required to maintain the links between the nodes but, unlike an array, no memory is ever wasted.