A few years ago, I interviewed a candidate who was a powerhouse with the Android framework. They could build a complex UI in their sleep and understood Coroutines inside and out. But when I asked them to implement a simple singly linked list on the whiteboard, they froze. They tried to use an ArrayList to simulate the behavior, which completely defeated the purpose of the exercise. It was a wake-up call for them—and a reminder for me—that there is a massive difference between knowing how to use a library and understanding the memory structures that make those libraries work. You might never write a custom linked list in your day-to-day job, but thinking through the pointers is the best way to sharpen your mental model of how objects live in the heap.

Building the Atomic Node

At its core, a linked list isn't a single entity; it's a chain of small, independent objects. In Kotlin, we represent this with a Node class. Since we want our list to be flexible, we'll use a generic type T. The key here is the next property. It has to be nullable because the very last node in your chain points to nothing—the end of the line.

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

I prefer using a data class here for simplicity, though a regular class works too. The most important thing to remember is that next is a reference. When you change next, you aren't moving the data; you're just changing where the "arrow" points.

Wiring the List Logic

Now we need a wrapper class to manage these nodes. You don't want the user of your list to have to manually track the head (the first node). The LinkedList class handles the entry point and the logic for traversing the chain. While you could just track the head, I always recommend keeping a tail reference as well. Without a tail, adding an element to the end of the list becomes an O(n) operation because you have to walk through every single node just to find the end. With a tail, it's O(1).

class MyLinkedList<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun add(value: T) {
        val newNode = Node(value)
        if (head == null) {
            head = newNode
            tail = newNode
        } else {
            // Attach the new node to the current tail and move the tail forward
            tail?.next = newNode
            tail = newNode
        }
    }

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

Navigating the Nullability Minefield

The "whiteboard" part of this exercise is where most developers stumble: handling the edges. What happens if you try to remove an item from an empty list? What if the list only has one item? In Kotlin, the type system helps us, but you still have to be explicit about your null checks. When removing a node, you essentially have to "leapfrog" it. You find the node before the one you want to delete and point its next reference to the node after the target.

This is where the logic gets fiddly. If you're removing the head, the head moves to the second node. If you're removing the tail, you have to traverse the whole list again to find the new second-to-last node to update the tail reference. It's tedious, but that's exactly why this is a classic interview question—it tests your ability to handle state transitions without crashing the program.

📋 Practical Task

Exercise: Implement a Middle-Element Finder for MyLinkedList

In a real interview, you're rarely asked to just build the list; you're asked to perform an operation on it. Your task is to add a function called findMiddle() to the MyLinkedList class provided in the lesson.

The Constraints:

• You cannot use a counter to track the size of the list (no list.size / 2).
• You must use the "Fast and Slow Pointer" technique: one pointer moves one step at a time, while another moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be exactly in the middle.

Requirements:

1. Modify the MyLinkedList class to include the findMiddle() method.
2. The method should return the value of the middle node, or null if the list is empty.
3. Test your implementation with lists of both even and odd lengths to ensure the pointer logic holds up.