5
\$\begingroup\$

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
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Does this answer your question? Double LinkedList Deep Copy in Kotlin \$\endgroup\$ Aug 19 '20 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\$ Aug 19 '20 at 22:01
  • 2
    \$\begingroup\$ ah, I see now. Give me a minute \$\endgroup\$ Aug 19 '20 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
    Aug 19 '20 at 22:44
3
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\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\$ Aug 20 '20 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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