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
 }
}

• Carson Graham: Does this answer your question? Double LinkedList Deep Copy in Kotlin
• adamhurwitz.eth: Thanks for the suggestion @CarsonGraham. The linked question does not answer the question above as it does not cover the topics of Generics and Thread Safety.
• Carson Graham: ah, I see now. Give me a minute
• pacmaninbw: This question ended up in the close vote queue as a duplicate of the original, which it wasn't. When you ask a follow up question to something closely related I recommend you provide a link to the original question as well.

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)

• adamhurwitz.eth: Thank you for the thorough response regarding generic usage @Carson Graham. I've refactored the clear function in this commit to not "zero out" the data as the Java garbage collection will delete unreferenced resources as you outlined.