Bsrgvty

Q: Given a list, reverse the order of its elements (don't use
collections).

Here is my solution:

public static <T> void reverse(List<T> list) 
 if (list.size() > 0) 
 T t;
 t = list.get(0);
 list.remove(0);
 reverse(list);
 list.add(t);
 

1. I want to know if this is an efficient way of reversing a list


2. Is this working for every list as input?

Java doesn't handle recursion very well. And by not very well I mean it should be avoided almost every time where you cannot limit the depth to something small. To show you how bad it is let's take a look at this simple program:

public static void main(String[] args) 
 for(int n = 0; n < 100_000; n+=100) 
 List<Integer> list = new ArrayList<>();
 for(int i = 0; i < n; i++) 
 list.add(i);
 
 reverse(list);
 System.out.println(n);
 

At some point in the output we can see this:

17800
17900
Exception in thread "main" java.lang.StackOverflowError
at slowness.SlowApp.reverse(SlowApp.java:24)
at slowness.SlowApp.reverse(SlowApp.java:24)

This means that on my machine with default settings I can't even handle a list of 18000 integers. Any list bigger than that just crashes the program.

Is it possible to do it without recursion then?

This has proven a little trickier than I expected when I started writing this answer.

I was thinking of 2 possible approaches.

One is to always update the list in place. Just take the last element from the list and insert it into the correct spot (insert at 0, next insert at 1, next ...). Since we don't know which kind of List we are working with this could be a really expensive operation.

The other approach is to first take a copy of all the elements. Then clear the input list. Reverse the copied elements and insert them back into the input list. The main advantage here is that we can copy them into an array which allows O(1) access to each element even for updating them.

An example implementation is then:

public static <T> void reverse2(List<T> list) 
 T[] array = (T[]) list.toArray();

 list.clear();

 for(int i = 0; i < array.length/2; i++) 
 T temp = array[i];
 array[i] = array[array.length - i-1];
 array[array.length-i-1] = temp;
 

 for(T item : array) 
 list.add(item);
 

This implementation has no issue with a List of a million Integers.

Edit: just inserting backwards was too obvious after I tried to use list.addAll(aray) which didn't work (needs collection, not an array). I'll leave the current implementation as-is in my answer.

Note that this also isn't the most efficient way. I highly advise you to look at the implementation of the internal Collection.reverse to see a better way.

No and no. This is a very inefficient way to reverse, for example, a dynamic array based list (it's a different story with a linked list). With a dynamic array based (e.g. ArrayList) The remove(0) operation will require moving every other element in the list (linear in the length), so the whole method is quadratic in the total length of the list. It also requires a linear number of stack frames, which are actually pretty expensive and if you ask for too many the program will crash, which means this method will not work for long lists.

An efficient solution would work in linear time with a constant space requirement.

When thinking about inputs, it's important to also consider null as a possible input. The deficient spec does not indicate what should be done with a null input, which means you have had to make a decision, and that decision should be documented. The 'easy' (and often best) option is to explicitly test for a null input and throw an IllegalArgumentException exception, so that anyone using your method receives a useful error message. You could argue that your code should do nothing with a null, but that's a bit iffy, because the spec doesn't qualify the behaviour, and that would 'silently' fail if someone passed it a null incorrectly: throwing an exception forces any unexpected usage to be address directly, which may or may not prompt a decision change, which makes it a good 'default' choice.

There is no need here to pre-declare t: just declare and assign it in one go:

T t = list.get(0);

This makes it easier to find out what it means. You could also make it final in this case, so that it is entirely clear that it is only assigned once, which makes it that little bit easier to reason about the code.

When writing recursive code like this, it can pay select the 'most ideal' base case. In this instance, any list of length no more than 1 is already reversed, so you could change the if condition to list.size() > 1. This doesn't change the complexity, but is something of which to be aware.

Already answered, but as task, one probably fares better with not introducing too many extra structures.

I'll immediately give an iterative version. It shows some improvements that could also be made to your recursive solution.

The recursive solution is fine, though seemingly needing a call stack the size of the list. However tail-recursion can be optimized by a good compiler (made iterative).
The iterative version needs an extra variable to hold a temporary result (the recursive call's result).

public static <T> void reverse(List<T> list) 
 if (list.size() > 1) // Not needed, heuristic optimisation
 //List<T> reversed = new ArrayList<>(list.size());
 List<T> reversed = new LinkedList<>();
 while (!list.isEmpty()) // Or list.size() > 1
 T t = list.remove(0);
 reversed.add(t);
 
 list.addAll(reversed);
 

I want to know if this is an efficient way of reversing a list

Already answered by others, but it could be astonishly good.
Nicer would be if the list was not modified in-situ, but substituted by a new List,
as then the list.addAll(reversed) could be exchanged for return reversed;.

Is this working for every list as input?

Yes, though the list must not be operated upon at the same time.

There are some lists, immutable lists (that are not allowed to be changed) or lists that are backed by arrays (strudcturally immutable), that will throw an error.