Insert a Node Before Given Node in Kotlin | Linked List

by

Approach for inserting a new node before a given node value in a linked list:

  1. Create a new node with the data value you want to insert.
  2. If the linked list is empty, print a message indicating that the list is empty and return.
  3. If the value you want to insert before is in the first node of the linked list, insert the new node before the first node and update the head property to point to the new node. Return.
  4. Loop through the linked list and check whether the data value of the next node is equal to the value you want to insert before.
  5. If the value is found, insert the new node before the node with the value and return.
  6. If the value is not found, print a message indicating that the value was not found.

To insert a new node before a given node value in a linked list, Here’s an example Kotlin code:

Kotlin
class Node(var data: Int) {
    var next: Node? = null
}
class LinkedList {
    var head: Node? = null
    fun insertBefore(value: Int, newNode: Node) {
        if (head == null) {
            println("Linked list is empty")
            return
        }
        if (head!!.data == value) {
            newNode.next = head
            head = newNode
            return
        }
        var current = head
        while (current?.next != null) {
            if (current.next!!.data == value) {
                newNode.next = current.next
                current.next = newNode
                return
            }
            current = current.next
        }
        println("Value '$value' not found in linked list")
    }
}
// Example usage
fun main() {
    val ll = LinkedList()
    ll.head = Node(1)
    ll.head!!.next = Node(2)
    ll.head!!.next!!.next = Node(3)
    val newNode = Node(4)
    ll.insertBefore(2, newNode)
    // The linked list should now be 1 -> 4 -> 2 -> 3
}

Here’s a step-by-step explanation of the insertBefore method in the Kotlin code I provided earlier, which inserts a new node before a given node value in a linked list:

  1. The method takes two arguments: value, an integer value representing the node value before which we want to insert the new node, and newNode, a Node object representing the new node we want to insert.
  2. If the linked list is empty (i.e., the head property is null), the method prints a message indicating that the list is empty and returns.
  3. If the value we’re looking for is in the first node of the linked list (i.e., the data property of the head node is equal to value), we insert the new node before the first node by updating the next property of newNode to point to the current head, and then updating the head property to point to newNode. We then return from the method.
  4. If the value we’re looking for is not in the first node of the linked list, we initialize a variable called current to point to the first node in the list (i.e., the head property).
  5. We then iterate over the linked list using a while loop. The loop continues as long as current.next is not null (i.e., there are more nodes to traverse), and we use the null-safe call operator (?.) to ensure we don’t get a NullPointerException if current is null.
  6. Inside the loop, we check whether the data property of the next node in the list (i.e., current.next!!.data) is equal to value. If it is, we have found the node before which we want to insert the new node.
  7. We then update the next property of newNode to point to the node after current, which is the node with the value value. We do this by setting newNode.next equal to current.next.
  8. Finally, we update the next property of current to point to newNode, effectively inserting newNode into the linked list before the node with the value value.
  9. If the value we’re looking for is not found in the linked list, we print a message indicating that the value was not found.

The time complexity of inserting a node before a given node value in a linked list is O(n), where n is the number of nodes in the linked list. This is because in the worst case scenario, we may have to traverse the entire linked list to find the node with the value we want to insert before.

The space complexity of this operation is O(1), which is constant space, since we are only creating a single new node and not using any additional data structures that would require more memory as the size of the linked list grows.

Leave a Comment