Kotlin Data Structures - Arrays and Strings
Tags: android, androiddev, kotlin
Published: 2019-07-13 15:16:53

---
title: Kotlin Data Structures - Arrays and Strings
published: true
description: This is a series of posts with a basic introduction to Kotlin data structures. 
tags: android, androiddev, kotlin
cover_image: https://thepracticaldev.s3.amazonaws.com/i/c9yrlwt100zuzt2oyrkk.jpg
---

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:

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

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

```kotlin
    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:

```kotlin
    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:

```java
   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:

```kotlin
    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:

```kotlin
    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():

```kotlin
    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.

```kotlin
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:
```kotlin
    val s1 = IntArray(5) { index ->
        index * index
    }
```
We get this very ugly result:

```java
      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:

```kotlin

    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.

```kotlin
    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.


```kotlin
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 :)