SE250:HTTB:Array-based Lists:Operations
| Previous Page | Contents | Next Page |
Insertion
In Lab 3, we experimented with two methods on how to insert elements into an array, the "push" (arraylist_push) and "put" (arraylist_put) methods. Before the performance of these methods are discussed, the following is how the 2 methods are used:
<HTML>
<IMG SRC="http://www.geocities.com/braydondunnit/SOFTENG250/3.jpg" ALIGN=LEFT>
The Put Method
This method inserts a specified value at a particular index, by first shifting all preceding values 1 space to the right. In the diagram to the left, the X stand for a empty space. An element "d" is then added into index 3. This will push the previous elements at index 3, "e", and everything following it to the right, so now element "d" takes on the position of index 3.
void arraylist_put( ArrayList *alist, element_t elt, int index ) {
assert( index >= 0 && index <= alist->length );
if( alist->length == alist->capacity )
ensure_capacity( alist,
alist->capacity < ARRAYLIST_MIN_ALLOC ? ARRAYLIST_MIN_ALLOC
: (int)(alist->capacity * 2));
memmove( &alist->arr[ index + 1 ], &alist->arr[ index ],
(alist->length - index) * sizeof( element_t ) );
alist->arr[ index ] = elt;
alist->length++;
}
</HTML> Here is a tiny animated form of the picture above to give you an idea of how the PUT Method works. State4PlasmaTalk 15:13, 9 June 2008 (NZST)
<html>
</html>
<HTML>
<IMG SRC="http://www.geocities.com/braydondunnit/SOFTENG250/2.jpg" ALIGN=LEFT>
The Push Method
This method simply inserts a specified value into the end of the array. In the diagram to the left, the X's stand for a empty space. Assuming there is more than one empty space still left in the array, when the push method is called, it will add the value into the first free space of the array.
void arraylist_push( ArrayList *alist, element_t elt ) {
arraylist_put( alist, elt, alist->length );
}
The code shows how the push method makes use of the put method. This is because since the put method inserts a value into a specific index, calling the push method would be identical to calling a put method that inserts the value into the end of its list (alist->length).
</HTML> Here is a tiny animated form of the picture above to give you an idea of how the PUSH Method works. State4PlasmaTalk 16:36, 9 June 2008 (NZST)
<html>
</html>
Dynamically Resizing Array
We often do not know how many elements will be stored in an array, thus there would be no point creating an array with a fixed size because there is the chance of being not enough space. Therefore a dynmically resizing array is used.
When the array is filled up, a slot of memory that is larger than the initial array is allocated, the old array is then copied into this one, while the old one is freed up and just the new one is used. The diagrams following illustrate this:
<HTML> <IMG SRC="http://www.geocities.com/braydondunnit/SOFTENG250/4.jpg"> </HTML>
The capacity would continue to increase as the array keeps filling up, when it gets filled up again capacity would be 16, then 32, 64, 128..etc. The growth capacity determines how the array is resized, another way of implementing the growth capacity is using incremental instead, as shown below:
<HTML> <IMG SRC="http://www.geocities.com/braydondunnit/SOFTENG250/5.jpg"> </HTML>
The capacity would continue to increase, to 8, 10, 12, 14...etc.
It may be tempting to use say a growth capacity of *10000 or +100000, as this would be there would likely never be much need of the array to be resized. But this would also most likely be high wastage of memory, as it is also unlikely the space will ever get filled up. Instead that space will be preallocated and never be used, which is a waste.
Resizing Factor and Alignment
<html><img src="http://img26.picoodle.com/img/img26/4/6/13/f_ArrayListm_81b05df.gif"/></html>
Ensure Capacity
This function works by pre-allocating a specified number of array space before the start of the program. The code for it was as below:
void ensure_capacity( ArrayList *alist, int required_capacity ) {
if( required_capacity > alist->capacity ) {
alist->arr = realloc( alist->arr, required_capacity * sizeof(element_t) );
assert( alist->arr != (element_t*)0 );
alist->capacity = required_capacity;
}
}
For example, if the line of code: ensure_capacity(&myArray,1000) was called, then 1000 elements worth of array space will be allocated before the program starts. An alternative to calling ensure capacity is to alter the ARRAYLIST_MIN_ALLOC value. Both methods can produce the same results, the difference being that ensure capacity allocates at the start of the memory, while ARRAYLIST_MIN_ALLOC does so while its doing the first loop.
| Previous Page | Contents | Next Page |