Data Structures and Algorithms in Kotlin

# CHAPTER 29

Data Structures and Algorithms in Kotlin #

1. Chapter Introduction #

2. Learning Objectives #

• Implement a custom Stack and Queue.

• Understand the mechanics of a Singly Linked List.

• Implement Binary Search for O(log N) lookups.

• Implement basic Sorting Algorithms (Bubble Sort).

3. The Stack (LIFO) #

class Stack<T> {
    private val elements = mutableListOf<T>()

    // Add to the top
    fun push(item: T) = elements.add(item)

    // Remove from the top
    fun pop(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(elements.size - 1)
    }

    // Look at the top without removing
    fun peek(): T? = elements.lastOrNull()
}

fun main() {
    val stack = Stack<String>()
    stack.push("Home Screen")
    stack.push("Profile Screen")
    
    println(stack.pop()) // Output: Profile Screen
}

4. The Queue (FIFO) #

class Queue<T> {
    private val elements = mutableListOf<T>()

    // Add to the back of the line
    fun enqueue(item: T) = elements.add(item)

    // Remove from the front of the line
    fun dequeue(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(0)
    }
}

fun main() {
    val printQueue = Queue<String>()
    printQueue.enqueue("Document1.pdf")
    printQueue.enqueue("Image.png")
    
    println(printQueue.dequeue()) // Output: Document1.pdf
}

5. Linked Lists #

// The Node holds the data, and a reference to the next Node!
class Node<T>(val value: T, var next: Node<T>? = null)

class LinkedList<T> {
    var head: Node<T>? = null

    fun append(value: T) {
        if (head == null) {
            head = Node(value)
            return
        }
        
        // Traverse to the end of the list
        var current = head
        while (current?.next != null) {
            current = current.next
        }
        current?.next = Node(value)
    }

    fun printList() {
        var current = head
        while (current != null) {
            print("${current.value} -> ")
            current = current.next
        }
        println("null")
    }
}

fun main() {
    val list = LinkedList<Int>()
    list.append(10)
    list.append(20)
    list.append(30)
    list.printList() // Output: 10 -> 20 -> 30 -> null
}

6. Searching: Binary Search #

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        when {
            arr[mid] == target -> return mid      // Found it!
            arr[mid] < target -> left = mid + 1   // Target is in the right half
            else -> right = mid - 1               // Target is in the left half
        }
    }
    return -1 // Not found
}

fun main() {
    // Array MUST be sorted for Binary Search to work!
    val sortedNumbers = intArrayOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
    val index = binarySearch(sortedNumbers, 23)
    println("Found at index: $index") // Output: 5
}

7. Sorting: Bubble Sort #

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

fun main() {
    val numbers = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    bubbleSort(numbers)
    println(numbers.joinToString(", ")) // 11, 12, 22, 25, 34, 64, 90
}

8. Common Mistakes #

• Using Binary Search on an unsorted list: Binary search mathematically relies on the data being sorted (Left is smaller, Right is larger). If the list is unsorted, it will fail silently and return -1.

9. Best Practices #

• Use the Standard Library in Production: While implementing a Stack manually is great for interviews, in real Kotlin applications, you should use ArrayDeque (Double-ended queue), which serves as an incredibly fast Stack and Queue natively.

10. Exercises #

1. 1. What data structure would you use to build an "Undo" feature in a text editor? (Answer: Stack).

1. 2. What data structure would you use to manage printer jobs sent from 10 different computers? (Answer: Queue).

11. MCQs with Answers #

12. Interview Questions #

• Q: Explain how Binary Search works and why it is drastically faster than Linear Search.

• Q: Compare an Array with a Linked List. When would you use one over the other?

13. Summary #

14. Next Chapter Recommendation #