Linked List Operations

Welcome to our tutorial focusing on Linked List Operations in Kotlin. Singly linked lists (or just linked lists) are among the most fundamental data structures used in computer science. They provide an efficient way to manage data that is not necessarily contiguous in memory. While they lack the fast random access of arrays, they excel at sequential traversal and link updates, making them an indispensable tool in a programmer's toolkit.

To work with linked lists, we first need to define a ListNode class, which represents a node in the linked list. In Kotlin, we use a class with a constructor to define the structure and handle the potential absence of a next node using nullability.

class ListNode(
    var value: Int = 0,      // Holds the value or data of the node
    var next: ListNode? = null // Points to the next node; null means it's the end
)

// Initialization of linked list: 1 -> 2 -> 3 -> 4 -> 5
val head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

In the ListNode class:

• value holds the data of the node.
• next is a reference to the next node in the linked list. It is of type ListNode?, which means it can either hold a ListNode object or be null. It is null by default, meaning the node does not point to any other node when it is freshly created.

To understand this, first know that a linked list is a linear data structure where each element is a separate object known as a node. A node comprises data and a reference (link) to the next node in the sequence.

The provided code creates a linked list where each node points to another as follows: 1 -> 2 -> 3 -> 4 -> 5, and the last node points to null.

One example of a problem to practice involves reversing a linked list, a common operation in interviews and the industry. To reverse a linked list, we will need to sequentially rearrange the next link of each node to point toward its previous node.

Here is what the code looks like in Kotlin. Note that this code runs in $O(n)$ time, where $n$ is the number of nodes, and uses $O(1)$ additional memory:

class ListNode(var value: Int = 0, var next: ListNode? = null)

fun reverseLinkedList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var current = head
    
    while (current != null) {
        val nextNode = current.next // Save the next node
        current.next = prev         // Reverse the link
        prev = current              // Move prev forward
        current = nextNode          // Move current forward
    }
    
    return prev // New head of the reversed list
}

fun main() {
    // Test
    val head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    
    var reversedHead = reverseLinkedList(head)
    
    // Printing the reversed list
    while (reversedHead != null) {
        print("${reversedHead.value} ")
        reversedHead = reversedHead.next
    }
    // Output: 5 4 3 2 1 
}