java: use StringBuilder to insert at the beginning

Question

I could only do this with String, for example:

String str = "";
for (int i = 0; i < 100; i++) {
    str = i + str;
}

Is there a way to achieve this with StringBuilder? Thanks.

Pastoralist

Answer 1

StringBuilder sb = new StringBuilder();
for(int i=0;i<100;i++){
    sb.insert(0, Integer.toString(i));
}

Warning: It defeats the purpose of StringBuilder, but it does what you asked.

---

Better technique (although still not ideal):

1. Reverse each string you want to insert.
2. Append each string to a StringBuilder.
3. Reverse the entire StringBuilder when you're done.

This will turn an O(n²) solution into O(n).

Qualm

...since it makes AbstractStringBuilder move all the contents past the index of insertion in order to find room for the inserted ones. However, that's an implementation detail, not one of principle. – Purl

@entonio: Indeed, but it's a very critical detail. :) – Qualm

I see,It looks like I shouldn't be using StringBuilder then, Thanks a lot – Pastoralist

@user685275: Yeah, if you need backwards insertion then you really need something that can insert at the beginning of the string. I think the easiest solution is the technique above (reversing things twice), although you could probably make a better class of your own with char arrays (might want to look into "deque"s). – Qualm

Another option when conditions are right is to use a linked list with addFirst and then use Collectors.joining(...) to create the desired string. – Moldavia

@jorgeu: It's difficult to overstate how extremely rare it is for a linked list to be a better choice here. – Qualm

@Mehrdad you sure you know what string builder is doing when you add at the begining? see #26170680 – Moldavia

@jorgeu: Yeah. I don't see anything in your link to the contrary either. And see here. – Qualm

@Mehrdad I have tried your Better Technique. you should append string in a reverse way. else if you append 01 you will get 10 in final string – Bragg

@AkhilSurapuram: That's what I mentioned in step #1, right? – Qualm

@Mehrdad sorry I meant to say you also need to reverse the string builder before inserting reversed strings. – Bragg

@AkhilSurapuram: Isn't the string builder empty initially? – Qualm

Hmmm...the "purpose" of StringBuilder? Seems from the javadocs its "purpose" is to act as a mutable string, its "typical benefit and use" is to avoid the N^2 append loops, definitely? In this case it reintroduces an N^2 loop, but with input size of "only" 100, might still be acceptably fast to just do insert(0, )'s depending on how often, perhaps... :) – Kadner

@rogerdpack: I'd say that's the mechanism, not the purpose. The purpose is to be asymptotically faster than string manipulation, which it won't be if you use it wrong. – Qualm

Thank you for clarifying the O notation on both cases – Lonesome

Answer 2

you can use strbuilder.insert(0,i);

Heeler

Why did this get so many likes! The class is not defined correctly - only the signature of the method call! – Aldus

@Aldus I suppose strbuilder is a variable, not the class name (indeed, StringBuilder#insert is not a static method, therefore you could not invoke it as StringBuilder.insert(0,i)). – Ranita

Answer 3

Maybe I'm missing something but you want to wind up with a String that looks like this, "999897969594...543210", correct?

StringBuilder sb = new StringBuilder();
for(int i=99;i>=0;i--){
    sb.append(String.valueOf(i));
}

Extramarital

Strange this post did not get much voting while providing the solution by clever manipulation of the loop, – Deemphasize

@Deemphasize he just reversing the String. It doesn't answer how to append on the left. – Myrt

Achieves the desired effect. – Extramarital

I think that there could be cases in which you can use this approach instead of trying to hack a way to do the insert on the beginning which uses the true potential of StringBuilder. Anyway, there are cases in which you can't reverse the loop so you need also the other answers. – Wilburn

Answer 4

As an alternative solution you can use a LIFO structure (like a stack) to store all the strings and when you are done just take them all out and put them into the StringBuilder. It naturally reverses the order of the items (strings) placed in it.

Stack<String> textStack = new Stack<String>();
// push the strings to the stack
while(!isReadingTextDone()) {
    String text = readText();
    textStack.push(text);
}
// pop the strings and add to the text builder
String builder = new StringBuilder(); 
while (!textStack.empty()) {
      builder.append(textStack.pop());
}
// get the final string
String finalText =  builder.toString();

Ier

ArrayDeque should be used instead of Stack. "A more complete and consistent set of LIFO stack operations is provided by the {@link Deque} interface and its implementations, which should be used in preference to this class. " – Salivation

Answer 5

This thread is quite old, but you could also think about a recursive solution passing the StringBuilder to fill. This allows to prevent any reverse processing etc. Just need to design your iteration with a recursion and carefully decide for an exit condition.

public class Test {

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        doRecursive(sb, 100, 0);
        System.out.println(sb.toString());
    }

    public static void doRecursive(StringBuilder sb, int limit, int index) {
        if (index < limit) {
            doRecursive(sb, limit, index + 1);
            sb.append(Integer.toString(index));
        }
    }
}

