Data structures are fundamental building blocks in programming that allow efficient data organization, storage, and manipulation. Kotlin, as a modern and expressive language, provides various built-in data structures that cater to different use cases. In this blog, we will explore Kotlin's key data structures, their characteristics, and when to use them.

Pre-Requisites: Android Studio installed and Java installed

What is a Data Structure?

A data structure is a specialized way of organizing and storing data in a computer so that it can be used efficiently. It provides a means to manage large amounts of data efficiently for various operations such as searching, sorting, and modifying. Data structures are fundamental to programming and essential for designing efficient algorithms.

Why Do We Need Data Structures?

Efficient data structures are crucial for solving complex problems effectively. They help in:

• Optimizing Performance: The right data structure ensures quick access and modification of data.

• Memory Management: Data structures help in optimal memory usage.

• Scalability: A well-structured program using appropriate data structures can handle increasing amounts of data efficiently.

• Ease of Implementation: Many programming problems become easier to solve with the proper data structures.

Choosing the Right Data Structure

Selecting the appropriate data structure depends on the problem at hand. For example:

• Need fast lookups? → Use Map

• Need ordered elements? → Use List

• Need uniqueness? → Use Set

• Need first-in-first-out behavior? → Use Queue

• Need last-in-first-out behavior? → Use Stack

You will know each of these data structure after reading the complete article.

Create a new Android Studio Project

You need to create a new project. Choose an “Empty Views Activity Template”, then type name as “DataStructures” as shown below and create the project.

Kindly let the project build successfully. Just because few files are showing does not mean the project is successfully built.

Also, you need a stable internet connection for the proect to build the first time as it downloads some files from the internet which are necessary for the code to run.

Create New file for writing Kotlin Code

Select “Android” View from drop down. Then navigate to app → kotlin + java → com.igtuw.datastructures

Inside the “com.igtuw.datastructures” folder create a new kotlin file (not class) as shown below.

Select File and name the file as “KotlinDS” and press enter

You will get a new Empty file as shown below

Print “Hello World” on console

Run the main Kotlin function by clicking on the green triangle in the left side of line 3

You will see a loading icon on the top center.

You will see a build process running in the bottom “yes that blue thing”. Let it completely build, and the blue thing will disappear.

The result will be shown as below

Few Concepts to know before starting the data structures code

Before diving into coding data structures in Kotlin, one should be familiar with the following fundamental concepts:

1. Variables and Data Types

Variables are storage locations that hold values. Kotlin has different types of variables, including:

• Primitive Types: Int, Double, Boolean, Char, etc.

• Complex Types: List, Map, Set, Pair, etc.

• Nullable Types: Kotlin supports null safety using nullable types (String?, Int?).

• Immutable vs Mutable Variables: val (immutable) vs var (mutable).

2. Control Flow

Control flow determines how code executes in different situations:

• Conditional Statements: if-else, when.

• Loops: for, while, do-while for iteration.

• Recursion: A function calling itself to solve problems like factorial calculation.

3. Functions

Functions help modularize and reuse code.

• Basic Function:

• Higher-Order Functions: Functions that take other functions as parameters.

• Lambda Expressions: Inline anonymous functions.

4. Object-Oriented Programming (OOP)

Kotlin is an object-oriented language with features like:

• Classes and Objects:

• Inheritance:

• Polymorphism & Encapsulation: Allows methods to be overridden and restricts direct access to class members using private, protected, and public modifiers.

5. Collections Framework

Collections store multiple items in Kotlin.

• Lists (Ordered, may contain duplicates): listOf() (immutable), mutableListOf() (mutable).

• Sets (Unique elements, unordered): setOf(), mutableSetOf().

• Maps (Key-value pairs): mapOf(), mutableMapOf().

6. Algorithmic Thinking

Understanding basic algorithms is crucial for problem-solving.

• Sorting Algorithms:

  • Bubble Sort (Simple but inefficient):

  • Quick Sort (Efficient divide and conquer sorting method).

• Searching Algorithms:

  • Linear Search: Check elements one by one.

  • Binary Search: Efficient searching in a sorted list.

7. Time and Space Complexity

Understanding algorithm efficiency using Big-O notation.

• O(1): Constant time operations.

• O(n): Linear time (loops over n elements).

• O(log n): Logarithmic time (Binary search).

• O(n²): Quadratic time (Nested loops, Bubble sort).

• Space Complexity: Memory usage for variables and data structures.

Data Structures in Kotlin

1. Lists in Kotlin

A list in Kotlin is an ordered collection of elements where duplicates are allowed.

