Reversing a String in Java

Today I’m going to go ‘back to basics’ a bit and talk about string manipulation in Java. In particular, let’s talk about reversing a string. Something that is taught in every 100-level computer science class. The premise is simple enough. Take a string as input, return a string with the sequence of letters reversed.

So that means:

FOXTROT

Is turned into:

TORTXOF

Reversing a string is simple enough: Starting from the end of the source string take each character and append it to a new string. When you have reached the beginning of the source string return the result. It’s the approach you take that determines if you really know your Java coding, however.

In Java, the String object is immutable. This means that you cannot change it. And making a ‘change’ to a string actually creates a new string and disposes of the old one. Consider the following:

	String input = "FOXTROT";
	String s = "";

	for (int i= input.length(); i > 0 ; --i ) {
		s = s + input.charAt(i-1);
	}

Or rather what the Java compiler will actually turn the above code into:

	String input = "FOXTROT";
	String s = "";

	for (int i= input.length(); i > 0 ; --i ) {
		s = (new StringBuilder()).append(s).append(input.charAt(i-1)).toString();
	}

(Be thankful you don’t actually ever have to write that out yourself)

New strings are created for each iteration. One that will include all the characters from the previous iterations plus a new string that represents the current letter in your input variable. The previous version of the string and the character that was converted into a string are flagged to be garbage collected until the final result, “TORTXOF”, is created.

So you might think that’s not so bad. Just a few bytes, right? But if you do something like this when you’re parsing files with thousands of lines of text, it can add up fast. And when you build up a lot of objects for flagging for garbage collection you cause the JVM’s garbage collector to invoke more often, affecting your performance of your software and the scalability of the software you’re creating.

A more memory-savvy approach is to leverage the StringBuilder class. You can also use the StringBuffer class, which is synchronized and used if you need to write something that is thread-safe (which is a completely different topic). StringBuilder, since it’s not synchronized, has the benefit of also being faster.

So taking this into account the above code would look something like this:

	StringBuilder sb = new StringBuilder();
	String input = "FOXTROT";
	String s = "";

	for (int i=input.length(); i > 0 ; --i ) {
		sb.append(input.charAt(i-1));
	}
		

	s = sb.toString();

In this example, we’re down to two string objects: One for the input and one result. Far less GC will occur. Less overhead and work for the JVM and better scalability for your application.

The complete class shown for this example is below. Java is definitely a language that’s geared toward programmer productivity. But learning *how* the Java language itself works makes sure that you leverage it for maximum machine productivity as well.

package com.codethought.java101;

/**
 *	Simple string reverse utility class.  If you want to learn more about all the fun
 *  things you can do with String manipulation in Java I've provided the link below.
 *
 *  Note the use of a StringBuffer.  Strings are immutable.
 *  Meaning that if you change one - say by catenation - the previous version gets
 *  sent off to GC (garbage collection).  To minimize impact to GC, StringBuilders 
 *  can be used to create the string you need (since they're mutable).  When you 
 *  are done, you just call toString() on the builder and call it good.  You can find more out
 *  at:
 *  
 *  http://docs.oracle.com/javase/tutorial/java/data/manipstrings.html
 *  http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/StringBuilder.html
 *  
 *  @author David Orriss Jr
 */

class StringReverser  {

    /**
     * Reverses the string given to it.  
     * 
     * @param 	input 	the string to be reversed
     * @return null if null string is sent, the exact input for short strings, or the reversed string
     */
	public String reverse (String input) {
		StringBuilder sb = new StringBuilder();
		
		//defensive coding in the event someone tries to use a null string
		//you could also just let an NPE trigger.  personal choice
		if (input==null) {
			return null;
		}
		
		if (input.length()<2) {
			return input;
		}
		//strings are zero-based (see referenced docs for details).
	    //subtract 1 in the call to charAt, decrement to 'step back' 
		//down thru the string.
		for (int i=input.length(); i > 0 ; --i ) {
			sb.append(input.charAt(i-1));
		}
		
		return sb.toString();
	}
	
}