Array algorithms for deletin elements

• About algorithms for deleting (values of) array elements
• Deleting all values from an array
• Deleting a specific value from an array (the first or last found)
• Deleting a specific value from an array at all found positions
• Deleting the most recently entered value from an array
• Most common errors

In some situations, it is necessary to remove (delete) some values from an array. Whether they are invalid or incorrect values, those values should no longer be present in the array.

Unlike the situation where elements’ values are replaced — where there is an “old” and a “new” value (i.e., the value to be replaced (“old”) and the value that replaces the old one (“new”)) — in deletion there is only the “old” value, and the new value can be a neutral or default value (e.g., 0 or -1), or the other elements of the array can be shifted so that they overwrite the deleted element.

Therefore, deleting values of array elements usually does not mean physically removing the element from the array and reducing the array’s length (capacity) by one, but only:

• setting the value of that element to some initial (neutral) value
• and/or shifting the subsequent elements of the array one position “to the left,” so that no “empty” space remains where the deleted value was.

As with replacing element values, the “old” value can be:

• some specific value (for example, delete the number 500 or the letter ‘A’)
• or a set of values expressed by some rule (for example, deleting all numbers in the array that are greater than 300)

Deletion can sometimes mean deleting all elements of the array (regardless of their values). The effect is as if working with a newly initialized array, and often in such cases a new array of the same characteristics (element type and capacity) is initialized.

Deletion can also mean deleting all elements of the array that have the “old” value. For example, delete all incomes greater than 40,000 dollars.

In some cases, deletion can mean deleting the value of only one element (which has the “old” value), for example, the first or last found such element in the array. For example, delete the first found profit (from the array of profits) that is greater than 3,000 dollars.

Finally, deleting can mean deleting the most recently entered value. It involves memorizing which value was most recently entered (to the array) and to what position, and then removing it. If an (array) element helper counter is used, this is an easy thing to do as the counter value helps find the exact position of the value that had been entered last.

As stated, simple deletion often implies shifting the subsequent elements of the array (those after the deleted element) one position forward, i.e., “to the left” — which is a version of the algorithm covered in the lesson on replacing values of array elements.

Algorithmically, when deleting values of array elements, a FOR-EACH loop cannot be used, and other characteristics of these algorithms are:

• It deletes the value of one or more array elements — by replacing the “old” value of the element with a “neutral” value or by shifting other array elements to that position.
• The algorithm stops as soon as a value is deleted only if deleting the value of a single array element. If deleting multiple elements, the algorithm does not stop until the whole array is traversed. This may involve multiple shifts of elements.
• The algorithm typically includes finding the array element(s) containing the “old” value.

In some situations, it is necessary to delete all values from the array and start over — with an empty array. In this case, all values must be deleted regardless of what those values are.

This can be done in two ways:

1. By iterating through the existing array and setting the values of its elements to the default value (e.g., 0 or false) or a “neutral” value (e.g., -1) that represents a “free spot” in the array.
2. By initializing a completely new array with the same characteristics — same capacity, same element type. Upon initialization, Java will anyway set all array element values to the default value for that element type.

In both cases, if a counter of array elements is used, it must be reset to zero. Actually, if the rules for introducing and using an element counter are strictly followed, and if it is not important to physically remove these values, it is enough to just reset the counter to zero. The array will still contain all the values it had, but because the counter is reset to zero, inserting into the array will start from the beginning, without considering the “old” values.

Although both methods are always applicable, which one is better for a particular situation depends on the array type. For relatively short arrays (small capacity) where deletion is done by setting elements to the default value, initializing a new array is probably simpler and faster. On the other hand, if the array is longer, if the array needs to stay at the same memory address, or if deletion is done by setting to a value that is not default, the first option (keeping the existing array but deleting its elements) is probably better.

Example 1

Create a class PatientTemperatures that has:

