Given the following method:
public String toString()
{
if (_head == null)
return "";
String S="";
WordNode currentNode = _head;
while (currentNode != null)
{
S+=currentNode.getWord()+" ";
currentNode = currentNode.getNext();
}
return S;
}
What are time and space complexities? In Java, String is immutable object. How can it affect complexity? Thanks.
Time complexity is O(n), where n is the number of nodes, because you iterate over each node once. Space complexity is actually O(n*m), where n is the number of nodes and m is the length of the largest string you will create (which is the last string which contains all the words). This is because you create n strings, and string creation in java has memory usage proportional to the number of characters in the string (which in your case is maximum m). If you want to see exactly how much memory string creation uses, see this link: http://www.javamex.com/tutorials/memory/string_memory_usage.shtml.
Btw, you do not really need the if check in the beginning of your function because if the head is null, your while loop will not undergo any iterations and you will return an empty string anyway. Taking out this conditional will improve your time performance by a constant factor (but the time complexity will of course be the same).