# 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

// 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)

# Implement

See the full code on GitHub.

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

var first: Node<T>? = null,
var last: Node<T>? = null,
val randMap: HashMap<Node<T>?, Node<T>?> = hashMapOf()
) {
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
}
}

• Does this answer your question? Double LinkedList Deep Copy in Kotlin Aug 19, 2020 at 21:56
• 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. Aug 19, 2020 at 22:01
• ah, I see now. Give me a minute Aug 19, 2020 at 22:02
• 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. Aug 19, 2020 at 22:44

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)

• 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. Aug 20, 2020 at 20:14