2
\$\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.
}

Implement

fun main() {
    // Setup
    val node1 = Node(1)
    val node2 = Node(2)
    val node3 = Node(3)
    node1.next = node2
    node1.random = node3
    node2.previous = node1
    node2.next = node3
    node3.previous = node2
    node3.random = node1

    val linkedList = LinkedList()
    val deepCopy = linkedList.nextDeepCopy(node1)
    // LinkedList data changed.
    node1.data = 101
    node2.data = 202
    node3.data = 303
    val shallowCopy = linkedList.shallowCopy(node1)
    println("Deep copy made")
    linkedList.print(deepCopy)
    println()
    println("Shallow copy made")
    linkedList.print(shallowCopy)
}

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

class LinkedList {
    fun <T> nextDeepCopy(node: Node<T>?): Node<T>? {
        if (node != null) {
            return Node(
                    data = node.data,
                    previous = newDeepCopy(node.previous),
                    next = nextDeepCopy(node.next),
                    random = newDeepCopy(node.random)
            )
        } else return null
    }

    fun <T> newDeepCopy(node: Node<T>?): Node<T>? {
        if (node != null) {
            return Node(
                    data = node.data,
                    previous = node.previous,
                    next = node.next,
                    random = node.random
            )
        } else return null
    }

    fun <T> shallowCopy(node: Node<T>?) = node!!.copy()

    fun <T> print(node: Node<T>?){
        if (node != null){
            println("Node data:${node.data} previous:${node.previous?.data} next:${node.next?.data} random:${node.random?.data}")
            print(node.next)
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Your latest edit has made this question off-topic as the code does not work as intended. Please can you remove your 'answer' that was previously in the question and add it back into the question. \$\endgroup\$ – Peilonrayz Jun 27 at 18:07
  • \$\begingroup\$ I've made the suggested recommendation above re-adding the code. The question seems to be on-topic without the sample code as the question is asking the optimal implementation of a Double LinkedList deep copy in Kotlin. Therefore, it seems appropriate to include the code as an answer vs. in the question. \$\endgroup\$ – Adam Hurwitz Jun 27 at 18:11
3
\$\begingroup\$

Misplaced Responsibility: print()

The class LinkedList (or data class Node, see below) should not print() functions. Calling print() functions is a separate responsibility and should be done elsewhere in the code: What if you want your program to support different output formats like JSON or XML and they shall be sent over the network? Of course, we don't prepare software for all what-ifs. But we do make the obvious "cuts" between responsibilities. To get a printable representation, extract the text used by the print() calls into a toString() method. Then call print(node) from main().

Avoid Feature Envy (from LinkedList on Node)

Feature Envy is a special type of Misplaced Responsibility. The class LinkedList doesn't have any features of its own, and no state. Instead, it only operates on everything in the data class Node. This is a design smell that we call Feature Envy. Move all the methods from the class LinkedList to the data class Node. Then remove the class LinkedList.

You will notice that when you fix Feature Envy problems, the lines become shorter: References that have to wander around because of the Feature Envy become the omittable this.

There are situations where this type of Feature Envy is justified: In cases of specific design patterns like Proxy, Delegate, Facade.

The class LinkedList does not qualify as a Facade because it exposes the type Node<T>. It would only qualify if its type Node<T> would be hidden from the user, and the only other type the user sees were <T>.

The sitaution would, of course, change once you give class LinkedList fields head and tail.

Avoid error-prone interfaces

The current interface is error-prone. It allows for broken linked lists. The fields next and previous should be read-only for the user of Node. Instead, the user of Node should have to go through a method like insertAfter(), insertBefore(), delete(). After all, insertion and deletion are not atomic operations but should be transactions. As a next step, you could ponder about the thread-safety of these operations.

Avoid exposing implementation detail

That a LinkedList is implemented with Nodes is an implementation detail that the user doesn't need to know. The user should be able to focus on the primary purposes of LinkedLists:

  • Payload (data)
  • Iteration/Traversal
  • Insertion and Removal Your interface is too low-level.

The perfect LinkedList interface is (almost?) indistiguishable from an ArrayList interface. It should be possible to swap one implementation, like LinkedList, for another, like ArrayList, due to performance considerations (O(1) random access for ArrayList, O(n/2) random access for LinkedList vs O(1) insert/delete for LinkedList, O(n/2) insert/delete for ArrayList) without having to change all the code that uses the list.

Null-Checking

Only use Type? if you really need to support nullability. I recommend to use Type instead of Type? whereever you can. That the Kotlin compiler can enforce NonNull is one of the many strengths that it has over Java. Don't squander it by making everything nullable with ?.

BUG: fun nextDeepCopy() doesn't create a deep copy

It doesn't, because it doesn't recurse to itself but calls newDeepCopy(), and that is not recursive.

The correct way to create a deep copy of a LinkedList with additional random pointers would be to

  1. Create a map with the old nodes as key and the new node as value.
  2. Loop over the map, setting the pointers of the new nodes by a lookup in the map. Traditional ways of copying a LinkedList won't work because of the random pointer.

Also, fun newDeepCopy() does exactly the same thing as the built-in fun copy(), it creates a shallow copy of the current object.

Unit Tests?

There are ways how to prevent bugs like the one above. I recommend writing unit tests. Even better, use Test-Driven Development.

Use if-expressions

In Kotlin, if is an expression. You can make use of it.

The code:

if (condition) return a else return b

can also be written as, more idiomatic:

return if (condition) a else b

This would allow for all of your functions to become expression functions.

Piece of Sample Code

Here's a code snippet to show how your code could look like:

data class Node<T>(
        var data: T?,
        var previous: Node<T>? = null,
        var next: Node<T>? = null,
        var random: Node<T>? = null
) {
    fun shallowCopy() = copy() // You could even omit this
    fun deepCopy(): Node<T> = TODO("Implement this")
    fun toString() = "Node data:${data} previous:${previous?.data} next:${next?.data} random:${random?.data}"
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very small remark: instead of the if-expression, let or run offers an even more compact solution, node?.run { Node(data, previous, next, random) } given that you don't go for the even simpler option: node?.copy() \$\endgroup\$ – tieskedh Jun 29 at 14:11
  • \$\begingroup\$ Thank you for the thorough code review @Christian Hujer! I will post a new answer with the nextDeepCopy() bug fix, and then I will continue to refactor based on the additional notes above. \$\endgroup\$ – Adam Hurwitz Jun 29 at 20:29
  • 1
    \$\begingroup\$ @tieskedh, Good point. I've found for myself it can be easy to get carried away with too much nesting using the accessor extension functions so I try to be cognizant based on the use case. \$\endgroup\$ – Adam Hurwitz Jun 30 at 20:15
  • 1
    \$\begingroup\$ you're right. I'm less restricted in frequency, but more on the nesting-level: almost never more than one extension-scope function and I choose for the not-extension scope function unless there's a good reason. \$\endgroup\$ – tieskedh Jul 1 at 12:03

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.