Linked List Implementation in Kotlin

1. Introduction

In this tutorial, we will learn how to implement a simple Linked List data structure using Kotlin programming language.

A Linked List is a linear data structure where each element is a separate object. Each element (or node) of a linked list comprises two items: the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list.

2. Implementation Steps

1. Define a Node class with two properties: data and next.

2. Define a LinkedList class which will contain various linked list operations.

3. Implement the append method to add data to the end of the linked list.

4. Implement the prepend method to add data to the start of the linked list.

5. Implement the deleteWithValue method to remove a node with a specific value.

6. Implement the display method to view the linked list.

3. Implementation in Kotlin Programming

class Node<T>(var data: T, var next: Node<T>? = null)
class LinkedList<T> {
    private var head: Node<T>? = null
    
    // 3. Implement the `append` method
    fun append(data: T) {
        if (head == null) {
            head = Node(data)
            return
        }
        var current = head
        while (current?.next != null) {
            current = current?.next
        }
        current?.next = Node(data)
    }
    
    // 4. Implement the `prepend` method
    fun prepend(data: T) {
        val newHead = Node(data, head)
        head = newHead
    }
    
    // 5. Implement the `deleteWithValue` method
    fun deleteWithValue(data: T) {
        if (head == null) return
        if (head?.data == data) {
            head = head?.next
            return
        }
        var current = head
        while (current?.next != null && current.next?.data != data) {
            current = current.next
        }
        current?.next = current?.next?.next
    }
    
    // 6. Implement the `display` method
    fun display(): List<T> {
        val result = mutableListOf<T>()
        var current = head
        while (current != null) {
            result.add(current.data)
            current = current.next
        }
        return result
    }
}

// Client code to demonstrate the linked list functionality
val ll = LinkedList<Int>()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
println(ll.display())  // Expected Output: [0, 1, 2, 3]
ll.deleteWithValue(2)
println(ll.display())  // Expected Output: [0, 1, 3]

Output:

[0, 1, 2, 3]
[0, 1, 3]

Explanation:

1. A Node class is defined with type parameter T. Each node has data and a reference to the next node, which is initialized as null.

2. A LinkedList class is defined with a private head reference, which will point to the first node in the linked list.

3. The append method starts from the head and traverses the list to find the last node, then appends the new node to the end.

4. The prepend method adds a new node at the beginning of the list by shifting the current head of the list.

5. The deleteWithValue method starts from the head and traverses the list to find the node with the specified value, then removes it.

6. The display method starts from the head and traverses the list, collecting the data in each node to display the entire list.