Doubly Linked List Implementation in Kotlin

In this source code example, we will write a code to implement the Doubly Linked List data structure using the Kotlin programming language.

A doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly-linked list, a node consists of three parts: node data, a pointer to the next node in sequence (next pointer), and a pointer to the previous node (previous pointer).

A doubly linked list might be useful when working with something like a list of web pages, which has each page containing a picture, a link to the previous page, and a link to the next page. For a simple list of numbers, a linked list and a doubly-linked list may look the same, e.g., [3, 1, 4, 2, 5]. However, the doubly linked list also has an easy way to get the previous element, as well as the next element.

Doubly Linked List Implementation in Kotlin

Let's Implement Doubly Linked List to perform the below operations:
    getFirst()
    add()
    get()
    set()
    removeFirst()
    removeLast()
    removeValue()
    addAll()
Here is the complete code for your reference:

class DoublyLinkyList<E> {
    private var size = 0
    private var head: Node<E>? = null
    private var tail: Node<E>? = null

    private inner class Node<E> constructor(internal var prev: Node<E>?, internal var element: E, internal var next: Node<E>?)

    fun getFirst() = head?.element

    fun getLast() = tail?.element

    fun removeFirst() = unlinkHead()

    fun removeLast() = unlinkTail()

    fun addFirst(element: E) {
        linkHead(element)
    }

    fun addLast(element: E) {
        linkTail(element)
    }

    fun add(element: E) {
        linkTail(element)
    }

    fun <T> addAll(index: Int, arr: Array<T>): Boolean where T : E {
        validatePositionIndex(index)

        val numNew = arr.size
        if (numNew == 0) return false

        var pred: Node<E>?
        var succ: Node<E>?
        when (index) {
            0 -> {
                succ = head
                pred = null
            }
            size -> {
                succ = null
                pred = tail
            }
            else -> {
                succ = node(index)
                pred = succ.prev
            }
        }

        for (item in arr) {
            val e = item as E
            val newNode = Node<E>(pred, e, null)
            if (pred == null)
                head = newNode
            else
                pred.next = newNode
            pred = newNode
        }

        if (succ == null) {
            tail = pred
        } else {
            pred!!.next = succ
            succ!!.prev = pred
        }

        size += numNew
        return true
    }

    fun remove(element: E): Boolean {
        var curr = head
        while (curr != null) {
            if (curr.element == element) {
                unlink(curr)
                return true
            }
            curr = curr.next
        }
        return false
    }

    fun clear() {
        var x = head
        while (x != null) {
            val next = x.next
            x.next = null
            x.prev = null
            x = next
        }
        tail = null
        head = tail
        size = 0
    }

    fun size() = size

    operator fun contains(element: E) = indexOf(element) != -1

    fun get(index: Int): E {
        validateElementIndex(index)
        return node(index).element
    }

    fun set(index: Int, element: E): E {
        validateElementIndex(index)
        val x = node(index)
        val oldVal = x.element
        x.element = element
        return oldVal
    }

    fun add(index: Int, element: E) {
        validatePositionIndex(index)
        if (index == size) {
            linkTail(element)
        } else {
            linkBefore(element, node(index))
        }
    }

    fun remove(index: Int): E {
        validateElementIndex(index)
        return unlink(node(index))
    }

    fun indexOf(element: E): Int {
        var index = 0
        var x = head
        while (x != null) {
            if (element == x.element)
                return index
            index++
            x = x.next
        }
        return -1
    }

    private fun linkHead(element: E) {
        val h = head
        val newNode = Node<E>(null, element, h)
        head = newNode
        if (h == null) {
            tail = newNode
        } else {
            h.prev = newNode
        }
        size++
    }

    private fun linkTail(element: E) {
        val t = tail
        val newNode = Node<E>(t, element, null)
        tail = newNode
        if (t == null) {
            head = newNode
        } else {
            t.next = newNode
        }
        size++
    }

