Kotlin Data Structures: Choosing with Algorithmic Awareness

The Real Problem: Wrong Collection Choice

In Android or Backend development, it’s tempting to use mutableListOf() for absolutely everything. The syntax is friendly and “it works”. But imagine your app needs to check if a user has already liked a post among 10,000 likes. If you use a List, your app will do a linear loop every time the button is clicked. The result? Perceptible lag and a battery that drains quickly.

The Diagnosis: Choosing the wrong data structure turns an operation that should be instantaneous into a bottleneck that scales poorly as the number of users grows. As Aditya Bhargava says in “Understanding Algorithms”, the secret is understanding how memory is organized.

The Core Concept: How Memory Works

Kotlin collections are, for the most part, abstractions over classic JVM (Java) structures. To choose well, we need to understand the fundamental principles.

The Memory Dilemma: Array vs. Linked List

Computer memory is like a closet drawer. In an Array (base of ArrayList), all items need to be stuck together. In a Linked List (LinkedList), they can be scattered, as each item knows the address of the next one.

ArrayList (List in Kotlin):

• Items stay together in memory
• Fast access by index: O(1)
• Inserting at the beginning is slow: O(n) - needs to move all items

LinkedList:

• Items can be scattered
• Access by index is slow: O(n) - needs to traverse to the index
• Inserting at the beginning is fast: O(1) - just changes a pointer

The Hash Table: The Magic Shortcut

For search and uniqueness problems, we use Hash Tables (base of Set and Map). They use a mathematical function to transform a key into an index, allowing O(1) access.

How it works: When you search for a key, the hash table quickly calculates where that item is stored, without needing to traverse all items.

Where and How to Apply

List (ArrayList)

Use when: Reading by index is the most frequent operation.

Example: List of products where you always access by index, or need to maintain insertion order.

LinkedList

Use when: There’s a high frequency of insertion/removal at the beginning of the collection.

Example: Implementing a Queue where you add at the end and remove from the beginning.

Set (HashSet)

Perfect for: Uniqueness filters and existence checks (contains).

Example: Check if a user has already voted, if an email is already registered, or remove duplicates from a list.

Map (HashMap)

Ideal for: Caches, dictionaries, and any search based on unique keys.

Example: Product price cache, mapping user IDs to their data, or any situation where you need to search something by a key.

Anti-patterns

Using .contains() on a huge List inside a loop: This creates O(n²) complexity. If you have 1000 items and do this 1000 times, that’s 1 million comparisons!

Using ArrayList to implement a Queue: Where you remove a lot from the beginning. Each removal forces reordering of all items in memory, making it very slow.

Practical Implementation

1. Random Access vs. Insertion at Top

import java.util.LinkedList

// ArrayList: O(1) performance for reading, but O(n) for inserting at beginning
val priceList = listOf(10, 20, 30) 
val price = priceList[1] // Instant - O(1)

// LinkedList: O(1) for insertions at top (without reordering memory)
val messageQueue = LinkedList<String>()
fun receiveMessage(msg: String) {
    messageQueue.addFirst(msg) // O(1) efficient
}

When to use each:

• ArrayList (List): When you need to access items by index frequently
• LinkedList: When you need to add/remove from the beginning frequently

2. The Voting Problem (Set)

See how to avoid duplicates performatively using Set:

// HashSet under the hood: O(1) search
val voteSet = mutableSetOf<String>()

fun registerVote(voter: String) {
    if (voteSet.contains(voter)) { // O(1) - Doesn't traverse the list!
        println("Vote already counted for $voter.")
    } else {
        voteSet.add(voter)
        println("Vote registered successfully.")
    }
}

// Comparison: If it were a List, it would be O(n) - much slower!
// val voteList = mutableListOf<String>()
// if (voteList.contains(voter)) { ... } // Needs to check each item!

Why Set is better: With 10,000 votes, checking if someone already voted in a List would take up to 10,000 comparisons. With Set, it’s just 1 operation!

3. The Market “List” (Map)

Mapping keys to values avoids exhaustive linear searches:

// In Java (for verbosity comparison)
// HashMap<String, Double> map = new HashMap<>();

// In Kotlin - much simpler!
val priceBook = hashMapOf(
    "apple" to 0.67,
    "avocado" to 1.49,
    "milk" to 3.50
)

fun productPrice(name: String): Double? {
    return priceBook[name] // O(1) - Direct access via Hash
}

// Usage example
val applePrice = productPrice("apple") // Instant!
println("Apple price: $${applePrice}")

Why Map is better: If you had a list of products and needed to search for the price, you’d have to traverse the entire list. With Map, you go directly to the product!

Tradeoff Analysis

Operation Comparison

Operation	ArrayList (Kotlin List)	LinkedList	HashSet / HashMap
Read (Get)	O(1)	O(n)	O(1) (via key)
Insert (Beginning)	O(n)	O(1)	O(1)
Search (Contains)	O(n)	O(n)	O(1)
Memory Usage	Low (Continuous)	High (Extra pointers)	Medium (Bucket structure)

Critical Analysis

Reference Locality: ArrayList wins in processor cache performance by being in continuous memory blocks. This means when you access an item, the next items are already “ready” in memory cache.

Hash Cost: Set/Map is fast, but generating hashCode() for complex objects can have a cost. For primitive types or Strings, it’s almost negligible. For custom objects, make sure to implement hashCode() and equals() correctly.

Immutability: In Kotlin, prefer List (immutable) for concurrency safety, unless write performance requires MutableList. Immutable lists are safer in multi-threaded environments.

Key Takeaways

1. Lists are for order, Sets are for uniqueness: Use List when order matters, Set when you need to ensure there are no duplicates.

2. ArrayList is the “jack of all trades”, but fails in specific cases: It’s great for most cases, but fails miserably at insertions at the beginning or value searches in large volumes.

3. Map is your best optimization tool: Replace search loops with direct access via key. If you’re doing list.find { it.id == x }, you should probably use a Map!

4. Think before choosing: Always ask: “What will I do most with this collection?” If it’s searching by value, use Set or Map. If it’s accessing by index, use List.

5. Final Verdict: Programming in Kotlin with algorithmic awareness is what separates an app that “runs” from an app that scales. Choose your collection based on what you’ll do most: read, insert, or search.

Conclusion

Choosing the right data structure can transform a slow operation into something instantaneous. The difference between using a List or a Set to check existence can be the difference between an app that freezes and one that works perfectly.

Remember: there’s no universal “best” data structure. There’s the right structure for each problem. Understanding Big O and how memory works helps you make the right choice!

---

This article is part of the “Understanding Algorithms” series, based on the book by Aditya Y. Bhargava.