Incremental Java
Swapping Two Elements in an ArrayList

Swapping Two Elements in an ArrayList

Let's say you wanted to swap two elements. Swapping elements means to switch the contents of two elements. Let's see what this means, with an example.

Suppose the list looked like:

Index 0 1 2 3 4
Value "ape" "bat" "cat" "dog" "elk"

You wanted to switch the string at index 0 with the string at index 4 (i.e., switch "ape" for "elk"). After the swap, it looks like:

Index 0 1 2 3 4
Value "elk" "bat" "cat" "dog" "ape"

How would you write Java code that would do this swap?

First Attempt

Let's try this: 
public void swap( ArrayList list )
{
   list.set( 4, list.get( 0 ) ) ;  // LINE 1
   list.set( 0, list.get( 4 ) ) ;  // LINE 2
}
Let's look carefully at LINE 1. 
   list.set( 4, list.get( 0 ) ) ;
Recall that arguments must be evaluated first. In particular, we need to evaluate the second argument list.get( 0 ). This retrieves the object (handle) at index 0. This is "ape".

Thus, the method call is effectively: 

   list.set( 4, "ape" ) ;
This sets the object at index 4 to "ape".

At this point, list looks like:

Index 0 1 2 3 4
Value "ape" "bat" "cat" "dog" "ape"
As you can see, this is a problem. We want to swap "ape" with "elk", but now "elk" is gone. (Although this doesn't affect anything, element 0 and element 4 now share a handle to the "ape" object).

If we run next statement, 

   list.set( 0, list.get( 4 ) ) ;
and evaluate it: 
   list.set( 0, "ape" ) ;
we end up with the same list as above. In any case, we've lost "elk", and we need to figure out how to avoid this.

Second Attempt

In order to avoid this, we need to save "elk" before we overwrite it with "ape". To do this, we need a local variable. 
public void swap( ArrayList list )
{
   Object temp = list.get( 4 ) ;  // Save "elk"
   // MORE CODE TO BE ADDED
}
We fetched a copy of the handle to "elk" and put it in a local variable called temp. We know that "elk" is a String. In fact, temp has a handle to a String object. Why didn't we cast it to a String? We don't need to! All we plan to do is put this string at index 0. We don't intend to use it as a String (not yet, anyway).

Now that we've saved "elk", we can set the object at index 4 (which is currently holding "elk") to the object at index 0 (which is currently holding "ape"). 

public void swap( ArrayList list )
{
   Object temp = list.get( 4 ) ;  // Save "elk"
   list.set( 4, list.get( 0 ) ) ; // Put "ape" at index 4
   // MORE CODE TO BE ADDED
}
So far, list still looks the same as before:
Index 0 1 2 3 4
Value "ape" "bat" "cat" "dog" "ape"
That's OK. We've lost "elk" in the ArrayList, but we have a variable, temp holding onto it. Now we update index 0 of the ArrayList with temp. 

public void swap( ArrayList list )
{
   Object temp = list.get( 4 ) ;  // Save "elk"
   list.set( 4, list.get( 0 ) ) ; // Put "ape" at index 4
   list.set( 0, temp ) ; // Put "elk" at index 0
}
Now list is the way we wanted it.
Index 0 1 2 3 4
Value "elk" "bat" "cat" "dog" "ape"

Third Attempt

The second attempt worked, but it's really not a great method. It specifically swaps index 0 and index 4. It would be much better if we could swap any two indexes in the ArrayList. This is a choice we want the object user to make. This means we should add two parameters which the user can set to decide which two elements to swap. 
public void swap( ArrayList list, int firstInd, int secondInd )
{
   Object temp = list.get( firstInd ) ;
   list.set( firstInd, list.get( secondInd ) ) ;
   list.set( secondInd, temp ) ;
}
We can even do a little better because set() returns back the original element which it is about to overwrite. For example, if "ape" was at index 0, and we're about to overwrite it with "elk", the set() method returns "ape".

This allows us to write a shorter version: 

public void swap( ArrayList list, int firstInd, int secondInd )
{
   Object temp = list.set( firstInd, list.get( secondInd ) ) ;
   list.set( secondInd, temp ) ;
}
Either this version or the previous one is acceptable.

If we made a method call and wanted to swap the elements at index 0 and index 4, we'd write: 

foo.swap( list, 0, 4 ) ;
This is an unusual method call because, frankly, we don't use the object foo. We don't refer to any instance variables, only parameter variables and local variables. In general, any method that doesn't use instance variables should be static.

Thus, it's better to write: 

public static void swap( ArrayList list, int firstInd, int secondInd )
{
   Object temp = list.set( firstInd, list.get( secondInd ) ) ;
   list.set( secondInd, temp ) ;
}
If this were in class Foo, we'd write the method call as: 
Foo.swap( list, 0, 4 ) ;
Looks a lot like the version we had before, right? Except this time, Foo is a class. In the previous method call, foo was an object.

Swapping integers

Here's an example of swapping with primitive variables. 
int temp = x ;
x = y ;
y = temp ;

Thinking about Swapping

Swapping is one of those really fundamental operations in all of programming. It is the basis for many important algorithms. An algorithm is a solution to some problem. For example, imagine you have a list of names, and you wish to alphabetize it. This is a problem called sorting.

Most sorting algorithms require swapping.