Mutable and Immutable Lists

Kotlin provides two types of lists:

• Immutable List (List<T>): Cannot be modified after initialization (Read-only, cannot be modified after creation)

• Mutable List (MutableList<T>): Supports modifications (add, remove, update elements).

Example:

val immutableList = listOf(1, 2, 3, 4, 5)
val mutableList = mutableListOf(1, 2, 3, 4, 5)
mutableList.add(6) // Allowed

When to Use Lists?

• Use an immutable list when you don't want modifications after initialization.

• Use a mutable list when you need to frequently update the collection.

2. Sets in Kotlin

A Set in Kotlin is a collection that stores unique elements only, meaning it does not allow duplicates. Unlike lists, sets do not guarantee order unless using a specialized implementation.

Mutable and Immutable Sets

• Immutable Set (Set<T>): Contains unique elements and does not allow modifications.

• Mutable Set (MutableSet<T>): Allows adding or removing elements dynamically.

Example:

val immutableSet = setOf(1, 2, 3, 4, 5)
val mutableSet = mutableSetOf(1, 2, 3, 4, 5)
mutableSet.add(6) // Allowed

When to Use Sets?

• When you need a collection of unique elements.

• When searching for an element should be fast (Sets offer O(1) lookup time for HashSet).

3. Maps in Kotlin

A Map in Kotlin is a key-value pair collection, where each key is unique, but values can be duplicated. Maps are useful for fast lookups and associative data storage.

Mutable and Immutable Maps

• Immutable Map (Map<K, V>): Key-value pairs cannot be modified after initialization.

• Mutable Map (MutableMap<K, V>): Allows modifications like adding or removing key-value pairs.

Example:

val immutableMap = mapOf("A" to 1, "B" to 2, "C" to 3)
val mutableMap = mutableMapOf("A" to 1, "B" to 2, "C" to 3)
mutableMap["D"] = 4 // Allowed

When to Use Maps?

• When you need a key-value relationship between elements.

• When lookup operations need to be efficient (O(1) for HashMap).

4. Queues in Kotlin

A Queue in Kotlin is a First In, First Out (FIFO) data structure, meaning elements are added at the end and removed from the front.

Kotlin does not provide built-in Queue (FIFO - First In First Out) implementations but they can be implemented using LinkedList.

import java.util.LinkedList

val queue: LinkedList<Int> = LinkedList()
queue.add(1)
queue.add(2)
queue.add(3)
val dequeuedElement = queue.poll() // Removes 1

When to Use Queues?

• When you need First-In-First-Out (FIFO) behavior.

• When handling task scheduling (e.g., job queues, print queues).

• When implementing breadth-first search (BFS) in graph algorithms.

• When processing real-time data streams.

5. Stacks

A Stack is a Last In, First Out (LIFO) data structure, meaning the last element added is the first to be removed.

Kotlin does not provide built-in Stack (LIFO - Last In First Out) implementations but they can be implemented using LinkedList.

import java.util.Stack

val stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
val poppedElement = stack.pop() // Removes 3

When to Use Stacks?

• When you need Last-In-First-Out (LIFO) behavior.

• When implementing undo/redo functionality in applications.

• When managing function calls and recursion (call stack).

• When parsing expressions (e.g., evaluating mathematical expressions or syntax parsing).

5. Linked List in Kotlin

A linked list is a linear data structure where elements (nodes) are linked using pointers. Kotlin does not provide a built-in LinkedList, but it can be implemented manually.

// Node class
class Node<T>(var data: T, var next: Node<T>? = null)

// Linked List class
class LinkedList<T> {
    private var head: Node<T>? = null

    // Insert at the end
    fun append(data: T) {
        if (head == null) {
            head = Node(data)
            return
        }
        var current = head
        while (current?.next != null) {
            current = current.next
        }
        current?.next = Node(data)
    }

    // Insert at the beginning
    fun prepend(data: T) {
        val newNode = Node(data, head)
        head = newNode
    }

    // Delete a node
    fun delete(data: T) {
        if (head == null) return

        // If head node is the one to be deleted
        if (head?.data == data) {
            head = head?.next
            return
        }

        var current = head
        while (current?.next != null) {
            if (current.next?.data == data) {
                current.next = current.next?.next
                return
            }
            current = current.next
        }
    }

    // Display the list
    fun display() {
        var current = head
        while (current != null) {
            print("${current.data} -> ")
            current = current.next
        }
        println("null")
    }
}

