Hey, so this is the first post in a series containing a basic introduction to Kotlin data structures. I'll try to be the most hands on as possible, so for that reason I'll be using problems from Cracking the Code Interview as examples of usage of such data structures. Today we'll be starting with two of the most basic ones: Arrays and Strings.

Strings

Strings in Kotlin, like in Java, are immutable, so we have to be very careful when handling them and mind the cases where new strings would be created without explicit warning. The class String is used to represent a string instance, each element of a string can be retrieved as a Char instance by indexed access, therefore you can think of it as an array of Char objects:

    val word = "Hello World"
    val letterH = word[0]

So, going through each element of a String is as easy as using a for-loop:

    for (c in word){
        println(c)
    }

Similar to many languages out there, you can escape special characters using the backslash, like "\n".

Another interesting featue of strings in Kotlin is how we can use something called string templates. If we'd like to insert values into a string at runtime, we may use string templates. To do so we'd need to use $ before the variable we'd like to insert into the string or use curly braces if we're evaluating an expression:

    val oneThousand = 1000

    println("1 thousand = $oneThousand")
    println("1 thousand and one = ${oneThousand + 1}")

Funny enough, if we decompile the bytecode back to java code we get the old + concatenation we're used to:

   public static final void main(@NotNull String[] args) {
      Intrinsics.checkParameterIsNotNull(args, "args");
      int oneThousand = 1000;
      String var2 = "1 thousand = " + oneThousand;
      System.out.println(var2);
      var2 = "1 thousand and one = " + (oneThousand + 1);
      System.out.println(var2);
   }

One last thought about Kotlin strings is that they use the same idea of String Pools as in Java. This means that if two strings are equal (structuraly speaking) they point to the same place in memory. Why is this important, you may ask? In kotlin we can compare two variablesby using the structural equality == and the referential equality ===. Because of String Pools and the whole string imutabilty, if we initialize two variables with the same string value, they'll hold the same referece, the code bellow would run to completion:

    val first = "first"
    val second = "first"

    assertTrue { first == second }
    assertTrue { first === second }

Most of the Kotlin types have nice extension functions to make our lives working with them easier. Here's a list of my favorite ones:

associate()

This method takes each character of the original string and apply a transformation that returns a Map. You can use it to create a map of characters counts of your string:

    val s = "Levi Moreira de Albuquerque"

    val bin = s.associate { c ->
        Pair(c, s.count { s -> s == c })
    }

    print(bin)


    {L=1, e=5, v=1, i=2,  =3, M=1, o=1, r=3, a=1, d=1, A=1, l=1, b=1, u=3, q=2}

capitalize() and decapitalize()

It takes a Locale and capitalizes the first letter of the string according to that Locale.

toSet

Would you like to know if there are repeated values in a string and can use extra space? Just use toSet():

    val s1 = "Levi Moreira de Albuquerque"
    val s2 = "abcdefghijk"

    false
    true

Arrays

Arrays in Kotlin are representd by the Array class, the basic anatomy of this class is as follows, this is the general implementation of an Array, but kotlin has specialized classes for primitive types such as IntArray, FloatArray and DoubleArray.

class Array<T> private constructor() {
    val size: Int
    operator fun get(index: Int): T
    operator fun set(index: Int, value: T): Unit
}

Accessing an array happens just like in Java, you can use square brackets and an index to access a position. Though this is just syntactic sugar to the get() and set() methods ilustrated above.

The primitive types arrays get translated into their counterparts when targetting the JVM plataform, for instance IntArray is represented by int[], FloatArray to float[] and so on. This is clear when we decompile the code:

    val s1 = IntArray(5) { index ->
        index * index
    }

We get this very ugly result:

      byte var2 = 5;
      int[] var3 = new int[var2];

      for(int var4 = 0; var4 < var2; ++var4) {
         int var6 = false;
         int var9 = var4 * var4;
         var3[var4] = var9;
      }

Just like strings, Arrays have some very interesting extension functions, some of my favorite ones are listed here:

binarySearch

Performs a binary search in the array, note that the array needs to be sorted for the result to work as expected.

forEach

intersect

Returns a set with the numbers that existing both in the first array and in the given collection:

    val s1 = IntArray(10) { index ->
        index * index
    }

    val s2 = IntArray(20) { index -> index }
    print(s1.intersect(s2.toList()))

    [0, 1, 4, 9, 16]

joinToString

Creates a string with the elements of the array using a separator (a comma isthe default value). We can also add a prefix/postfix to each element.

    val s1 = IntArray(5) { index ->
        index * index
    }
    print(s1.joinToString(separator = " "))

    0 1 4 9 16

max, min, average, sum

Performs the given action (find max, min or calculate the sum/average) with the elements of the given array.

The example

As an example of usage of such data structures we'll have a look at the first problem from the first chapter of Cracking the Code Interview. We need to devise an algorithm that can detect if a string contains only unique characters. The impementation is pretty straightfoward if we don't care about performance we cook up a O(n^2) time algorithm. But we'd like to have an O(n) algorithm and for that we'll use a BitSet.

A BitSet is simply an array of bits, we'll initialize our array with the number of characters in the extended ASCII alphabet (I made an assumption that we'll be only feeding ASCII strings), therefore we'll be using a constant amount of space.

The idea is simple, the array is initialized with false in all positions. We'll go through the input string checking each character, the integer version of the character will index the BitSet, if the given position is true we can immediately return false because there's a duplicate (we've seen it before), otherwise we return true in the end, because we looped through the whole string and didn't find any duplicates. I've also added a small check at the beginning because if a string is larger than the alphabet, it must contain repeated characters.

fun isUnique(s: String): Boolean {
    if (s.length > 256) return false
    val bits = BitSet(256)
    for (c in s) {
        if (bits[c.toInt()]) {
            return false
        }
        bits[c.toInt()] = true
    }
    return true
}

As you can see in the method above, both the BitSet and the String can be accessed by using an index. Also, I've used the .toInt() extension method to convert a Char to its integer equivalent.

I hope this was helpful to give you an introduction about some basic data structures in Kotlin. In the next post we'll talk about LinkedLists, see you there :)