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 class
involves 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:
- A node with two properties: a non-null payload of type
T
and a non-null linked list; or - 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 LinkedList
without 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:
- If
LinkedList
is aNode<T>
then return the concatenation of thepayload
andnext
. - If
LinkedList
is aTerminal
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:
- If
LinkedList
is aNode<T>
, then the size is 1 plus the size of thenext
property of the node. - If
LinkedList
is aTerminal
, 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.