Double LinkedList Deep Copy in Kotlin with Generics and Thread Safety

Question

Goal

• Return a deep copy of a double LinkedList.
• Each node also contains an additional random pointer, potentially to any node or null.

Code to start

data class Node<T>(
    var data: T?,
    var previous: Node<T>? = null,
    var next: Node<T>? = null,
    var random: Node<T>? = null

class LinkedList {
    // TODO: Implement deep copy here.
}

Questions

• Generics - Is there a better approach to handle the generic variance as to not need as T when passing in a generic type? i.e. linkedList.add(data = 1 as T)
• Add thread-safety for operations - Are there any specific recommendations on thread-safety for this solution or broader topics to research to understand thread-safety considerations further?

Implement

See the full code on GitHub.

LinkedList.kt

class Node<T>(
        var prev: Node<T>? = null,
        var next: Node<T>? = null,
        var rand: Node<T>? = null,
        var data: T
)

class LinkedList<T>(
        var first: Node<T>? = null,
        var last: Node<T>? = null,
        val randMap: HashMap<Node<T>?, Node<T>?> = hashMapOf()
) {
    // Add Node to the end of LinkedList
    fun add(data: T): Node<T> {
        val temp = last
        val newNode = Node(prev = temp, data = data)
        last = newNode
        if (temp == null)
            first = newNode
        else
            temp.next = newNode
        return newNode
    }

    fun deepCopyWithoutRandoms(prev: Node<T>?, node: Node<T>?): Node<T>? {
        return if (node == null)
            null
        else {
            val newNode = Node(data = node.data)
            if (node.rand != null) {
                newNode.rand = node.rand
                randMap.put(node.rand, null)
            }
            newNode.prev = prev
            newNode.next = deepCopyWithoutRandoms(newNode, node.next)
            if (randMap.containsKey(node))
                randMap.put(node, newNode)
            return newNode
        }
    }

    fun updateRandoms(node: Node<T>?): Node<T>? {
        if (node != null) {
            if (node.rand != null)
                node.rand = randMap.get(node.rand!!)
            updateRandoms(node.next)
            return node
        } else return null
    }

    fun clear() {
        var node = first
        while (node != null) {
            node.prev = null
            node.next = null
            node.rand = null
            node.data = 0 as T
            node = node.next
        }
    }

    fun toString(first: Node<T>?): String {
        var output = ""
        var node = first
        while (node != null) {
            output += String.format("(prev:%s next:%s data:%s random:%s)\n", node.prev, node.next, node.data, node.rand)
            node = node.next
        }
        return output
    }
}

Answer 1

I'm not going to touch on your question on thread safety as it is a broad topic I am not familiar with. However, I can help with your questions about generics.

Right now, you're using generics great, except in one single place

node.data = 0 as T

The type of node.data is T. This code will fail if T is not Int - for example, if T is String, the code will look like this:

node.data = 0 as String

and that will throw a runtime exception.

Here's the important thing, though. There's no reason to do node.data = <anything>. I assume the reason for having it originally was to "zero out" or get rid of the data as it's removed from the list - but that's what java will do for you automatically!

Let's say you have the following structure

linked list    /--> node 1   /--> value 1
-----------    |    ------   |    --------
first node ---/     data ---/        7

when you delete the pointer to node 1, you end up in this situation

linked list         node 1   /--> value 1
-----------         ------   |    --------
first node->null    data ---/        7

now that there is no reference anywhere to node 1, the jvm garbage collector deletes it

linked list         value 1
-----------         ------
first node->null        7

and because there is no reference to value 1, it's also deallocated.

This means that there's no reason to set the data field to anything - and, besides the point, there is no possible value you could set it to that would work for any value of T (in java, though, you could use null)