Singly Linked List in Kotlin

by

A Singly Linked List is a specialized case of a generic linked list. In a singly linked list, each node links to only the next node in the sequence, i.e if we start traversing from the first node of the list, we can only move in one direction.

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

The Node class represents a node in the list, with a data property to store the element and a next property to reference the next node in the list.

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

The LinkedList class represents the list itself, with a head property to reference the first node, a tail property to reference the last node, and a size property to keep track of the number of nodes in the list. The class also provides methods to add and remove nodes from the list, check if the list is empty, and get the size of the list.

Kotlin
fun size(): Int {
    var count = 0
    var current = head
    while (current != null) {
        count++
        current = current.next
    }

size(): Returns the number of nodes in the list.

Kotlin
fun addFirst(data: T) {
    val newNode = Node(data)
    if (isEmpty()) {
        head = newNode
        tail = newNode
    } else {
        newNode.next = head
        head = newNode
    }
}

The addFirst method adds a node with the given element to the beginning of the list. If the list is empty, the new node becomes both the head and the tail of the list. Otherwise, the new node’s next property is set to the current head, and the new node becomes the new head.

Kotlin
fun addLast(data: T) {
    val newNode = Node(data)
    if (isEmpty()) {
        head = newNode
        tail = newNode
    } else {
        tail?.next = newNode
        tail = newNode
    }
}

addLast(data: T): Adds a new node with the given data at the end of the list.

Kotlin
fun removeFirst(): T? {
    if (isEmpty()) {
        return null
    }
    val data = head?.data
    if (head == tail) {
        head = null
        tail = null
    } else {
        head = head?.next
    }
    return data
}

removeFirst(): Removes the first node from the list and returns its data.

Kotlin
fun removeLast(): T? {
    if (isEmpty()) {
        return null
    }
    val data = tail?.data
    if (head == tail) {
        head = null
        tail = null
    } else {
        var current = head
        while (current?.next != tail) {
            current = current?.next
        }
        current?.next = null
        tail = current
    }
    return data
}

removeLast(): Removes the last node from the list and returns its data.

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

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

    fun isEmpty(): Boolean {
        return head == null
    }

    fun size(): Int {
        var count = 0
        var current = head
        while (current != null) {
            count++
            current = current.next
        }
        return count
    }

    fun addFirst(data: T) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            tail = newNode
        } else {
            newNode.next = head
            head = newNode
        }
    }

    fun addLast(data: T) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            tail = newNode
        }
    }

    fun removeFirst(): T? {
        if (isEmpty()) {
            return null
        }
        val data = head?.data
        if (head == tail) {
            head = null
            tail = null
        } else {
            head = head?.next
        }
        return data
    }

    fun removeLast(): T? {
        if (isEmpty()) {
            return null
        }
        val data = tail?.data
        if (head == tail) {
            head = null
            tail = null
        } else {
            var current = head
            while (current?.next != tail) {
                current = current?.next
            }
            current?.next = null
            tail = current
        }
        return data
    }

    override fun toString(): String {
        var current = head
        var string = ""
        while (current != null) {
            string += "${current.data} -> "
            current = current.next
        }
        string += "null"
        return string
    }
}
fun main() {
    val list = SinglyLinkedList<Int>()
    list.addFirst(1)
    list.addLast(2)
    list.addFirst(3)
    println(list) 											// Output: 3 -> 1 -> 2 -> null
    println("Size: ${list.size()}") 						// Output: Size: 3
    println("Removed first element: ${list.removeFirst()}") // Output: Removed first element: 3
    println(list) 											// Output: 1 -> 2 -> null
    println("Removed last element: ${list.removeLast()}") 	// Output: Removed last element: 2
    println(list) 											// Output: 1 -> null
}

Leave a Comment