Kotlin: Implement Linked List

1. Introduction

A Linked List is a sequence of nodes that hold data and point to the next node. Unlike arrays, linked lists are dynamic in nature, allowing for efficient insertions and deletions. In this guide, we will detail how to implement a singly linked list in Kotlin.

2. Program Overview

Our linked list will support the following operations:

1. Add an element to the end of the list.

2. Remove an element from the end of the list.

3. Display the contents of the list.

The building block of the linked list is the Node which will store the data and reference to the next node.

3. Code Program

// Definition of a Node
class Node(var data: Int, var next: Node? = null)

// Definition of LinkedList
class LinkedList {
    private var head: Node? = null   // Head of the list, starts as null indicating an empty list.

    // Add an element to the end of the list
    fun append(data: Int) {
        if (head == null) {
            head = Node(data)
            return
        }
        var current = head
        while (current?.next != null) {
            current = current?.next
        }
        current?.next = Node(data)
    }

    // Remove the last element
    fun removeLast() {
        var current = head
        if (current?.next == null) {
            head = null
            return
        }
        while (current?.next?.next != null) {
            current = current?.next
        }
        current?.next = null
    }

    // Display the list elements
    fun display() {
        var current = head
        while (current != null) {
            print("${current.data} -> ")
            current = current.next
        }
        println("null")
    }
}

fun main() {
    val list = LinkedList()

    list.append(5)
    list.append(10)
    list.append(15)
    list.display()

    list.removeLast()
    list.display()
}

Output:

5 -> 10 -> 15 -> null
5 -> 10 -> null

4. Step By Step Explanation

1. Node Declaration:

- Each Node contains data and a reference to the next node (initially null).

2. LinkedList Initialization:

- The LinkedList class contains a reference to the head node, which starts as null indicating an empty list.

3. Append Operation:

- If the list is empty (head is null), a new node is created, and the head points to it.

- Otherwise, traverse the list until the end is reached and then add the new node.

4. RemoveLast Operation:

- If the list has only one element, set the head to null.

- Otherwise, traverse the list until the second last node is reached. The next of this node is set to null to remove the last node.

5. Display Function:

- Iterate through the list, and print each node's data until the list end is reached. 

The main function showcases the linked list's usage. We add three elements, display the list, remove the last element, and then display the list again. 

Through this program, learners can understand the foundational principles behind a singly linked list and its primary operations in Kotlin.