**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 = 0

Step 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.