2.2.2 Resizing

The ADT of an array should not be constrained by a capacity limited at creation time. This feature is well supported by many scripting languages, such as Perl and PHP. In other words, after an array is created, a program can refer to any element in it. Some implementations makes sure all elements in an array has default values, while others just ensures there is storage for elements.

Regardless of whether elements have default values, the difficulty is the reallocation of memory. In C, we can use the subroutine malloc to request memory. When an array increases in size, we allocate for a new and bigger array, copy everything from the existing array, then free the existing array.

This also means that resizing is an expensive operation. It is expensive because of all the data copying. An even more important impact of frequent resizing is memory fragmentation. Memory fragmentation occurs when memory chunks of different sizes are allocated and deallocated frequently.

One approach to resize an array is to always double the capacity when needed. Some approaches also shrinks the capacity of an array by half when it is okay to do so. The following is a sample verbal log of how an array adjusts its capacity:

• Array creation, initial capacity is 16. Number of elements in use is 0.
• Index element 4. No problem. Number of elements in use is 5.
• Index element 12. No problem. Number of elements in use is 13.
• Index element 22. The array needs to get larger. Doubling the capacity to 32 solves the problem. Number of elements in use is 23.
• Index element 100. The array needs to get larger. Doubling gets to 64 elements. Double again to get to 128 elements. Number of elements in use is 101.
• Index element 32. No problem.
• Manual resize to 20. Instead of actually reducing the capacity to 20, the capacity is reduced to 32 (from 128). The number of elements in use is reduced to 20. The array internally tracks the number of elements in use (as opposed to the capacity).

Besides doubling/halfing, there are other techniques to change the capacity of an array. Such techniques include the use of linked lists, trees and maps. However, these techniques are quite advanced compared to the intended level of skills for this module.