• An attribute temperatures which is an array holding multiple measurements of patients’ body temperatures in a hospital (e.g., 36.4). The array should be initialized immediately with a capacity of 10.
• An attribute counter which represents the count of elements in the array. The initial value is zero.
• A method enterTemperature that inserts a new temperature at the first free position in the array, but only if there is space in the array and the entered temperature is within the range from 33.5 to 41.5 degrees. Otherwise, the method prints the message “ERROR” on the screen.
• A method deleteAllTemperatures which deletes all temperatures from the array by initializing a new array with the same characteristics. Of course, the counter should also be reset to zero.
• A method deleteAllTemperatures2 which deletes all temperatures from the array by setting each element to the default value for the double type. Again, the counter should be reset to zero.
• A method deleteAllTemperatures3 which deletes all temperatures from the array by resetting the counter to zero.
• A method print that prints all elements of the array in one line. If there are no temperatures entered, it prints “The array is empty” on the screen.

Create a class TestPatientTemperatures which in the main method creates one object of the class PatientTemperatures and inputs the temperatures 36.5, 39.1, and 35.7 into it. After that, all temperatures should be printed, then all temperatures deleted, and printed again.

In the method deleteAllTemperatures, a completely new array within the temperature attribute is initialized (whose elements have the value 0.0), and the old array that contains temperatures 36.5, 39.1, and 35.7 is deleted (the Garbage Collector frees that memory space). The capacity of the new array is the same as the old one, and the element type is also the same. The counter gets the value zero, so it is considered that no temperatures are entered, and new entries start from the first position in the array onward.

In the method deleteAllTemperatures2, using a FOR loop, all elements of the existing temperature array are set to 0.0. In this method, no new array is created; instead, the elements of the existing array are “deleted” one by one. Thus, the temperature array remains at the same memory location; no new array is made. Again, since the counter is set to zero, it is considered that there are no entered temperatures, and new entries start from the first position onward.

However, what happens if the values of the array elements are not really “deleted,” but only the counter is reset to zero? This solution is shown in the method deleteAllTemperatures3. The temperature array still contains the values 36.5, 39.1, and 35.7, but since the counter is set to zero, those values are not considered at all: input starts again from the first element (future inputs will overwrite these three “old” temperatures), and printing elements happens for indices from zero to the counter value, so at first it shows the array as empty, and later only the newly entered temperatures are printed.

Sometimes it is necessary to go through an array and delete the value of only one element. The most common way to delete is to remove the first (or possibly the last) element of the array that has the “old” value. However, depending on how the array is used, there are different versions of these algorithms:

• Deleting the value of an element at a precisely defined position (the whole capacity of the array is always used, and it is exactly known what each element of the array represents, e.g., an array of bus seats or an array of monthly profits). Here deletion is done by setting the value of the requested element to the default or “neutral” (initial) value.
• Deleting the value of the first/last element of the array that has the “old” value (a search is performed for the first such element from the beginning or the last such element from the end of the array). Here deletion can be done by setting the value of the requested element to the default/“neutral” value, but also by shifting the elements “to the left” and reducing the counter by one.

Example 2

Create a class MonthlyTemperatures that has:

• An attribute monthlyTemperatures which is an array of average temperatures in a city (e.g., 23.1) for each of the 12 months in a year. The first element of the array refers to January, the second to February, etc., and the last to December (e.g., 123.44). The array should be initialized immediately upon declaration.
• A constructor that takes as a parameter an array of exactly 12 elements representing the monthly temperatures. This constructor copies that array into the monthlyTemperatures attribute.
• A method deleteTemperature which deletes an existing temperature for a specific month by setting the value of the corresponding array element to 0. The only parameter of the method is the month number. Note that the month numbers range from 1 to 12, while the indices range from 0 to 11.
• A method print that prints all monthly temperatures using a FOR loop.

Create a class TestMonthlyTemperatures which in the main method creates an object of the class MonthlyTemperatures with arbitrary temperatures for each month. Then it is necessary to delete the temperature for February and print all monthly temperatures on the screen.

The algorithm for deleting the value of an element at a precisely defined position is found in the method deleteTemperature. Since the entire array (full capacity) is used here, and it is exactly known which element corresponds to which value (each element corresponds to one month in the year), searching and finding an element with the “old” value is not necessary, and thus no FOR loop is needed. The value of the element at the precisely defined position is deleted — in this case, the month number minus one represents the index of the element in the array where the “old” value should be replaced with zero. Zero here represents the default value, although it could be set to some “impossible” value, e.g., -1000 (lower than absolute zero, which is -273.15 degrees Celsius). Moreover, shifting the other elements one place “to the left” should not be done here, as that would disrupt the data about which temperature corresponds to which month.

