Algorithms and Data Structures in Kotlin: A Practical Guide

Algorithms and Data Structures in Kotlin: From Theory to Practice

Kotlin is a modern programming language that combines the conciseness of Python and the power of Java. To write efficient code, you need to understand how algorithms and data structures work. In this article, we will break down key concepts using Kotlin examples that will help you write fast and reliable programs.

The material will be useful for both beginners and developers who want to systematize their knowledge. All examples can be run in the IntelliJ IDEA environment or an online compiler.

1. Basic Data Structures in Kotlin

The Kotlin standard library provides a rich set of data structures. Let's look at the main ones.

Lists (List, MutableList)

Lists are ordered collections of elements. Kotlin separates mutable and immutable lists.

fun main() {    // Immutable list    val fruits = listOf("Apple", "Banana", "Orange")        // Mutable list    val numbers = mutableListOf(1, 2, 3)    numbers.add(4)    numbers.removeAt(1)        println(fruits[0]) // Apple    println(numbers)   // [1, 3, 4]}

Sets (Set, MutableSet)

Sets store unique elements. They are useful for checking duplicates.

fun main() {    val uniqueNumbers = setOf(1, 2, 2, 3, 3, 3)    println(uniqueNumbers) // [1, 2, 3]        val mutableSet = mutableSetOf("a", "b")    mutableSet.add("c")    println(mutableSet.contains("b")) // true}

Maps (Map, MutableMap)

Maps store key-value pairs. An analogue of a hash table.

fun main() {    val capitals = mapOf(        "Russia" to "Moscow",        "USA" to "Washington",        "France" to "Paris"    )        println(capitals["Russia"]) // Moscow        // Mutable map    val scores = mutableMapOf("Ivan" to 85)    scores["Maria"] = 92    scores["Ivan"] = 90}

2. Implementation of Classic Data Structures

Sometimes standard structures are not enough. Let's look at how to implement a stack and a queue manually.

Stack

A stack works on the LIFO (Last In, First Out) principle. It is used in parsers, undo actions, and graph traversal.

class Stack<T> {    private val elements = mutableListOf<T>()        fun push(item: T) = elements.add(item)    fun pop(): T? = if (isEmpty()) null else elements.removeAt(elements.size - 1)    fun peek(): T? = elements.lastOrNull()    fun isEmpty() = elements.isEmpty()    fun size() = elements.size}

fun main() {    val stack = Stack<Int>()    stack.push(10)    stack.push(20)    stack.push(30)        println(stack.pop())   // 30    println(stack.peek())  // 20    println(stack.size())  // 2}

Queue

A queue works on the FIFO (First In, First Out) principle. It is used in task processing systems.

class Queue<T> {    private val elements = mutableListOf<T>()        fun enqueue(item: T) = elements.add(item)    fun dequeue(): T? = if (isEmpty()) null else elements.removeAt(0)    fun peek(): T? = elements.firstOrNull()    fun isEmpty() = elements.isEmpty()}

fun main() {    val queue = Queue<String>()    queue.enqueue("Task 1")    queue.enqueue("Task 2")    queue.enqueue("Task 3")        println(queue.dequeue()) // Task 1    println(queue.peek())    // Task 2}

3. Sorting Algorithms in Kotlin

Sorting is a basic operation. Let's break down three popular algorithms.

QuickSort

One of the most efficient algorithms with an average complexity of O(n log n).

fun quickSort(arr: IntArray, low: Int, high: Int) {    if (low < high) {        val pi = partition(arr, low, high)        quickSort(arr, low, pi - 1)        quick