Working with Partially Filled Arrays

COMP 1010 Home > More With Arrays > Working with Partially Filled Arrays

Introduction When working with arrays, you will come across situations where some array indexes contain a value, while others do not. These arrays are said to be 'partially filled'. This section will tell you why partially filled arrays occur, what a partially filled array looks like, and how to handle partially filled arrays.

{{{Body}}}

Why Partially Filled Arrays Occur

Partially filled arrays occur because once an array size it set, the array size cannot be changed. Therefore, we generally pick an array size that is large enough to hold the potential number of values that need to be stored. For example, if you usually need to store 20 values in an array, but sometimes you might need to store 40, then you need to make an array of size 40. However, this means that on average, half the array indexes will be empty.

Other reasons why partially filled arrays occur include cases where array indexes are only filled with values once certain conditions are met. For example, say you wanted to make a program to keep track of which numbers from 0 to 9 a user has typed in. You could create an array of size 10, and set the corresponding array index to filled for each number that is typed in (e.g. if the user types in 2, array index at 2 is set to filled). If the user has typed in 3, 7, and 9, then only the array indexes at 3, 7 and 9 will be filled and the array will be partially filled.

What a Partially Filled Array Looks Like

Figure 1 below shows an example of a partially filled array of size 10. The green indexes represent filled array values, while the white indexes represent empty array values. While there are simpler ways to fill the indexes which would still make the array a partially filled array (e.g. having all of the filled array indexes next to each other in a solid block), it is partially filled arrays such as these that you must be able to handle.

Handling Partially Filled Arrays

Handling partially filled arrays has many similarities to handling completely filled arrays, as you can iterate through them and access them just as you would any other array. The difference however, is that you must able to check to see if an array index is filled, and you may need to insert or remove index values from a partially filled array.

To deal with this added complexity, it is important to know how to do two things:

1. Know how to define an array index to be empty, based on the type of variable that gets stored in the array.

2. Know how to keep track of the number of filled indexes in the array.

Defining an Empty Index

The obvious value to choose when determining if an index is empty is the default value that a variable is assigned when the variable is created. Recall that when you create a String variable, its default value is null. Meanwhile, for ints, doubles, and chars, their default values are 0. Lastly, the default value for a boolean variable is false.

While using the default value may work well in some cases (using the default works well for Strings), the default value will not work for all cases. In particular, using the default value to define the empty index in an array of ints or doubles can usually lead to problems.

For example, suppose you have a program which stores an assignment mark out of 10 for a group of students in an array of type int. Each index in the array corresponds to one students mark. If you use the default value to define an empty index, it will be impossible to tell the difference between students whose assignments have not been marked, and students who got a mark of 0.

In order to avoid cases where the default value conflicts with possible array values, you need to initialize the array to something different. In the above scenario, the problem of 0 being both an empty index and an input value can be solved by initializing the array index values to -1. The code snippet below shows some example code as to what the initialization code might look like:

int [] gradeArray = new int[30] //gradeArray - there are 30 indexes, one for each student

for(int i = 0; i < gradeArray.length; i++) //go through all indexes
{
    gradeArray[i] = -1; //set each index to -1
}//end for loop

While initializing the array index values to -1 works well in the assignment mark example, it obviously wouldn't work if -1 was a valid input value. However, in the above example, we are following a more general rule: always define your empty index such that it can not be mistaken for a valid input value.

Keeping Track of Filled Indexes

When working with a partially filled array where array values are added and removed, your array may fill up to maximum capacity. By keeping a counter of the number of array indexes which are filled, you can quickly determine if new values can be added to the array.

For example, the block of code to ensure there is room in the array might look like this:

if(valueCount == stringArray.length) //if the counter (valueCount) is the same size as the array (stringArray)
{
    System.out.println("The array is full!"); //no insert can take place!
}//end if valueCount
else
{
   //here is where the insert code would go
}//end else

Keeping track of the number of filled array indexes must take place in two parts of your program. You must first increment the counter whenever you insert a value into an array, and decrement the same counter whenever you remove a value from an array.

A block of code that inserts a value into any empty array index might look like this:

if(stringArray[indexAdd] == null) //if stringArray at position indexAdd is defined to be empty
{
    stringArray[indexAdd] = newStringValue; //assign it the value of newStringValue
    valueCount = valueCount + 1; //increment the counter by one
}//end if stringArray

In contrast a block of code that removes a value from an array index might look like this:

stringArray[indexRemove] = null; //set the stringArray index at position indexRemove back to the defined empty index
valueCount = valueCount -1 ; //decrement the counter