    private fun linkBefore(element: E, succ: Node<E>) {
        val pred = succ.prev
        val newNode = Node(pred, element, succ)
        succ.prev = newNode
        if (pred == null) {
            head = newNode
        } else {
            pred.next = newNode
        }
        size++
    }

    private fun unlinkHead() {
        head?.let {
            val next = it.next
            it.next = null
            head = next
            if (next == null) {
                tail = null
            } else {
                next.prev = null
            }
            size--
        }
    }

    private fun unlinkTail() {
        tail?.let {
            val prev = it.prev
            it.prev = null
            tail = prev
            if (prev == null) {
                head = null
            } else {
                prev.next = null
            }
            size--
        }
    }

    private fun unlink(curr: Node<E>): E {
        val element = curr.element
        val next = curr.next
        val prev = curr.prev

        if (prev == null) {
            head = next
        } else {
            prev.next = next
            curr.prev = null
        }

        if (next == null) {
            tail = prev
        } else {
            next.prev = prev
            curr.next = null
        }

        size--
        return element
    }

    private fun node(index: Int): Node<E> {
        if (index < size shr 1) {
            var x = head
            for (i in 0 until index)
                x = x!!.next
            return x!!
        } else {
            var x = tail
            for (i in size - 1 downTo index + 1)
                x = x!!.prev
            return x!!
        }
    }

    private fun validateElementIndex(index: Int) {
        if (index < 0 || index >= size)
            throw IndexOutOfBoundsException(outOfBoundsMsg(index))
    }

    private fun validatePositionIndex(index: Int) {
        if (index < 0 && index > size)
            throw IndexOutOfBoundsException(outOfBoundsMsg(index))
    }

    private fun outOfBoundsMsg(index: Int): String {
        return "Index: $index, Size: $size"
    }

    override fun toString(): String {
        var curr = head
        if (curr == null) return "[]"
        else {
            val sb = StringBuilder()
            sb.append('[')
            while (curr != null) {
                sb.append(curr.element)
                curr = curr.next
                if (curr?.element == null) {
                    sb.append(']')
                } else {
                    sb.append(',').append(' ')
                }
            }
            return sb.toString()
        }
    }
}

fun main(args: Array<String>) {
    val doublyLinkyList = DoublyLinkyList<String>()
    println("First item of the linky list is - ${doublyLinkyList.getFirst()}")
    println("Last item of the linky list is - ${doublyLinkyList.getLast()}")

    println()
    doublyLinkyList.add("Kotlin")
    println("First item of the linky list is - ${doublyLinkyList.getFirst()}")
    println("Last item of the linky list is - ${doublyLinkyList.getLast()}")

    println()
    doublyLinkyList.add("Java")
    println("First item of the linky list is - ${doublyLinkyList.getFirst()}")
    println("Last item of the linky list is - ${doublyLinkyList.getLast()}")

    doublyLinkyList.add("C#")
    doublyLinkyList.add("Python")
    doublyLinkyList.add("JavaScript")

    println()
    println("Elements at doublyLinkyList - $doublyLinkyList")
    doublyLinkyList.remove("JavaScript")
    println("Elements at doublyLinkyList after removing JavaScript - $doublyLinkyList")
    doublyLinkyList.remove("Kotlin")
    println("Elements at doublyLinkyList after removing Kotlin - $doublyLinkyList")
    doublyLinkyList.remove("C#")
    println("Elements at doublyLinkyList after removing C# - $doublyLinkyList")
    doublyLinkyList.remove("Java")
    println("Elements at doublyLinkyList after removing Java - $doublyLinkyList")
    doublyLinkyList.remove("Python")
    println("Elements at doublyLinkyList after removing Python - $doublyLinkyList")

    testGetFirst()
    testAdd()
    testGet()
    testSet()
    testRemoveFirst()
    testRemoveLast()
    testRemoveValue()
    testAddAll()
}