// Test the LinkedList
fun main() {
    val list = LinkedList<Int>()
    list.append(10)
    list.append(20)
    list.append(30)
    list.prepend(5)
    list.display()  // Output: 5 -> 10 -> 20 -> 30 -> null
    list.delete(20)
    list.display()  // Output: 5 -> 10 -> 30 -> null
}

When to Use Linked Lists?

• When frequent insertions and deletions are required.

• When memory usage is a concern (linked lists dynamically allocate memory).

• When you need a resizable structure without the overhead of arrays.

6. Graphs in Kotlin

A graph is a collection of nodes (vertices) and edges.

Graphs can be represented in multiple ways. The two most common ways are:

1. Adjacency List (Efficient for sparse graphs)

2. Adjacency Matrix (Efficient for dense graphs)

Here, I’ll show how to implement a graph using an adjacency list in Kotlin.

We will use a HashMap (MutableMap) to store the adjacency list.

class Graph<T> {
    private val adjacencyList: MutableMap<T, MutableList<T>> = mutableMapOf()

    // Add a vertex
    fun addVertex(vertex: T) {
        adjacencyList.putIfAbsent(vertex, mutableListOf())
    }

    // Add an edge (undirected graph)
    fun addEdge(vertex1: T, vertex2: T) {
        adjacencyList[vertex1]?.add(vertex2)
        adjacencyList[vertex2]?.add(vertex1)  // Comment this for a directed graph
    }

    // Print the adjacency list
    fun printGraph() {
        for (vertex in adjacencyList.keys) {
            println("$vertex -> ${adjacencyList[vertex]}")
        }
    }

    // BFS Traversal (Breadth-First Search)
    fun bfs(start: T) {
        val visited = mutableSetOf<T>()
        val queue = ArrayDeque<T>()

        queue.add(start)
        visited.add(start)

        while (queue.isNotEmpty()) {
            val vertex = queue.removeFirst()
            print("$vertex ")

            for (neighbor in adjacencyList[vertex] ?: emptyList()) {
                if (neighbor !in visited) {
                    queue.add(neighbor)
                    visited.add(neighbor)
                }
            }
        }
        println()
    }

    // DFS Traversal (Depth-First Search)
    fun dfs(start: T, visited: MutableSet<T> = mutableSetOf()) {
        if (start in visited) return

        print("$start ")
        visited.add(start)

        for (neighbor in adjacencyList[start] ?: emptyList()) {
            dfs(neighbor, visited)
        }
    }
}

fun main() {
    val graph = Graph<Int>()

    // Add vertices
    for (i in 1..5) {
        graph.addVertex(i)
    }

    // Add edges
    graph.addEdge(1, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 5)
    graph.addEdge(4, 5)

    // Print graph
    graph.printGraph()

    // BFS Traversal
    println("BFS Traversal starting from node 1:")
    graph.bfs(1)

    // DFS Traversal
    println("DFS Traversal starting from node 1:")
    graph.dfs(1)
}

When to Use Graphs?

• When representing networks like social connections, road maps, or web pages.

• When solving problems like shortest path (Dijkstra's Algorithm) or network traversal (DFS, BFS).

7. Hash Tables (HashMap) in Kotlin

A hash table is a data structure that maps keys to values using a hash function.

fun main() {
    val hashTable = HashMap<String, Int>()

    // Insert key-value pairs
    hashTable["Alice"] = 25
    hashTable["Bob"] = 30
    hashTable["Charlie"] = 35

    // Access values
    println("Alice's Age: ${hashTable["Alice"]}") // Output: Alice's Age: 25

    // Check if a key exists
    println("Contains Bob? ${"Bob" in hashTable}") // Output: true

    // Iterate through the hash table
    for ((key, value) in hashTable) {
        println("$key -> $value")
    }

    // Remove an element
    hashTable.remove("Charlie")

    println("After removing Charlie: $hashTable") // Output: {Alice=25, Bob=30}
}

When to Use Hash Tables?

• When fast lookups and insertions are needed (O(1) on average).

• When data needs to be stored as key-value pairs.

After Words

Data structures are the backbone of efficient programming, and Kotlin provides a rich set of built-in and customizable options to handle various data needs. From linear structures like lists, stacks, and queues to non-linear structures like trees and graphs, Kotlin offers both simplicity and flexibility. Whether you're working with hash maps for fast lookups, linked lists for dynamic memory allocation, or priority queues for scheduling tasks, understanding these structures will help you write optimized and maintainable code. By leveraging Kotlin’s powerful collections framework and custom implementations, you can build scalable applications with ease. Keep exploring and mastering these structures to enhance your problem-solving skills in Kotlin!