DEV Community

Bill Odida
Bill Odida

Posted on

2 1 1 1

Kotlin Data Structures: A Comprehensive Guide

LinkedList in Kotlin

Overview

A LinkedList is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Kotlin provides both the standard library implementation and the ability to create custom implementations.

Implementation from Scratch

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

class LinkedList<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null
    var size = 0
        private set

    fun add(value: T) {
        val newNode = Node(value)
        if (head == null) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            tail = newNode
        }
        size++
    }

    fun addFirst(value: T) {
        val newNode = Node(value)
        newNode.next = head
        head = newNode
        if (tail == null) {
            tail = newNode
        }
        size++
    }

    fun removeFirst(): T? {
        if (head == null) return null
        val value = head?.value
        head = head?.next
        size--
        if (head == null) {
            tail = null
        }
        return value
    }

    fun find(value: T): Boolean {
        var current = head
        while (current != null) {
            if (current.value == value) return true
            current = current.next
        }
        return false
    }

    override fun toString(): String {
        return buildString {
            var current = head
            append("[")
            while (current != null) {
                append(current.value)
                if (current.next != null) append(", ")
                current = current.next
            }
            append("]")
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Using Kotlin's Built-in LinkedList

fun main() {
    // Creating a LinkedList
    val linkedList = LinkedList<String>()

    // Adding elements
    linkedList.add("First")
    linkedList.add("Second")
    linkedList.addFirst("New First")

    // Accessing elements
    println(linkedList.first)    // New First
    println(linkedList.last)     // Second

    // Removing elements
    linkedList.removeFirst()
    linkedList.removeLast()

    // Checking size and emptiness
    println(linkedList.size)     // 1
    println(linkedList.isEmpty()) // false
}
Enter fullscreen mode Exit fullscreen mode

Stack in Kotlin

Overview

A Stack is a LIFO (Last-In-First-Out) data structure. While Kotlin doesn't have a built-in Stack class, we can implement one using various approaches.

Custom Stack Implementation

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

    fun push(element: T) {
        elements.add(element)
    }

    fun pop(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(elements.lastIndex)
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    fun isEmpty() = elements.isEmpty()

    fun size() = elements.size

    override fun toString() = elements.toString()
}

// Usage example
fun main() {
    val stack = Stack<Int>()
    stack.push(1)
    stack.push(2)
    stack.push(3)

    println(stack.pop())    // 3
    println(stack.peek())   // 2
    println(stack.size())   // 2
}
Enter fullscreen mode Exit fullscreen mode

Using Kotlin Collections as Stack

fun main() {
    // Using MutableList as a stack
    val stack = mutableListOf<Int>()

    // Push operations
    stack.add(1)        // push
    stack.add(2)        // push

    // Pop operation
    val lastElement = stack.removeLastOrNull()

    // Peek operation
    val topElement = stack.lastOrNull()
}
Enter fullscreen mode Exit fullscreen mode

Queue in Kotlin

Overview

A Queue is a FIFO (First-In-First-Out) data structure. We'll implement both a basic Queue and a more advanced implementation with Kotlin's features.

Basic Queue Implementation

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

    fun enqueue(element: T) {
        elements.add(element)
    }

    fun dequeue(): T? {
        if (elements.isEmpty()) return null
        return elements.removeAt(0)
    }

    fun peek(): T? = elements.firstOrNull()

    fun isEmpty() = elements.isEmpty()

    fun size() = elements.size

    override fun toString() = elements.toString()
}
Enter fullscreen mode Exit fullscreen mode

Advanced Queue Implementation with Circular Buffer

class CircularQueue<T>(private val capacity: Int) {
    private val elements = Array<Any?>(capacity) { null }
    private var front = 0
    private var rear = -1
    private var size = 0

    fun enqueue(element: T): Boolean {
        if (isFull()) return false

        rear = (rear + 1) % capacity
        elements[rear] = element
        size++
        return true
    }

    @Suppress("UNCHECKED_CAST")
    fun dequeue(): T? {
        if (isEmpty()) return null

        val element = elements[front] as T
        elements[front] = null
        front = (front + 1) % capacity
        size--
        return element
    }

    @Suppress("UNCHECKED_CAST")
    fun peek(): T? = if (isEmpty()) null else elements[front] as T

    fun isEmpty() = size == 0

    fun isFull() = size == capacity

    fun size() = size
}
Enter fullscreen mode Exit fullscreen mode

HashTables in Kotlin

Overview

HashTables (or HashMaps in Kotlin) are key-value data structures that provide constant-time average case complexity for insertions and lookups.

Custom HashTable Implementation

class HashTable<K, V>(private val capacity: Int = 16) {
    private data class Entry<K, V>(
        val key: K,
        var value: V,
        var next: Entry<K, V>? = null
    )

    private val buckets = Array<Entry<K, V>?>(capacity) { null }
    private var size = 0

    private fun hash(key: K): Int {
        return Math.abs(key.hashCode() % capacity)
    }

    fun put(key: K, value: V) {
        val index = hash(key)
        val entry = Entry(key, value)

        if (buckets[index] == null) {
            buckets[index] = entry
            size++
            return
        }

        var current = buckets[index]
        while (current != null) {
            if (current.key == key) {
                current.value = value
                return
            }
            if (current.next == null) {
                current.next = entry
                size++
                return
            }
            current = current.next
        }
    }

    fun get(key: K): V? {
        val index = hash(key)
        var current = buckets[index]

        while (current != null) {
            if (current.key == key) {
                return current.value
            }
            current = current.next
        }
        return null
    }

    fun remove(key: K): Boolean {
        val index = hash(key)
        var current = buckets[index]
        var prev: Entry<K, V>? = null

        while (current != null) {
            if (current.key == key) {
                if (prev == null) {
                    buckets[index] = current.next
                } else {
                    prev.next = current.next
                }
                size--
                return true
            }
            prev = current
            current = current.next
        }
        return false
    }

    fun size() = size
    fun isEmpty() = size == 0
}
Enter fullscreen mode Exit fullscreen mode

Using Kotlin's Built-in HashMap

fun main() {
    // Creating a HashMap
    val map = HashMap<String, Int>()

    // Adding entries
    map["one"] = 1
    map["two"] = 2
    map.put("three", 3)

    // Accessing values
    println(map["one"])           // 1
    println(map.get("two"))       // 2
    println(map.getOrDefault("four", 0)) // 0

    // Removing entries
    map.remove("one")

    // Checking containment
    println(map.containsKey("one"))    // false
    println(map.containsValue(2))      // true

    // Iterating over entries
    for ((key, value) in map) {
        println("$key = $value")
    }

    // Using with nullable values
    val nullableMap = HashMap<String, Int?>()
    nullableMap["nullable"] = null
}
Enter fullscreen mode Exit fullscreen mode

Performance Characteristics

LinkedList

  • Access: O(n)
  • Search: O(n)
  • Insertion at beginning: O(1)
  • Insertion at end: O(1) with tail reference
  • Deletion at beginning: O(1)
  • Deletion at end: O(n)
  • Space complexity: O(n)

Stack

  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)
  • Space complexity: O(n)

Queue

  • Enqueue: O(1)
  • Dequeue: O(1) with proper implementation
  • Peek: O(1)
  • Space complexity: O(n)

HashTable

  • Insert: O(1) average, O(n) worst
  • Delete: O(1) average, O(n) worst
  • Search: O(1) average, O(n) worst
  • Space complexity: O(n)

Best Practices and Tips

  1. Choose the Right Collection:

    • Use LinkedList when frequent insertions/deletions at both ends are needed
    • Use Stack for LIFO operations
    • Use Queue for FIFO operations
    • Use HashTable for key-value associations with fast lookups
  2. Memory Considerations:

    • LinkedList requires extra memory for node references
    • CircularQueue can help manage memory in fixed-size scenarios
    • HashTable size should be balanced against expected number of elements
  3. Thread Safety:

    • These implementations are not thread-safe by default
    • Use Collections.synchronizedList() or other concurrent implementations for thread safety
  4. Performance Optimization:

    • Initialize collections with expected capacity when possible
    • Consider using specialized implementations for specific use cases
    • Monitor load factor in HashTable implementations

Image of AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay