A Linked List is a common data structure made of a chain of nodes in which each Node contains a value and a pointer to the next node in the chain. The head pointer points to the first node and the last element of the first node and last element of the list points to NULL. When the list is empty, the head pointer points to NULL.

data class Node(val value: Int){ 
    var next : Node? = null
}

-> In simple words, a linked lists consists of nodes where each node contains a data field and a reference (link) to the next node in the list.

Linked lists can dynamically increase in size and it is easy to insert and delete from a linked list because unlike arrays, we only need to change the pointer of the previous element and the next element to insert or delete and element.

Time Complexities :D

• Look Up

By Value -> O(n) By Index -> O(n)

• Insertion

At The End -> O(1) At The Beginning -> O(1) In The Middle -> O(n)

• Deletion

From The Beginning -> O(1) From The End -> O(n) From The Middle -> O(n)

Implementation <33

class MyLinkedList {

    private var first: Node? = null
    private var last: Node? = null
    private var size: Int = 0

    fun addLast(value: Int) {
        val node = Node(value)
        // if array is empty
        if (first == null) {
            first = node
            last = node
        } else {
            last?.next = node
            last = node
        }
        size++
    }

    fun addFirst(value: Int) {
        val node = Node(value)
        if (first == null) {
            first = node
            last = node
        } else {
            node.next = first
            first = node
        }
        size++
    }

    fun removeFirst() {
        if (isEmpty()) throw Exception("No Such Index Exists")
        if (first == last) {
            // if there's only one item in the list...
            first = null
            last = null
        } else {
            val second = first?.next
            first?.next = null
            val first = second
        }
        size--
    }

    fun removeLast() {
        if (isEmpty()) throw Exception("No Such Index Exists")
        val previousLast = getPrevious(last)
        if (first == last) {
            // if there's only one item in the list...
            first = null
            last = null
        } else {
            last = previousLast
            last?.next = null
        }
        size--
    }

    fun toArray(): Array<Int> {
        val array = Array(size){0}
        var index = 0
        var currentNode : Node? = first
        while (currentNode != null) {
            array[index++] = currentNode.value
            currentNode = currentNode.next
        }
        return array
    }

    fun getSize(): Int = size

    private fun getPrevious(node: Node?): Node? {
        var current: Node? = first
        while (current != null) {
            if (current.next == node) return current
            current = current.next
        }
        return null
    }

    fun printList() {
        var currentNode: Node? = first
        while (currentNode != null) {
            println(currentNode.value)
            currentNode = currentNode.next
        }
    }

    fun indexOf(value: Int): Int {
        if (isEmpty()) return -1
        var currentNode: Node? = first
        var index: Int = 0
        while (currentNode != null) {
            if (currentNode.value == value) return index
            index++
            currentNode = currentNode.next
        }

        return -1
    }

    fun contains(value: Int): Boolean = indexOf(value) != -1

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

}