In many cases, the array is not used to full capacity, so instead of deleting the value of an element at a precisely defined position, the array is first searched for an element that has the “old” value. Variations include finding the first or last such element in the array, and the method of deleting the value depends on whether an element counter is used.

If no element counter is used, the “old” value is replaced with the default or initial value. If an element counter is used, deletion is done by shifting elements left from the position where the value to be deleted is found and onward. Of course, the element counter should then be decreased by one because the array contains one less value after deletion.

Example 3

Create a class ProductPrices that has:

• An attribute prices which is an array containing prices of multiple products (e.g., 123.44).
• A constructor that takes an array of prices as a parameter and assigns it to the prices attribute.
• A method deleteFirst which takes an old price as a parameter and finds the first element in the array (starting from the beginning) that has that old price. The method deletes the value of that element by setting it to -1 (an impossible value for a price).
• A method deleteLast which takes an old price as a parameter and finds the last element in the array (starting from the end) that has that old price. The method deletes the value of that element by setting it to -1 (an impossible value for a price).
• A method print which prints all elements of the array on the screen.

Create a class TestProductPrices which in the main method creates an object of the ProductPrices class containing five prices: 300.0, 200.0, 300.0, 200.0, and 500.0. Then it deletes the first element of the array with the price 200.0 and the last element of the array with the price 300.0. Finally, it calls the print method.

The deleteFirst method deletes the old price for the first element in the array that contains that old price. A FOR loop goes through all index values of the array (0 to length-1), and within a nested IF statement, it checks whether the current element contains the “old” price. If it does, the “impossible” price -1 is assigned to that element of the array, and the loop is terminated with a break statement (the whole method can also be stopped with a return statement). If you think about it, you can conclude that this algorithm is very similar to the algorithm for replacing an element at the first found position. The only difference is that instead of a new value (new price), a default value (or in this case “impossible” value) is assigned to the place in the array, thus “deleting” the old price.

It is very important that the method stops immediately after the replacement, because otherwise the search for the “old” price and deletion would continue, meaning the price -1 would be entered instead of the “old” price in all places where the “old” price is found.

In the deleteLast method, a nearly identical algorithm is presented, only this time it replaces the “old” price with -1 in the last element of the array that contains the “old” price. The only difference is that the FOR loop iterates through the indices in reverse order (from length-1 to 0), so the search for the first element with the “old” price starting from the end of the array actually turns into a search for the last such element starting from the beginning of the array. This algorithm is also very similar to the algorithm for replacing the value of the last found element of the array.

It should be noted that introducing an element counter in this case leads to a significant change in the previous algorithms. Although the search still needs to be performed, it now goes from 0 to counter-1 (or reverse for the last found element), but deletion is performed by shifting elements “left” and reducing the counter value.

Example 4

Create a class ProductPrices2 that has:

• An attribute prices which is an array containing prices of multiple products (e.g., 123.44). The array should be initialized immediately with capacity 100.
• An attribute counter which represents the number of actually entered prices in the array. Initial value is zero.
• A method insertPrice which takes a new price as a parameter and inserts it into the first free spot in the array, only if the price is zero or greater and if there is space in the array. Otherwise, it should just print the message “ERROR” on the screen.
• A method deleteFirst which takes an old price as a parameter and finds the first element in the array (from the start) that has the old price. The method deletes that element by shifting all elements to the right of it one position to the left.
• A method deleteLast which takes an old price as a parameter and finds the last element in the array (first from the end) that has the old price. The method deletes that element by shifting all elements to the right of it one position to the left.
• A method print which prints all elements of the array on the screen.

Create a class TestProductPrices2 which in the main method creates an object of the ProductPrices2 class containing five prices: 300.0, 200.0, 300.0, 200.0, and 500.0. Then it deletes the first element in the array that has the price 200.0 and the last element in the array that has the price 300.0. Finally, it calls the print method.

