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 do not have useful values. 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. Whenever there are filled indexes mixed with empty indexes, the array will be partially filled. 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 the most complex type of filled index layout for a partially filled array. While there are other ways to fill the indexes which would still make the array a partially filled array, Figure 1 represents the most general case you will need to handle.

//picture haer

Handling Partially Filled Arrays

When dealing with partially filled arrays, there are two important things that you should know how to do.

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

2. 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
}

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 track of the number of array indexes which are filled, you can quickly determine if new values can be added to the array.

Keeping track of the number of filled array indexes must take place in two parts of your program. You must first increment a 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[i] == null) //if the arrayIndex is defined to be empty
{
   stringArray[i] = newStringValue; //assign it the value of newStringValue
   valueCount = valueCount + 1; //increment the counter by one
}

Likewise, a block of code that removes a value from an array might look like this:

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

Putting it All Together

So for example, a block of code that inserts a value into any empty array index might look something like this:

if(valueCount == stringArray.length)
{
   System.out.println("The array is full!");
}
else
{
   for(int i = 0; i < stringArray.length; i++)
   {
      if(stringArray[i] == null)
      {
         stringArray[i] = newStringValue;
         valueCount = valueCount + 1;
      }
   }
}

String array an array of strings, i is a loop variable, newStringValue is an externally supplied value, and valueCount is the number of filled array indexes.

   stringArray[valueToRemove] = null;
   valueCount = valueCount -1 ;

if(stringArray[inputIndex] == null) {