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


# 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

node1.data = 101
node2.data = 202
node3.data = 303
println()
}

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

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

• 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. Jun 27, 2020 at 18:07
• 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. Jun 27, 2020 at 18:11

# 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:

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

• 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() Jun 29, 2020 at 14:11
• 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. Jun 29, 2020 at 20:29
• @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. Jun 30, 2020 at 20:15
• 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. Jul 1, 2020 at 12:03