In programming, iterations are very common. Whenever we want to loop through a sequence type of data structure, we will use iterations. In this tutorial, we will look at iterating array elements and some minute details with String data type.
Basic Idea
When we want to check something for each value of the array or list, we will have to iterate through all elements unless it is sorted in which case, we may be able to use binary search kind of technique. In general, iteration would look like this.
1int[] nums = new int[] {1, 2, 3, 4, 5};
2for (int i = 0; i < nums.length; i++) {
3 System.out.println(nums[i]);
4}
This is straight forward. In each iteration, we are keeping track of index position. When we want to get value at a index, we use indexing operation. Now, iteration can be sped up a little bit if we use two, three digit jumps. Even though this does not improve the amortized time complexity, it does run slightly faster.
1int[] nums = new int[] {1, 2, 3, 4, 5};
2for (int i = 0; i < nums.length; i += 2) {
3 System.out.println(nums[i]);
4}
Another option is to iterate using two pointers. For example, one pointer would start at the left side and another from the right until they cross each other. In this case, effectively we are processing two elements in single iteration. This technique can be useful if we want to reverse a string or want to find anagrams, etc.
String Creation
Strings are so popular and so easy to use that we do not realize what happens under the hood.
Strings are Interned
Something to keep in mind is that Strings are interned. That means new string creation is avoided until it’s actually needed. For example, if we define two strings with the same value, it will actually create only single string and point both variables to the same location in memory where the value is stored.
1String s1 = "hello";
2String s2 = "hello";
Strings are Immutable
In most languages, Strings are immutable. That means concatenating single character to existing string will create a new string. This is similar to array copy operation. If we have very long text of millions of characters and you want to add just a single character at the end, all characters will have to copied to another location in memory with that additional character at the end.
If the problem is about returning a string which we build one by one, it’s usually good idea to store those characters in a list or array and at the end only build the string using one of the available operations.
For example, in Java, we can build the string at the end using StringBuilder class. We can keep appending new element using append(character) method and at the end materialize it into string using toString(). In Python, we can do something similar using join(list) method.
1def create_string(s):
2 lst = []
3 for character in s:
4 lst.append(character)
5 return ", ".join(lst)
1public static String createString(String str) {
2 StringBuilder sb = new StringBuilder();
3 for (int i = 0; i < str.length(); i++) {
4 sb.append(str.charAt(i))
5 }
6 return sb.toString();
7}
Comments