Cordiform

Answer 6

You can use the insert method with the offset. as offset set to '0' means you are appending to the front of your StringBuilder.

StringBuilder sb = new StringBuilder();
for(int i=0;i<100;i++){
    sb.insert(0,i);
}

NOTE: as the insert method accept all types of primitives, you can use for int, long, char[] etc.

Retrogressive

Answer 7

I had a similar requirement when I stumbled on this post. I wanted a fast way to build a String that can grow from both sides ie. add new letters on the front as well as back arbitrarily. I know this is an old post, but it inspired me to try out a few ways to create strings and I thought I'd share my findings. I am also using some Java 8 constructs in this, which could have optimised the speed in cases 4 and 5.

https://gist.github.com/SidWagz/e41e836dec65ff24f78afdf8669e6420

The Gist above has the detailed code that anyone can run. I took few ways of growing strings in this; 1) Append to StringBuilder, 2) Insert to front of StringBuilder as as shown by @Mehrdad, 3) Partially insert from front as well as end of the StringBuilder, 4) Using a list to append from end, 5) Using a Deque to append from the front.

// Case 2    
StringBuilder build3 = new StringBuilder();
IntStream.range(0, MAX_STR)
                    .sequential()
                    .forEach(i -> {
                        if (i%2 == 0) build3.append(Integer.toString(i)); else build3.insert(0, Integer.toString(i));
                    });
String build3Out = build3.toString();


//Case 5
Deque<String> deque = new ArrayDeque<>();
IntStream.range(0, MAX_STR)
                .sequential()
                .forEach(i -> {
                    if (i%2 == 0) deque.addLast(Integer.toString(i)); else deque.addFirst(Integer.toString(i));
                });

String dequeOut = deque.stream().collect(Collectors.joining(""));

I'll focus on the front append only cases ie. case 2 and case 5. The implementation of StringBuilder internally decides how the internal buffer grows, which apart from moving all buffer left to right in case of front appending limits the speed. While time taken when inserting directly to the front of the StringBuilder grows to really high values, as shown by @Mehrdad, if the need is to only have strings of length less than 90k characters (which is still a lot), the front insert will build a String in the same time as it would take to build a String of the same length by appending at the end. What I am saying is that time time penalty indeed kicks and is huge, but only when you have to build really huge strings. One could use a deque and join the strings at the end as shown in my example. But StringBuilder is a bit more intuitive to read and code, and the penalty would not matter for smaller strings.

Actually the performance for case 2 is much faster than case 1, which I don't seem to understand. I assume the growth for the internal buffer in StringBuilder would be the same in case of front append and back append. I even set the minimum heap to a very large amount to avoid delay in heap growth, if that would have played a role. Maybe someone who has a better understanding can comment below.

Nazareth

Answer 8

Difference Between String, StringBuilder And StringBuffer Classes
String
String is immutable ( once created can not be changed )object. The object created as a
String is stored in the Constant String Pool.
Every immutable object in Java is thread-safe, which implies String is also thread-safe. String
can not be used by two threads simultaneously.
String once assigned can not be changed.
StringBuffer
StringBuffer is mutable means one can change the value of the object. The object created
through StringBuffer is stored in the heap. StringBuffer has the same methods as the
StringBuilder , but each method in StringBuffer is synchronized that is StringBuffer is thread
safe .
Due to this, it does not allow two threads to simultaneously access the same method. Each
method can be accessed by one thread at a time.
But being thread-safe has disadvantages too as the performance of the StringBuffer hits due
to thread-safe property. Thus StringBuilder is faster than the StringBuffer when calling the
same methods of each class.
String Buffer can be converted to the string by using
toString() method.

    StringBuffer demo1 = new StringBuffer("Hello") ;

// The above object stored in heap and its value can be changed.
/
// Above statement is right as it modifies the value which is allowed in the StringBuffer
StringBuilder
StringBuilder is the same as the StringBuffer, that is it stores the object in heap and it can also
be modified. The main difference between the StringBuffer and StringBuilder is
that StringBuilder is also not thread-safe.
StringBuilder is fast as it is not thread-safe.
/
// The above object is stored in the heap and its value can be modified
/
// Above statement is right as it modifies the value which is allowed in the StringBuilder

Gag

Welcome to stackoverflow. Please include an explanation of what the code does and how it solves the problem in the question. – Minestrone

Answer 9

How about:

StringBuilder builder = new StringBuilder();
for(int i=99;i>=0;i--){
    builder.append(Integer.toString(i));
}
builder.toString();

OR

StringBuilder builder = new StringBuilder();
for(int i=0;i<100;i++){
  builder.insert(0, Integer.toString(i));
}
builder.toString();

But with this, you are making the operation O(N^2) instead of O(N).

Snippet from java docs:

Inserts the string representation of the Object argument into this character sequence. The overall effect is exactly as if the second argument were converted to a string by the method String.valueOf(Object), and the characters of that string were then inserted into this character sequence at the indicated offset.

Foucquet