Choosing Kotlin Collections by Performance and Ordering Trade-offs

Welcome back. Last lesson, we kept earlier screen states intact by creating new values instead of mutating a shared list. Now we can ask a more operational question: is a list the right collection for the job? An articles screen needs a display order, but bookmarked IDs need fast membership checks, and an article cache needs lookup by ID. Those are different requirements.

In about 40 minutes, you’ll compare Kotlin lists, sets, and maps by lookup, insertion, ordering, and memory use. The goal is to make a choice you can explain both in an Android code review and in an interview.

Start with the operation the feature needs

Kotlin’s collection interfaces express useful promises. A List has positions and allows duplicates. A Set has unique elements. A Map associates unique keys with values; unlike List and Set, it does not extend Collection. Each has read-only and mutable interfaces. As last lesson established, a read-only interface limits what a caller can do through that reference; it does not necessarily make the underlying object immutable.

Read the Kotlin documentation’s overview and List section for those promises and the usual list implementation.

For the articles screen, a list is a natural public shape because the position of each article matters:

data class Article(
    val id: String,
    val title: String,
    val subtitle: String?
)

val articles: List<Article> = listOf(
    Article("a1", "Kotlin state", null),
    Article("a2", "Coroutines", "Async work")
)

println(articles[0].title) // Kotlin state

This adds an id to the article model from last lesson. In a typical array-backed list such as ArrayList, fetching by index takes $O(1)$ time. Finding an article by ID is different: without another index, you may have to examine every article, taking $O(n)$ time.

Adding to the end of a mutable ArrayList is usually cheap—amortized $O(1)$—because it keeps spare capacity. Occasionally it must grow its backing storage and copy elements, making that particular append $O(n)$. Inserting near the front generally takes $O(n)$, because later elements must move.

The same trade-off matters when updating screen state. Last lesson’s current.articles + newArticle leaves the old list unchanged, which is useful for predictable state, but it makes a new list and copies references to its existing elements. That update costs $O(n)$ time and additional list storage. An in-place append avoids that copy but gives up the same straightforward guarantee about the earlier list. Choose based on state ownership and update frequency, not just the speed of one operation.

Sets and maps trade storage for keyed lookup

Suppose the UI only needs to answer, “Is article a2 bookmarked?” A list of bookmarked IDs can answer, but each membership check may scan the list. A hash-based set is built for this question. If you also need to retrieve an Article from its ID, a map holds the associated value.

Watch the short explanation of hash sets and maps. Treat its constant-time claims as expected-case behavior, not an unconditional guarantee.

The Kotlin documentation adds an important ordering distinction: its usual mutable set and map implementations preserve insertion order, while alternatives named HashSet and HashMap make no iteration-order promise.

Here is one sensible combination for an articles feature:

val bookmarkedIds: MutableSet<String> = HashSet()
bookmarkedIds.add("a2")

val isBookmarked = "a2" in bookmarkedIds

val articlesById: MutableMap<String, Article> = HashMap()
for (article in articles) {
    articlesById[article.id] = article
}

val selectedArticle: Article? = articlesById["a2"]

The set answers membership; the map retrieves an article by key. Both typically take $O(1)$ time per lookup with well-distributed hashes. Building articlesById takes $O(n)$ time and $O(n)$ extra space. It stores references to the articles, not a second copy of every Article object. Keeping both a list and map is worthwhile when many ID lookups justify that extra index—not necessarily for one lookup on a small screen.

There are correctness costs too. If an ID appears twice while building the map, the later value replaces the earlier one. If the list subsequently changes, the index must be updated or rebuilt. And because a map lookup can return null, take care when nullable values are allowed: map[key] == null would not distinguish an absent key from a key mapped to null; containsKey(key) does.

Compare concrete implementations, not just interfaces

Big-O notation describes how work scales, but an interface alone does not promise a particular implementation. The table below describes typical array-backed and hash-based choices on Android/JVM. Hash-operation times are expected averages; collisions can degrade them, and resizing or rehashing occasionally makes one insertion more expensive.

All five use $O(n)$ storage as the number of stored items grows; their constants and spare capacity differ. Hash tables also need stable equality and hash codes for stored keys or set elements. Recall last lesson’s warning about mutable data-class properties: changing a property involved in equals() and hashCode() after placing that object in a hash set or using it as a map key can make lookup fail.

For a closer look at the set guarantees and memory trade-off, read the standard library API’s performance and usage notes.

Apply the distinctions to three product requirements:

• Show articles in feed order, including possible repeated entries: keep a List. Neither a set’s uniqueness nor a map’s key lookup replaces positional display order.
• Check whether an ID is bookmarked; display order comes from the feed: use a HashSet<String> for membership. Its own iteration order is irrelevant.
• Display bookmarks in the order the user first saved them: a LinkedHashSet<String> provides uniqueness and insertion-order iteration. That is not alphabetical or “most recently saved first”: adding an existing ID again does not move it to the end.

A small list can still be the better engineering choice for occasional searches: it needs no separate index to maintain and may use less memory. Conversely, repeatedly scanning a large list for IDs is a reason to consider a map or set. State the expected data size and access pattern before claiming either choice is faster.

Key takeaways

Choose a List for positions and duplicates, a Set for uniqueness and membership, and a Map for values addressed by unique keys. An array-backed list offers fast indexed access but costly middle insertion; hash-based structures usually offer fast keyed operations in exchange for extra storage. Decide separately whether iteration order matters: LinkedHashSet and LinkedHashMap preserve insertion order, while HashSet and HashMap do not promise it.

The senior-level answer is not just a type name. It includes which operation dominates, what order the feature requires, what extra state must stay synchronized, and whether the memory cost is justified. Next lesson, we’ll use extension functions and higher-order functions to express operations on these collections without hiding those choices.