Incremental Java
Reversing an ArrayList

Reversing the List

Let's try to reverse the list. For example, suppose the ArrayList looks like:

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

We want the to reverse it so the list now looks like:

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

How can you do this?

This is where you need to sit and think.

First Attempt

One way to reverse a list is to make a new list. Then, we go backwards in the old list (almost as if we're printing it), and get() the object handles in reverse order, and add() it to the second list.

Here's the code:

public ArrayList reverse( ArrayList orig )
{
   ArrayList reversed = new ArrayList() ;
   for ( int i = orig.size() - 1 ; i >= 0 ; i-- )
   {
       Object obj = orig.get( i ) ;
       reversed.add( obj ) ;
   }
   return reversed ;
}

Trace the code where orig has the contents of the ArrayList at the beginning of this lesson, to see if reversed has the contents in reverse.

One Problem

Suppose you didn't want to create a new ArrayList? Can we reverse it in place? To reverse in place means to not use a second ArrayList. We can use an Object local variable or two.

Second Attempt: In-place reversal

What does it mean for a list to be reversed? It means the last element is now the first, and the first is now the last. The second to last element is now the second element, and vice versa.

This sounds like swapping. And it is!

To describe what we're going to do, we'll write out pseudocode. Pseudocode is like an outline. It's not real Java code, but it's not hard to make it real Java code.

Here's an example:

Initialize start to 0 and end to list.size() - 1. In other words, initialize it to the index of the first and last element. (It's important to realize we're using indexes).
Swap the elements at the index, start and end.
Increment start (by 1) and decrement end by 1.
Go back to step 2

This pseudocode isn't quite complete. We haven't said how many times we should repeat steps 2-4.

Let's write the code, and trace to see if it works:

public static void reverse( ArrayList list )
{
   for ( int start = 0, end = list.size() - 1 ;
         start < list.size() ;
         start++, end-- )
   {
      swap( list, start, end ) ;
   }
}

private static void swap( ArrayList alist, int front, int back )
{
   Object temp = alist.set( front, alist.get( back ) ) ;
   alist.set( back, temp ) ;
}

Reread the section about comma operators to understand the for loop above.

Does Second Attempt Work?

A programmer's job is to get their code to work. This means trying to figure out whether the code does what it should, and this means tracing.

Let's trace out the code. We print out the ArrayList after the completion of each iteration, starting at iteration 0.

Iteration 0

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

So far, so good.

Iteration 1

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

It looks like we're done, but there are several more iterations to go.

Iteration 2

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

This swapped the element at index 3 with itself. A little unnecessary work, but no problems.

Iteration 3

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

Uh oh. We just swapped index 3 with index 2. We're reversing the list a second time.

Iteration 4

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

Uh oh. We're back to the original list.

Third Attempt

By tracing the code on a small example, we found the error. We reversed the list twice. We should have stopped swapping once we were half way through the list. In fact, we should only swap when start < end.

Let's rewrite the code, this time correctly.

public static void reverse( ArrayList list )
{
   for ( int start = 0, end = list.size() - 1 ;
         start < end ;
         start++, end-- )
   {
      swap( list, start, end ) ;
   }
}

Alternatively, we can just go halfway through the list.

public static void reverse( ArrayList list )
{
   for ( int start = 0, end = list.size() - 1 ;
         start < list.size() / 2;
         start++, end-- )
   {
      swap( list, start, end ) ;
   }
}

Notice that when list.size() is odd, the result truncates. For example, we had list.size() equal to 5, so 5 / 2, using integer division is 2. Thus, start starts at 0, then 1, then when it reaches 2, we exit the loop. That way, we don't swap the middle element with itself.

The code also works when list.size() is even. Suppose the size was 6, then 6 / 2 evaluates to 3. first then has values 0, 1, and 3, and exits when it reaches 3.

Incremental Java Reversing an ArrayList

Reversing the List

First Attempt