The deleteFirst method deletes the old price for the first element in the array that contains the old price. A FOR loop goes through all index values of the array (0 to length-1), and within a nested IF statement, it checks whether the current element contains the “old” price. If it does, the deletion is done by shifting all remaining elements one place “left.” Here the method shiftLeft is called, which is introduced into the class exactly for this reason since this shifting will also be needed in the deleteLast method.

The shiftLeft method takes as a parameter the index of the element to be deleted and shifts elements with higher indices (“right” of the entered position) one place to the left, thereby deleting the element at the given index. For example, starting from the array in the task, shifting left would look like this:

It is important to note that since only part of the array is shifted left here, there is no need to introduce a temporary variable to remember the value of the first element and later assign it to the last position in the array.

Finally, after shifting left, the counter is decreased by one and the loop is terminated with a break statement (the whole method can also be stopped with a return statement).

It is very important that the method stops immediately after the deletion, otherwise the search for the “old” price and deletion would continue, meaning the price -1 would be inserted instead of the “old” price in all places where the “old” price is found.

The deleteLast method uses a very similar algorithm, but deletes the “old” price in the last element of the array that contains the “old” price. The only difference is that the FOR loop iterates through indices in reverse order (length-1 to 0), so the search for the first element with the “old” price starting from the end of the array actually turns into a search for the last such element starting from the beginning of the array. The shift left operation remains the same (it does not move “right,” etc.), and is done starting from the position of the element to be deleted onward.

Deleting a specific value from an array at all found positions is, algorithmically speaking, almost identical to deleting a value from the array at the first or last found position. The only important difference is that neither break nor return statements are used to stop deletion after the first (or last) element with the “old” value is found.

There isn’t even a difference in cases when the entire capacity of the array is used, and it is exactly known what each element represents compared to other cases. It is still necessary to use a FOR loop and go through the entire array looking for the “old” value.

In cases where a counter is used and deletion is done by shifting the subsequent elements of the array “to the left,” the only difference is omitting the break or return statement, so shifting “left” is performed every time an element to be deleted is found, and the element counter is decreased by one each time an element is deleted.

Sometimes the goal isn’t to delete a specific value from the array, but simply to delete the value that was last entered into the array. For example, the last input for temperature was incorrect and should be deleted.

If the array is used to full capacity, and it is known what each element represents, then it is necessary to know at which position the last value was entered (e.g., number of seats in a theater) to perform deletion. The algorithm then reduces to a simple deletion from a precisely defined position, as in the class MonthlyTemperatures from example 2.

If a counter of array elements is used, and the array is filled sequentially from the first element onwards, then the last added value is at the last position in the array (index is counter-1), so deletion boils down to decrementing the counter by one. In that case, it is not even necessary to know what that value was; it is only important that the counter is not zero (that the array is not empty).

If no counter is used in the array, then it is necessary to know which exact value was last entered to delete it from the array by searching for that value and deleting it from the first or last found position. If the array contains duplicates, whether to delete from the first or last occurrence (or maybe all occurrences) depends on how values are entered into the array. Algorithms for such deletion are given in example 3 in the class ProductPrices.

Some of the most common errors related to algorithms for deleting array element values, which are not syntax errors but affect the program’s behavior, include:

• Using a FOR-EACH loop to delete values from array elements, for example:

Instead of correctly (only a FOR loop should be used):

• Forgetting to break the loop after deleting the value of the first or last element of the array that has the “old” value, i.e., forgetting to put a break or return statement, for example:

Instead of correctly:

• When deleting values for all elements of the array that have the “old” value and using an element counter, forgetting to decrement the element counter after deletion:

Instead of correctly:

• When deleting values for all elements of the array that have the “old” value and using an element counter, iterating through elements up to the full length of the array (length-1) instead of up to the counter (counter-1):

Instead of correctly:

• When deleting a value at a precisely defined element in the array (when the array is used at full capacity), forgetting to decrement the ordinal number by one to match the index of that element in the array (e.g., 1 for January instead of the index which is 0):

Instead of correctly:

• When shifting elements in the array to the left, forgetting to consider that the counter for the FOR loop should go from 0 to counter - 2 (not to counter - 1) because each iteration works with the current element (index i) and the next one (index i + 1):

Instead of correctly: