Pfthb

I'm working on a small problem to reverse a ArrayList of Characters using recusion. I've got it mostly figured out but am currently having some issues with retrieving a item by it's index.

My function is as follows:

 public static ArrayList<Character> reverseArray(ArrayList<Character> array)

 if (array.size() == 1)
 return array;
 

 // Fetched the last item

 ArrayList<Character> lastItem = new ArrayList<Character>();

 System.out.println("Index: " + (array.size()-1));
 System.out.println("Item at index: "+ (array.size()-1) + "is: " + array.get((array.size()-1)));
 lastItem.add(array.get(array.size()-1));

 // Remove the last item
 array.remove(array.get(array.size()-1));

 // Join all arrays until the last entry
 lastItem.addAll(reverseArray(array));

 return lastItem;

Running the below array list throught the function:

 ArrayList<Character> test1 = new ArrayList<Character>();
 test1.add('a');
 test1.add('b');
 test1.add('c');
 test1.add('a');
 test1.add('b');
 test1.add('c');

The output in the console appears to be: [c, c, b, b, a, a]

I added some console prints to see what was happening, at index 5 it appears to pull the item at index 2. So through to the end it removes index 5 then 2, then 3 then 1. Changing the input array to not have duplicate values makes the function work. It appears to be an issue of having multiples of the same character.

Any ideas to why this would be happening?

You are calling the overloaded version of remove that taken the element to be removed.

When you remove c, the third element gets removed. So, on the next recursive call, the last element (c) remains.

You need to remove the element by position

array.remove(array.size() - 1);

I think you do it in wrong manner. You create too many useless temporary arrays. You just need just replace respective elements in ArrayList.

public static void reverseArray(List<Character> arr, int pos) 
 if (arr.isEmpty())
 return;

 int index = arr.size() - pos - 1;

 if (pos >= index)
 return;

 char ch = arr.get(pos);
 arr.set(pos, arr.get(index));
 arr.set(index, ch);

 reverseArray(arr, ++pos);

Client code:

List<Character> arr = new ArrayList<>();
arr.add('a');
arr.add('b');
arr.add('d');
arr.add('e');

reverseArray(arr, 0);