Linked List in Kotlin
Linked List in Kotlin
1.Before you begin:
In this blog we will learn how to implement Linked list in Kotlin and some basic operations that can be performed on Linked List.
Introduction:
Linked List is a type of Linear Data Structure that is the second most used data structure after the array, which allocates memory dynamically at run time that is it doesn’t require any size initialization as in the case of an array.
Linked List stores data in the form of nodes, which is divided into two parts, the first part stores the data and the second part points to the next node by storing the address of that node. In the simplest form, each node is composed of data and a reference to the next node in the sequence.
Some of the basic operations that can be performed in Linked List are below:
(1) Add
(2) Delete
(3) Find
The first element in the linked list will be called “Head” and the last element in the linked list will be called “Tail”.
Prerequisites:
- Experience with Kotlin syntax and basic knowledge of Linked List
What you’ll do ?
A sample application that demonstrates a linked list and its basic operations .
2.Getting Setup :
Explanation:
Step 1: Create a Node to maintain value and reference to next node
The above step is implemented using data class and overrided toString() method to print the linked list.
Code Sample:
data class Node<T>(var value: T, var next: Node<T>? = null) {
override fun toString(): String {
return if (next != null) {
"$value -> ${next.toString()}"
} else {
"$value"
}
}
}Step 2: Initialization of Head and Tail nodes
Every linked list will have a Head and a Tail nodes. If there is a single node, then the node itself will be Head and Tail.
Initialize the Head and Tail nodes to null and size variable that keeps track of size of linked list.
private var head: Node<T>? = null
private var tail: Node<T>? = null
private var size = 0Step 3: Add a node to Head
fun push(value: T) {
head = Node(value = value, next = head)
if (tail == null) {
tail = head
}
size++
}The above always adds new node to Head. A new Node is created and assigned to “head” and if tail is null then initialize tail to “head” . Always increment the size variable to keep track of size of linked list.
Step 4: To add a Node to the Tail
In this step a node is added to Tail which means appended to the end of the linked list
fun addAtTail(value: T) {
if (isEmpty()) {
push(value)
return
}
tail?.next = Node(value = value)
tail = tail?.next
size++
}There is an isEmpty() that keeps track of size of list, it checks whether list is empty or not.
If the list is empty we just create new node which can be created by calling push() method
If there is already some value to the tail, we will just point “next” of the current tail to newly created node and update the tail to newly created node.
Always increase the size
Step 4: Fetch value of linked list based on index
In this step , we fetch value of linked list based on index provided. We traverse through the entire list till we reach the index and retrieve value from node at that index.
If the index provided is greater than the size of the list , we return -1 as no node exists with that index.
fun get(index: Int): Int? {
var currentNode = head
var currentIndex = 0
return if(index >= size) {
-1
} else{
while (currentNode != null && currentIndex < index) {
currentNode = currentNode.next
currentIndex++
}
currentNode?.value.toString().toInt()
}
}Step 5: Add a node at specific index in the linked list
In order to achieve this we traverse the list till we reach the index and just point the next reference of newly created node to next node in that list and the previous node’s (node at given index) next to newly created node.
If the size of index is greater than size of list , just add node to tail
If the index is 0, then add the node to the head .
fun addAtIndex(index: Int, `val`: T) {
var currentNode = head
var newNode:Node<T>? = null
var previousNode:Node<T>? = null
var currentIndex = 0
if(index >= size){
addAtTail(`val`)
}else if(size > 0 && index == 0){
push(`val`)
}
else {
while (currentNode != null && currentIndex < index) {
previousNode = currentNode
currentNode = currentNode.next
currentIndex++
}
newNode = Node(value = `val`, next = currentNode)
previousNode?.next = newNode
size++
}
}Step 6: Delete a node at index
A method will be provided to delete a node at specific index.
If index is zero:
We need to check 2 conditions whether there is only one node in list or there are multiple nodes.
If the size of list is 1 , just make that node as null, probably head
If the size is greater than 1 and index is 0,we need to point head to next node and make current head to null.
The other condition is we traverse to that index and change the references of its previous and next nodes by making the node at index to null.
The last condition , if the index that we need to delete is tail, just set the previous node to tail and make current tail as null.
Also we decrement the size variableof list as we are deleting a node from the list.
fun deleteAtIndex(index: Int) {
// 1
var currentNode = head
var currentIndex = 0
var previousNode: Node<T>? = null
if (index < size) {
if (index == 0) {
if (size > 1) {
head = currentNode?.next
currentNode?.next = null
size--
} else if (size == 1) {
currentNode = null
size--
}
} else {
// 2
while (currentNode != null && currentIndex < index) {
previousNode = currentNode
currentNode = currentNode.next
currentIndex++
}
previousNode?.next = currentNode?.next
currentNode?.next = null
if(previousNode?.next == null){
tail = previousNode
}
size--
}
}
}We create a class called linked list and include all these methods in that class.
Congratulations:
In this blog we have covered the basic operations of implementing single linked list in Kotlin.