Incremental Java
Removing and Shifting

Removing an Element

What does it mean to remove an element from an array? The problem with Java arrays (and arrays in many languages) is the array is fixed in length. This means you can't easily remove elements from an array.

To remove an array element at index i, you shift elements with index greater than i left (or down) by one element. For example, if you want to remove element 3, you copy element 4 to element 3, element 5 to element 4, element 6 to element 5.

In other words, you copy element j + 1 to element j, where j ranges from i (which is the element we want to remove) up to the length of the array minus 2. (Minus 2? Why 2? We'll see soon).

This is not the only way to remove an element. The way we're doing it preserves the "order" of the array. For example, think of the array as a line of students waiting to get tickets to an event.

Suppose one student leaves the line. We can think of the student being "removed" from the line. When this student is removed, all of the students behind should move up one step. For example, if the student standing 3rd in line leaves, then the student that's 4th in line becomes 3rd. The one that's 5th in line becomes 4th, and so forth.

There are other ways to remove elements from an array, which we'll discuss later on.

We'll treat index 0 as the front of the line and the index, length - 1, as the end of the line.

We're going to implement removing this element in two ways. We do it with loops and with arrcopy(). In general, you should prefer to use arrcopy(), since it's shorter and should run faster (though you probably won't notice).

Removing An Element Using Loops 

public static void removeElt( int [] arr, int remIndex )
{
   for ( int i = remIndex ; i < arr.length - 1 ; i++ )
   {
      arr[ i ] = arr[ i + 1 ] ; 
   }
}
Notice that we used arr.length - 1 instead of arr.length. Why?

What's the maximum value that i reaches, but where the condition still evaluates to true? Answer: the maximum value of i where we still enter the loop body is arr.length - 2.

Let's plug in arr.length - 2 for i and see what happens. This is basically what happens on the last iteration of the loop. 

 arr[ arr.length - 2 ] = arr[ (arr.length - 2) + 1 ] ;
which is just: 
 arr[ arr.length - 2 ] = arr[ arr.length - 1 ] ;
This is a valid assignment. We are copying the last element of the array (i.e., element arr.length - 1) to the next to last element (i.e., element arr.length - 2).

The Wrong Index

Suppose we had written the loop as: 
// Wrong limit on the loop index
for ( int i = remIndex ; i < arr.length ; i++ )
{
   arr[ i ] = arr[ i + 1 ] ; 
}
In this case, i goes up to arr.length - 1. In the last iteration, the assignment in the loop body is equivalent to: 
 arr[ arr.length - 1 ] = arr[ (arr.length - 1) + 1 ] ;
which is: 
 arr[ arr.length - 1 ] = arr[ arr.length ] ;
arr.length is larger than the largest valid index for arr. This causes an error in Java (called an exception). That's why the limit of the array is arr.length - 1 instead of arr.length - 2.

An Example

Suppose we have the following array:

Index 0 1 2 3 4 5 6
Value 2 3 5 7 11 13 17

If we remove the element at index 2 (which holds value 5), then, after running the code, the array looks like:

Index 0 1 2 3 4 5 6
Value 2 3 7 11 13 17 17

You'll notice that the values from index 3-6 gets shifted to the left by 1. However, the element at index 6 is still 17.

This kind of removing leaves the last element (i.e., the element at the maximum index) unchanged.

Is that OK? Usually, it's fine. You might be tempted to set it to 0 or some other value, but if there's no compelling reason to do so, you can leave it alone.

Copying Using arraycopy()

Rather than use a loop, we should use arrcopy(). The code is much simpler: 
public static void removeElt( int [] arr, int remIndex )
{
   int numElts = arr.length - ( remIndex + 1 ) ;
   System.arraycopy( arr, remIndex + 1, arr, remIndex, numElts ) ;
}
We want to copy starting at remIndex + 1 and copying to remIndex (which effectively, shifts the values left by 1).

The hard part is computing how many elements we want to copy. We know that there are arr.length elements total. There are remIndex + 1 elements from index 0 to index remIndex which are not going to be shifted. So, we subtract from arr.length to find out the number of elements that are going to be shifted.

It's useful to learn how to compute quantities like numElts.

To make sure the formula works, assume the array size is 5, and that remIndex is 2. This means, we need to shift elements 3 and 4, which are two elements. The formula says 5 - (2 + 1) which is indeed 2.

Formalizing "Removing" an Element

When we say we want to remove an element, what to we really mean?

This isn't nearly as straight-forward as it sounds. If we define what it means to remove an element, then it makes it easier to see what that means.

Here's one way to define it.

Because the array's length doesn't change, then removing an element really means we ignore elements (starting at the largest index).

The main problem with this definition of removing an element is that we really can't tell an element has been removed.

Later on, we'll considered two ways to solve this problem. (One way is to create a new array who length is reduced by 1. The other way is to use an instance variable that keeps track of the number of valid values in the array).

Removing Without Order-Preservation

When we removed element 2 in the previous example, we kept the ordering. That is, the values in elements 3 through element 6 (inclusive) which are values 7, 11, 13, and 17 are still in that order after we remove value 5.

When we removed the value, we made sure of two things:

What if we didn't care about the order? What if we only wanted to make sure that: In that case, we can greatly simplify the code. We just copy the value of the last element (i.e., at element 6) to the element we want to remove (i.e., element 2).

Code 

public static void removeElt( int [] arr, int remIndex )
{
   arr[ remIndex ] = arr[ arr.length - 1 ] ; 
}
This array doesn't change if remIndex is arr.length - 1, but that's fine. It may seem weird, but we'll only worry about removing any element other than the last element.

Resulting Array

After running the code, the array looks like:

Index 0 1 2 3 4 5 6
Value 2 3 17 7 11 13 17

Notice that element 6 is still unchanged. However, element 2 has been overwritten with a new value.

If we use the analogy of students standing in the line, we've done the equivalent of letting the last person in line move to the location of the student who left the line.

While moving students may not be more efficient in the real world, it's much more efficient when writing a program. We only copy the value of one element to another. We don't need a loop.

Trace It!

Even though I've told you what the array looks like after the code is run, you really, really, (really) should trace the code to see that it's correct (it may not be!). Right now, tracing the code on paper is the best way for you to see how a program behaves.