fun testGetFirst() {
    println()
    println("==================================")
    println("getFirst method testing started")
    val doublyLinkyList = DoublyLinkyList<String>()
    println(doublyLinkyList.getFirst() == null)

    doublyLinkyList.add("Kotlin")
    println(doublyLinkyList.getFirst() == "Kotlin")

    doublyLinkyList.add("Java")
    println(doublyLinkyList.getFirst() == "Kotlin")

    doublyLinkyList.add("Python")
    println(doublyLinkyList.getFirst() == "Kotlin")

    doublyLinkyList.add(0, "Python")
    println(doublyLinkyList.getFirst() == "Python")

    doublyLinkyList.add(1, "JavaScript")
    println(doublyLinkyList.getFirst() == "Python")

    doublyLinkyList.set(0, "JavaScript")
    println(doublyLinkyList.getFirst() == "JavaScript")

    doublyLinkyList.set(1, "Kotlin")
    println(doublyLinkyList.getFirst() == "JavaScript")

    doublyLinkyList.addFirst("Kotlin")
    println(doublyLinkyList.getFirst() == "Kotlin")

    doublyLinkyList.addLast("JavaScript")
    println(doublyLinkyList.getFirst() == "Kotlin")

    println("getFirst method testing ended")
    println("==================================")
    println()
    doublyLinkyList.clear()
    println("Elements at LinkyList - $doublyLinkyList")

    doublyLinkyList.addFirst("Kotlin")
    println("Elements at LinkyList - $doublyLinkyList")

    doublyLinkyList.addFirst("Kotlin")
    println("Elements at LinkyList - $doublyLinkyList")

    doublyLinkyList.addFirst("Java")
    println("Elements at LinkyList - $doublyLinkyList")

    doublyLinkyList.addFirst("Python")
    println("Elements at LinkyList - $doublyLinkyList")
}

fun testAdd() {
    println()
    println("==================================")
    println("testAdd method testing started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")
    println("Elements at LinkyList - $doublyLinkyList")

    println()
    doublyLinkyList.add(1, "JavaScript")
    println("Elements at LinkyList - $doublyLinkyList")

    println()
    doublyLinkyList.add(2, "TypeScript")
    println("Elements at LinkyList - $doublyLinkyList")

    println()
    doublyLinkyList.add(3, "CofeeScript")
    println("Elements at LinkyList - $doublyLinkyList")

    println()
    doublyLinkyList.add(7, "MongoDB")
    println("Elements at LinkyList - $doublyLinkyList")

    println()
    doublyLinkyList.add(0, "SQL")
    println("Elements at LinkyList - $doublyLinkyList")

    println("testAdd method testing started")
    println("==================================")
}

fun testGet() {
    println()
    println("=================================")
    println("Testing get started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")

    println("0th Index - ${doublyLinkyList.get(0)}")
    println("1st Index - ${doublyLinkyList.get(1)}")
    println("2nd Index - ${doublyLinkyList.get(2)}")
    println("3rd Index - ${doublyLinkyList.get(3)}")
    println("4th Index - ${doublyLinkyList.get(4)}")
    println("Testing get ended")
    println("=================================")
}

