Linked List in Kotlin : Implementing and Appending elements

Linked lists are fundamental data structures where elements are stored sequentially. Each element holds a value and a reference to the next element, forming chain like structure. In Kotlin, creating a linked list involves defining a class for the nodes and implementing various operations to manipulate the list. Let’s create a linked list in Kotlin.

In Kotlin, one can construct a linked list by employing classes to define nodes and handle the connections among them.

Step 1: Create a Node Class

Create a Node class to represent each element in the linked list. Each node should have a value and a reference to the next node.`

class Node<T>(val value: T){
    var next:Node<T>? = null
}

Step 2: LinkedList Class

Create a LinkedList class that will manage the nodes and provide operations to manipulate the linked list.

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

    // add a new node to the end of the list
    fun append(value: T)
    {
        val newNode = Node(value)
        if(head == null)
        {
            head = newNode
        }
        else {
            var current = head
            while(current?.next != null)
            {
                current = current.next
            }
            current?.next = newNode
        }
    }
    // Print the elements of the linked list
    fun showLinkedList() {
        var current = head
        while (current!=null)
        {
            print("${current.value} -> ")
            current = current.next
        }
        println("null")
    }
}

Step 3: Using the LinkedList in Kotlin

You can now use the LinkedList class to create and manipulate linked lists.

fun main() {
val linkedList = LinkedList<Int>()
// adding elements to the linked list
linkedList.append(3)
linkedList.append(7)
linkedList.append(89)
linkedList.append(11)

// printing the linked list
println("Linked List:")
linkedList.showLinkedList()

}

Complete Program Example : LinkedList.kt

class Node<T>(val value: T){
    var next:Node<T>? = null
}


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

    // add a new node to the end of the list
    fun append(value: T)
    {
        val newNode = Node(value)
        if(head == null)
        {
            head = newNode
        }
        else {
            var current = head
            while(current?.next != null)
            {
                current = current.next
            }
            current?.next = newNode
        }
    }
    // Print the elements of the linked list
    fun showLinkedList() {
        var current = head
        while (current!=null)
        {
            print("${current.value} -> ")
            current = current.next
        }
        println("null")
    }
}


fun main() {
val linkedList = LinkedList<Int>()
// adding elements to the linked list
linkedList.append(3)
linkedList.append(7)
linkedList.append(89)
linkedList.append(11)

// printing the linked list
println("Linked List:")
linkedList.showLinkedList()

}

Output :

Linked List:
3 -> 7 -> 89 -> 11 -> null

This is a basic implementation of a singly linked list in Kotlin. You can further enhance it by adding operations like inserting at a specific position, deleting a node, or reversing the linked list.

Removing an element from the LinkedList

To remove an element from a linked list in Kotlin, you need to locate the node containing the desired value and update the references accordingly.

fun remove(value: T)
    {
        var current = head
        var previous: Node<T>? = null
        // Traverse the list to find the node with the specified value
        while (current!=null && current.value !=value)
        {
            previous = current
            current = current.next
        }
        // if value is not found
        if(current == null) {return}

        // update the ref.
        if(previous ==null){
            head = current.next}
         else{
             previous.next = current.next
         }
    }

Linked List:
3 -> 7 -> 89 -> 11 -> null
After Removing
3 -> 7 -> 11 -> null

LinkedList.kt

Open the Kotlin Playground and write the following code.

class Node<T>(val value: T){
    var next:Node<T>? = null
}


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

    // add a new node to the end of the list
    fun append(value: T)
    {
        val newNode = Node(value)
        if(head == null)
        {
            head = newNode
        }
        else {
            var current = head
            while(current?.next != null)
            {
                current = current.next
            }
            current?.next = newNode
        }
    }
    // Print the elements of the linked list
    fun showLinkedList() {
        var current = head
        while (current!=null)
        {
            print("${current.value} -> ")
            current = current.next
        }
        println("null")
    }

    fun remove(value: T)
    {
        var current = head
        var previous: Node<T>? = null
        // Traverse the list to find the node with the specified value
        while (current!=null && current.value !=value)
        {
            previous = current
            current = current.next
        }
        // if value is not found
        if(current == null) {return}

        // update the ref.
        if(previous ==null){
            head = current.next}
         else{
             previous.next = current.next
         }
    }
}


fun main() {
val linkedList = LinkedList<Int>()
// adding elements to the linked list
linkedList.append(3)
linkedList.append(7)
linkedList.append(89)
linkedList.append(11)

// printing the linked list
println("Linked List:")
linkedList.showLinkedList()

// Remove element with value 89
linkedList.remove(89)
println("After Removing")
linkedList.showLinkedList()



}

Applications of Linked list

Linked lists are often used in every application that needs a proper memory management system and a better cache implementation. Let’s dive deep into some of the cool applications of linked list. Linked lists serve as foundational structures for other data structures like stacks, queues, and graphs.

1. File Systems

In file systems, linked lists can be used to maintain the structure of directories or manage file allocation.

2. Music Players

The playlists in music players are often implemented using linked lists. Each node represents a track or video, linked to the next one in the playlist.

3. Cache Implementation

Linked lists are used in cache implementations where the least recently used items are removed efficiently by rearranging the list.