Circular Linked List in Kotlin

by

A circular linked list is a data structure in which the nodes form a circular sequence, where each node points to the next node, and the last node points back to the first node.

Kotlin
class Node(val data: Int, var next: Node? = null)

class CircularLinkedList {
    private var head: Node? = null
    private var tail: Node? = null

In this implementation, we define a Node class to represent each node in the linked list, and a CircularLinkedList class to represent the circular linked list. The head and tail fields point to the first and last nodes in the list, respectively.

Kotlin
fun isEmpty(): Boolean = head == null

fun insertAtEnd(data: Int) {
    val newNode = Node(data)
    if (isEmpty()) {
        head = newNode
        tail = newNode
        tail!!.next = head
    } else {
        tail!!.next = newNode
        tail = newNode
        tail!!.next = head
    }
}

The isEmpty method checks whether the list is empty. The insertAtEnd method inserts a new node with the given data at the end of the list. If the list is empty, we set both the head and tail to the new node and make it circular by setting its next field to itself. If the list is not empty, we update the tail to point to the new node and make it circular by setting its next field to the head.

Kotlin
fun delete(data: Int) {
    if (isEmpty()) return

    var prev: Node? = null
    var current = head
    while (current!!.data != data) {
        if (current.next == head) return // Element not found
        prev = current
        current = current.next
    }

    if (prev == null) { // Element is at the head
        if (head!!.next == head) { // Only one element in the list
            head = null
            tail = null
        } else {
            head = head!!.next
            tail!!.next = head
        }
    } else if (current == tail) { // Element is at the tail
        prev.next = head
        tail = prev
    } else { // Element is in the middle
        prev.next = current.next
    }
}

The delete method deletes the node with the given data from the list. If the list is empty, we simply return. We traverse the list to find the node with the given data, keeping track of the previous node (prev) and the current node (current). If the element is not found, we return. If the element is at the head, we update the head to the next node and make the list circular again by setting the next field of the tail to the head. If the element is at the tail, we update the tail to point to the previous node. If the element is in the middle, we update the next field of prev to point to current.next, effectively skipping over current.

Kotlin
fun display() {
    if (isEmpty()) return

    var current = head
    do {
        print("${current!!.data} ")
        current = current.next
    } while (current != head)
    println()
}

The display method traverses the list and prints the data of each node. We start at the head and continue until we reach the tail. Since this is a circular linked list, we need to check whether we have reached the head again before stopping.

Kotlin
class Node(val data: Int, var next: Node? = null)

class CircularLinkedList {
    private var head: Node? = null
    private var tail: Node? = null

    fun isEmpty(): Boolean = head == null

    fun insertAtEnd(data: Int) {
        val newNode = Node(data)
        if (isEmpty()) {
            head = newNode
            tail = newNode
            tail!!.next = head
        } else {
            tail!!.next = newNode
            tail = newNode
            tail!!.next = head
        }
    }

    fun delete(data: Int) {
        if (isEmpty()) return

        var prev: Node? = null
        var current = head
        while (current!!.data != data) {
            if (current.next == head) return // Element not found
            prev = current
            current = current.next
        }

        if (prev == null) { // Element is at the head
            if (head!!.next == head) { // Only one element in the list
                head = null
                tail = null
            } else {
                head = head!!.next
                tail!!.next = head
            }
        } else if (current == tail) { // Element is at the tail
            prev.next = head
            tail = prev
        } else { // Element is in the middle
            prev.next = current.next
        }
    }

    fun display() {
        if (isEmpty()) return

        var current = head
        do {
            print("${current!!.data} ")
            current = current.next
        } while (current != head)
        println()
    }
}

fun main() {
    val cll = CircularLinkedList()
    cll.insertAtEnd(1)
    cll.insertAtEnd(2)
    cll.insertAtEnd(3)
    cll.insertAtEnd(4)
    cll.insertAtEnd(5)
    cll.display() // Output: 1 2 3 4 5
    cll.delete(3)
    cll.display() // Output: 1 2 4 5
}

In the main function, we create a new CircularLinkedList, insert five nodes using the insertAtEnd method, and display the list using the display method. Finally, we delete the node with data 3 using the delete method and display the updated list. The output should be 1 2 3 4 5 followed by 1 2 4 5.

Leave a Comment