Living without Null

Originally published on: blog.kotlin-academy.com by Allan Caine

When writing code, we can usually avoid using null. It represents a state.

In Kotlin, there are many ways to avoid using null. In this article, we will show how to avoid using null to represent the empty state.

For example, the typical Java definition of a linked list is

package linkedlist;

import org.jetbrains.annotations.Nullable;

public class JavaLinkedList<T> {

    private final T payload;
    private JavaLinkedList next;


    public JavaLinkedList(T payload, @Nullable JavaLinkedList next) {
        this.payload = payload;
        this.next = next;
    }
}

In this Java implementation, null represents the empty list. Using null works. Yet, we incur all the hazards associated with the use of nulls. Null pointer exceptions are one hazard of using null. Is there a better way? Let’s explore Kotlin.

Kotlin can emulate the Java implementation of a linked list:

package linkedlist

data class LinkedList<T>(val payload : T, var next : LinkedList<T>? )

fun main(args: Array<String>) {
    val head = LinkedList(payload = "A", next = LinkedList(payload = "B", next = null))
}

Like its Java counterpart, this implementation comes at a price. It uses the nullable LinkedList<T>? . Can we improve our code further? The answer is yes.

A naïve approach to removing the nullable type LinkedList<T>? from the data classinvolves removing the question mark from the code:

package linkedlist

data class LinkedList<T>(val payload : T, var next : LinkedList<T>)

fun main(args: Array<String>) {
    val head = LinkedList(payload = "A", 
                          next = LinkedList(payload = "B", next = null))
    // Line 7 will not compile
}

The definition of the data class on line 3 is impractical. Also, lines 6 and 7 will not compile. Line 3 is saying that any linked list has a payload T and a reference to another non-null linked list. In other words, the linked list has an infinite length.

The definition above has an error. It does not take into account the empty list. Let’s define a linked list as follows:

A linked list is either:

1. A node with two properties: a non-null payload of type T and a non-null linked list; or
2. A terminal object.

We will use a sealed class to enforce that a linked list is either type 1 or type 2 and nothing more. To begin, let’s define the Node<T>:

package linkedlist

sealed class LinkedList {
    data class Node<T>(val payload : T, var next : LinkedList) : LinkedList()
}

We will use Kotlin’s object to define Terminal, because all Terminals are the same. Terminal is a singleton.

package linkedlist

sealed class LinkedList {
    data class Node<T>(val payload : T, var next : LinkedList = Terminal) : LinkedList()
    object Terminal : LinkedList()
}

val head = LinkedList.Node(payload = "A",
                            next = LinkedList.Node(payload = "B"))

val emptyList = LinkedList.Terminal

For the sake of convenience, the default value of the next property is Terminal. See line 4. We can code up a LinkedListwithout using the Terminal object. See line 9.

Let’s explore a few practical uses of our definition of a linked list. For example, we can define the toString() method as follows:

1. If LinkedList is a Node<T> then return the concatenation of the payload and next.
2. If LinkedList is a Terminal then return the empty string.

package linkedlist

sealed class LinkedList {
    data class Node<T>(val payload : T, var next : LinkedList = Terminal) : LinkedList() {
        override fun toString() = "$payload $next"
    }
    object Terminal : LinkedList() {
        override fun toString() = ""
    }
}

val head = LinkedList.Node(payload = "A",
                            next = LinkedList.Node(payload = "B"))

val emptyList = LinkedList.Terminal

fun main(args: Array<String>) {
    println(head) // prints A B
    println(emptyList) // prints a blank line
}

Size is another example. The definition of size is:

1. If LinkedList is a Node<T>, then the size is 1 plus the size of the next property of the node.
2. If LinkedList is a Terminal, then the size is zero.

Using Kotlin’s when as an expression, we can define the size recursively as

fun LinkedList.sizeRecursively() : Int = when(this) {
    is LinkedList.Node<*> -> 1 + next.sizeRecursively()
    is LinkedList.Terminal -> 0
}

fun main(args: Array<String>) {
    println(head.sizeRecursively()) // prints 2
    println(emptyList.sizeRecursively()) // prints 0
}

We defined the linked list as a sealed class. So, the when in line 1 is an expression. If when is an expression, then when must be exhaustive: Node<T>and Terminal.

As an alternative, we can place the definition of sizeRecursively()within the sealed class:

sealed class LinkedList {

    fun sizeRecursively() : Int = when(this) {
        is LinkedList.Node<*> -> 1 + next.sizeRecursively()
        is LinkedList.Terminal -> 0
    }
    
    data class Node<T>(val payload : T, var next : LinkedList = Terminal) : LinkedList() {
        override fun toString() = "$payload $next"
    }
    object Terminal : LinkedList() {
        override fun toString() = ""
    }
}

The function sizeRecursively() may not be very efficient. It is not tail recursive. So, an iterative implementation of sizeIteratively() may be better:

fun LinkedList.sizeIteratively() : Int {
    var accumulator = 0
    var pointer = this
    while (pointer is LinkedList.Node<*>) {
        accumulator++
        pointer = pointer.next
    }
    return accumulator
}

fun main(args: Array<String>) {
    println(head.sizeIteratively()) // prints 2
    println(emptyList.sizeIteratively()) // prints 0
}

We have shown that null represents a state. Using nulls involves dangers like null pointer exceptions. We have shown that we can enumerate all the possible states of a linked list by using a sealed class.

By using a sealed class as an enumeration of all possible states of an object, the code does not use null.

To be up-to-date with great news on Kotlin Academy, subscribe to the newsletter and observe Twitter.