Reputation: 6680

How is StringBuffer implementing append function without creating two objects?

It was an interview question. I was asked to implement the StringBuffer append function. I saw the code after the interview. But I cannot understand how the operation is done with creation of a single object.

I am thinking like this.

String s = "orange";
s.append("apple");

Here two objects are created.

But

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

Now here only one object is created.

How is Java doing this operation?

Upvotes: 28

Answers (10)

Nick Louloudakis

Reputation: 6005

tl;dr: In simple words, each string concatenation expression using the + character leads to a new String object with the contents of the initial strings being copied to the new one. StringBuffer holds an internal structure that expands only when needed, that characters are appended to it.

Hey, but lots of people use the + string concatenation!

Well, we/they shouldn't.

In terms of memory usage, you are using an array in StringBuffer in order to hold the characters - that resizes, truth, but rarely if the algorithm applied in resizing is efficient, and only one String object that is created once toString() is called, much better than the creation of a new String object on each + concatenation.

In terms of time complexity, characters are copied only once from _chars to the new string (O(n) time complexity), which in general is must better than string concatenation using the + operator, on which each operation leads to a new copy of the characters to a new object, leading to O(1 + 2 + .... + n) = O(n^2) operations.

Should I implement one on my own?

It would be good for you in terms of excercise, but modern languages provide native StringBuffer implementations to use it in production code.

In four simple steps:

Create a MyCustomStringBuilder class that internally (privately) holds an array (let's name it _chars) of characters of a fixed initial size. This array will hold the string characters.
Add an expanding method that will increase the size of _chars once the holding string character length exceeds its length. (What you are practically doing, is implementing a simple version of an ArrayList internally).
When using the stringBufferInstance.append(String s) method, add characters to _chars, increasing its size if needed.
In your toString() method implementation, you can simply create a string using the array:
```
public String toString() {
    return new String(_chars);
}
```

Upvotes: 1

Raja

Reputation: 19

****String s1="Azad"; ----One object will create in String cons. pool

System.out.println(s1);--output--Azad

s1=s1.concat("Raja");  Two object will create 1-Raja,2-AzadRaja and address of AzadRaja Store in reference s1 and cancel ref.of Azad object 

System.out.println(s1);  --output AzadRaja****

Upvotes: -1

Raja

Reputation: 19

String s = "orange";
s.append("apple");

It is not correct because append method is not available in String:

Upvotes: 1

stivlo

Reputation: 85476

First there is a problem with your question:

String s = "orange";
s.append("apple");

here two objects are created

Correct, two Objects are created, the String "orange" and the String "apple", inside the StringBuffer/StringBuilder no Objects will be created if we don't overflow the buffer. So those lines of code create 2 or 3 objects.

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

Now here only one object is created

I don't know where you get that, here you create one StringBuilder Object, one "Orange" String, one "apple" String, for a total of 3 Objects, or 4 if we overflow the StringBuilder buffer. (I count the array creation as object creation).

I read your question as, how can StringBuilder do the append without creating a new Object (when the buffer is not overflown)?

You should look at StringBuilder, since it's the non thread safe implementation. The code is interesting and easy to read. I've added the inline comments.

As internal structure there is a char array, not a String. It is initially built with length 16 and will be increased every time the capacity is exceeded. If the Strings to append fit within the char array, there is no need to create new Objects.

StringBuilder extends AbstractStringBuilder, where you'll find the following code:

/**
 * The value is used for character storage.
 */
char value[];

Since not all the array will be used at a given time, another important variable is the length:

/**  
 * The count is the number of characters used.
 */
int count;

There are many overloading of append, but the most interesting one is the following:

public AbstractStringBuilder append(String str) {
    if (str == null) str = "null"; //will literally append "null" in case of null
    int len = str.length(); //get the string length
    if (len == 0) return this; //if it's zero, I'm done
    int newCount = count + len; //tentative new length
    if (newCount > value.length) //would the new length fit?
        expandCapacity(newCount); //oops, no, resize my array
    str.getChars(0, len, value, count); //now it will fit, copy the chars 
    count = newCount; //update the count
    return this; //return a reference to myself to allow chaining
}

String.getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin) Copies characters from this string into the destination character array.

So, the append method is quite simple, the only magic left to discover is the expandCapacity, here it is:

void expandCapacity(int minimumCapacity) {
    //get the current length add one and double it
    int newCapacity = (value.length + 1) * 2; 
    if (newCapacity < 0) { //if we had an integer overflow
        newCapacity = Integer.MAX_VALUE; //just use the max positive integer
    } else if (minimumCapacity > newCapacity) { //is it enough?
        //if doubling wasn't enough, use the actual length computed
        newCapacity = minimumCapacity;
    }
    //copy the old value in the new array
    value = Arrays.copyOf(value, newCapacity); 
}

Arrays.copyOf(char[] original, int newLength) Copies the specified array, truncating or padding with null characters (if necessary) so the copy has the specified length.

In our case, padding, since we're expanding the length.

Upvotes: 55

Upul Bandara

Reputation: 5958

As others described, StringBuffer is mutable and it is implemented by using a char array. Operations in the StringBuffer are in-place operations.

More INFO can be available from the following link http://www.concentric.net/~ttwang/tech/jfastbuf.htm

It shows simple StringBuffer implementations using a char array.

Upvotes: 0

Peter Lawrey

Reputation: 533492

This doesn't compile.

String S= "orange";
S.append("apple");

if you do

final String S= "orange";
final S2 = S + "apple";

This doesn't create any objects as it is optimised at compile time to two String literals.

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

This creates two objects StringBuilder and the char[] it wraps. If you use

String s2 = s.toString();

This creates two more objects.

If you do

String S= "orange";
S2 = S + "apple";

This is the same as

String S2 = new StringBuilder("orange").append("apple").toString();

which creates 2 + 2 = 4 objects.

Upvotes: 4

John B

Reputation: 32949

StringBuilder is holding a buffer of chars in a char[] and converting them to a String when toString is called.

Upvotes: 1

Matthew Farwell

Reputation: 61695

StringBuffer, like StringBuilder allocates an array of char into which it copies the strings you append. It only creates new objects when the number of characters exceeds the size of the array, in which case it reallocates and copies the array.

Upvotes: 2