fun testSet() {
    println()
    println("=================================")
    println("Testing set started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")

    println("0th Index - ${doublyLinkyList.set(0, "Edited Kotlin")}")
    println("1st Index - ${doublyLinkyList.set(1, "Edited Java")}")
    println("2nd Index - ${doublyLinkyList.set(2, "Edited C#")}")
    println("3rd Index - ${doublyLinkyList.set(3, "Edited C")}")
    println("4th Index - ${doublyLinkyList.set(4, "Edited C++")}")
    println("Final list - $doublyLinkyList")
    println("Testing set ended")
    println("=================================")
}

fun testRemoveFirst() {
    println()
    println("=================================")
    println("Testing removeFirst started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")

    println("List - $doublyLinkyList")
    doublyLinkyList.removeFirst()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeFirst()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeFirst()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeFirst()
    println("List - $doublyLinkyList")
    println("Testing removeFirst ended")
    println("=================================")
}

fun testRemoveLast() {
    println()
    println("=================================")
    println("Testing removeLast started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")

    println("List - $doublyLinkyList")
    doublyLinkyList.removeLast()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeLast()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeLast()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeLast()
    println("List - $doublyLinkyList")
    doublyLinkyList.removeLast()
    println("List - $doublyLinkyList")
    println("Testing removeLast ended")
    println("=================================")
}

fun testRemoveValue() {
    println()
    println("=================================")
    println("Testing testRemoveValue started")
    val doublyLinkyList = DoublyLinkyList<String>()
    doublyLinkyList.add("Kotlin")
    doublyLinkyList.add("Java")
    doublyLinkyList.add("C#")
    doublyLinkyList.add("C")
    doublyLinkyList.add("C++")

    println("JavaScript" in doublyLinkyList)
    println("Kotlin" in doublyLinkyList)

    println("List - $doublyLinkyList")
    doublyLinkyList.remove("Java")
    println("List - $doublyLinkyList")
    doublyLinkyList.remove("Kotlin")
    println("List - $doublyLinkyList")
    doublyLinkyList.remove("JavaScript")
    println("List - $doublyLinkyList")
    doublyLinkyList.remove("Python")
    println("List - $doublyLinkyList")
    println("Testing testRemoveValue ended")
    println("=================================")
}

fun testAddAll() {
    println()
    println("=================================")
    println("Testing testAddAll started")
    
    val doublyLinkyList = DoublyLinkyList<String>()

    // Add few elements at begining of the linkedlist
    doublyLinkyList.addAll(0, arrayOf<String>("C", "C++"))
    println("List - $doublyLinkyList")
    doublyLinkyList.addAll(0, arrayOf<String>("Java", "Kotlin"))
    println("List - $doublyLinkyList")
    // Add few elements at middle of the linkedlist
    doublyLinkyList.addAll(2, arrayOf<String>("Python", "R"))
    println("List - $doublyLinkyList")
    // Add few elements at end of the linkedlist
    doublyLinkyList.addAll(doublyLinkyList.size(), arrayOf<String>("C#", "MATLAB"))
    println("List - $doublyLinkyList")
    println("Testing testAddAll ended")
    println("=================================")
}

Output:

First item of the linky list is - null
Last item of the linky list is - null

First item of the linky list is - Kotlin
Last item of the linky list is - Kotlin

First item of the linky list is - Kotlin
Last item of the linky list is - Java

Elements at doublyLinkyList - [Kotlin, Java, C#, Python, JavaScript]
Elements at doublyLinkyList after removing JavaScript - [Kotlin, Java, C#, Python]
Elements at doublyLinkyList after removing Kotlin - [Java, C#, Python]
Elements at doublyLinkyList after removing C# - [Java, Python]
Elements at doublyLinkyList after removing Java - [Python]
Elements at doublyLinkyList after removing Python - []

==================================
getFirst method testing started
true
true
true
true
true
true
true
true
true
true
getFirst method testing ended
==================================

Elements at LinkyList - []
Elements at LinkyList - [Kotlin]
Elements at LinkyList - [Kotlin, Kotlin]
Elements at LinkyList - [Java, Kotlin, Kotlin]
Elements at LinkyList - [Python, Java, Kotlin, Kotlin]

==================================
testAdd method testing started
Elements at LinkyList - [Kotlin, Java, C#, C, C++]

Elements at LinkyList - [Kotlin, JavaScript, Java, C#, C, C++]

Elements at LinkyList - [Kotlin, JavaScript, TypeScript, Java, C#, C, C++]

Elements at LinkyList - [Kotlin, JavaScript, TypeScript, CofeeScript, Java, C#, C, C++]

Elements at LinkyList - [Kotlin, JavaScript, TypeScript, CofeeScript, Java, C#, C, MongoDB, C++]

Elements at LinkyList - [SQL, Kotlin, JavaScript, TypeScript, CofeeScript, Java, C#, C, MongoDB, C++]
testAdd method testing started
==================================

=================================
Testing get started
0th Index - Kotlin
1st Index - Java
2nd Index - C#
3rd Index - C
4th Index - C++
Testing get ended
=================================

=================================
Testing set started
0th Index - Kotlin
1st Index - Java
2nd Index - C#
3rd Index - C
4th Index - C++
Final list - [Edited Kotlin, Edited Java, Edited C#, Edited C, Edited C++]
Testing set ended
=================================

=================================
Testing removeFirst started
List - [Kotlin, Java, C#, C, C++]
List - [Java, C#, C, C++]
List - [C#, C, C++]
List - [C, C++]
List - [C++]
Testing removeFirst ended
=================================

=================================
Testing removeLast started
List - [Kotlin, Java, C#, C, C++]
List - [Kotlin, Java, C#, C]
List - [Kotlin, Java, C#]
List - [Kotlin, Java]
List - [Kotlin]
List - []
Testing removeLast ended
=================================

=================================
Testing testRemoveValue started
false
true
List - [Kotlin, Java, C#, C, C++]
List - [Kotlin, C#, C, C++]
List - [C#, C, C++]
List - [C#, C, C++]
List - [C#, C, C++]
Testing testRemoveValue ended
=================================

=================================
Testing testAddAll started
List - [C, C++]
List - [Java, Kotlin, C, C++]
List - [Java, Kotlin, Python, R, C, C++]
List - [Java, Kotlin, Python, R, C, C++, C#, MATLAB]
Testing testAddAll ended
=================================

Related C Programs with Output and Step-By-Step Explanation:

Kotlin- Create Class Example Kotlin - for Loop Examples Kotlin - while and do-while loop example Kotlin - if statement example Kotlin - Nested if Statement Example Kotlin - if-else Statement Example Kotlin - if-else-if Statement Example Kotlin - when Expression Example Kotlin - break and continue Keyword Example Kotlin - Nested Class Example Kotlin - Inner Class Example Kotlin - Inheritance Example Kotlin - Abstract Class Example Kotlin Interface Example Kotlin Interfaces Inheritance Example Kotlin - Enum Class Example Kotlin - Enum Class Implementing Interfaces Example kotlin - Data Class Example Kotlin - Array Initialization Example Kotlin Array Basic Operations Kotlin - Sorting Arrays Example Kotlin - Two-Dimensional Arrays Example Kotlin - Find Array Elements Example Kotlin array initialization example Kotlin array basic operations Kotlin array count example Kotlin array traversal example Kotlin filtering arrays example Sorting arrays in Kotlin example Kotlin String Looping Example Kotlin Remove Leading and Trailing Whitespaces Example Kotlin Remove All Whitespaces from a String Example Kotlin Empty/Blank String Example Kotlin String Case Example Kotlin Comparing Strings Example Kotlin String Interpolation Example Kotlin - Get First and Last Characters of a String Example Kotlin String Example Kotlin List drop Example Kotlin List all Example Kotlin List any Example Kotlin List filter Example Kotlin List slice() Example Kotlin List contains() Example Kotlin List Sort Example - Ascending and Descending Order Kotlin List Iterate Example - forEach(), for Loop, forEachIndexed() and ListIterator Kotlin List first and last Element Example Kotlin List Count Example Kotlin List Indexing Example Kotlin List Example Kotlin listOf() Example Kotlin Set all Example Kotlin Set any Example Kotlin Set filter Example Kotlin Set union Example Kotlin mutableSetOf() Example Kotlin Set contains Example Kotlin Set Sort Example - Ascending and Descending Order Kotlin Set Iterate Example - forEach(), for Loop, forEachIndexed() and Iterator Kotlin Set first and last Element Example Kotlin Set count Example Kotlin Set indexing Example Kotlin Set Example Kotlin setOf() Example Stack Implementation in Kotlin Queue Implementation in Kotlin Deque Implementation in Kotlin Singly Linked List Implementation in Kotlin Doubly Linked List Implementation in Kotlin Circular Linked List Implementation in Kotlin Bubble Sort Algorithm in Kotlin Heap Sort Algorithm in Kotlin Insertion Sort Algorithm in Kotlin Merge Sort Algorithm in Kotlin Quick Sort Algorithm in Kotlin Selection Sort Algorithm in Kotlin

Comments

Post a Comment