• 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.


  • 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?


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

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
            temp.next = newNode
        return newNode

    fun deepCopyWithoutRandoms(prev: Node<T>?, node: Node<T>?): Node<T>? {
        return if (node == 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!!)
            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
  • \$\begingroup\$ Does this answer your question? Double LinkedList Deep Copy in Kotlin \$\endgroup\$ Commented Aug 19, 2020 at 21:56
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 19, 2020 at 22:01
  • 2
    \$\begingroup\$ ah, I see now. Give me a minute \$\endgroup\$ Commented Aug 19, 2020 at 22:02
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – pacmaninbw
    Commented Aug 19, 2020 at 22:44

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

  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 20, 2020 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.