Clone a linked list with a random pointer (part 2)

Question

This question is a follow-up question from here, where I implement the method from @vnp.

I have tested my code and it works, but the 3 steps processing seems a bit long to me. I also tried to write a few if/else, which seems a bit cluttering (e.g. code like newList.nextNode = newList.nextNode.nextNode if newList.nextNode else None). I'm wondering if there's any room to improve my code to make it even smaller and more elegant.

class LinkedListNode:
 def __init__(self, ID):
 self.ID = ID
 self.nextNode = None
 self.randomNode = None
 # return cloned new list
 def cloneList(self):
 # first step, add cloned node after each node
 node = self
 while node:
 newNode = LinkedListNode(node.ID)
 newNode.nextNode = node.nextNode
 node.nextNode = newNode
 node = node.nextNode.nextNode
 # 2nd step, setup random pointer
 node = self
 while node:
 node.nextNode.randomNode = node.randomNode.nextNode
 node = node.nextNode.nextNode
 # 3rd step, split existing and new list
 node = self
 newHead = node.nextNode
 newList = newHead
 while node:
 node.nextNode = node.nextNode.nextNode
 newList.nextNode = newList.nextNode.nextNode if newList.nextNode else None
 node = node.nextNode if node else None
 newList = newList.nextNode if newList else None
 return newHead
if __name__ == "__main__":
 node0 = LinkedListNode(0)
 node1 = LinkedListNode(1)
 node2 = LinkedListNode(2)
 node3 = LinkedListNode(3)
 node4 = LinkedListNode(4)
 node0.nextNode = node1
 node1.nextNode = node2
 node2.nextNode = node3
 node3.nextNode = node4
 node0.randomNode = node2
 node1.randomNode = node0
 node2.randomNode = node1
 node3.randomNode = node4
 node4.randomNode = node3
 newHead = node0.cloneList()
 while newHead:
 print (newHead.ID, newHead.nextNode.ID if newHead.nextNode else -1, newHead.randomNode.ID)
 newHead = newHead.nextNode

• greybeard: In the first loop: node = newNode.nextNode - in the third, just do node = node.nextNode = newList.nextNode & newList = newList.nextNode = node.nextNode if node else None (For "the test frame", wouldn't some add() come in handy?)
• Lin Ma: @greybeard, I do not quite get your point, but I think your always give valuable advice, so vote up. :) Would you mind to elaborate a bit more or write some real code. :)

Answer 1

• use documentation conventions
• avoid (close) name clashes (id)
• keep verbiage low

I failed to create an iterator for LinkedListNode that made cloneList more readable.

class LinkedListNode:
 """linked list node with an additional link to an arbitrary node in the same list"""
 def __init__(self, data, next = None, random = None):
 self.data = data
 self.next = next
 self.randomNode = random
 def cloneList(self):
 """return a clone of the list headed by self.
 randomNode of the new LinkedListNodes shall refer to the respective new nodes.
 Approach: interleave pre-existing nodes with newly created ones
 """
 # 1st step, add cloned node after each node
 node = self
 while node:
 next = node.next
 node.next = LinkedListNode(node.data, next)
 node = next
 # 2nd step, setup random pointer
 node = self
 while node:
 if node.randomNode
 node.next.randomNode = node.randomNode.next
 node = node.next.next
 # 3rd step, split original and new list
 newHead = clone = self.next
 node = self
 while node:
 node = node.next = clone.next
 clone = clone.next = node.next if node else None
 return newHead
if __name__ == "__main__":
 node4 = LinkedListNode(4)
 node3 = LinkedListNode(3, node4, node4)
 node2 = LinkedListNode(2, node3)
 node1 = LinkedListNode(1, node2)
 node0 = LinkedListNode(0, node1, node2)
 node1.randomNode = node0
 node2.randomNode = node1
 node4.randomNode = node3
 node = node0.cloneList()
 while node:
 next = node.next
 print(node.data, next.data if next else None,
 node.randomNode.data if node.randomNode else None)
 node = next

• greybeard: I'm not a python coder: this is more of a jump start, the code will implement the ideas poorly. Feel free to edit, suggest conversion to a "community wiki post", scorch...
• Lin Ma: I thought your code is pretty good, greybeard. I will see if janos has better ideas than yours. :))
• Lin Ma: BTW, greybeard, dump question for statement newHead = clone = self.next, underlying it will execute as (1) clone = self.next then newHead = self.next, or (2) clone = self.next, then newHead = clone?
• greybeard: It is not (2). The way I read assignemt statement, there is neither order nor synchrony implied - for a = b = x, b = x then a = x is as good as (2) or "it happens at exactly the same time" (or implies no action at all: storage location renaming). (Think of a, b = b, a) (This is in contrast to languages like those from the C family where assignment operators are part of regular expressions, binding right to left: (2) is right. The fun begins when coercions/casts rear their ugly head.)
• greybeard: Oh, sorry, my previous comment is inaccurate. For a = b = x, b = x then a = x is as good as a = x then b = x ((1)) or "it happens at exactly the same time"...

Answer 2

Cloning

I would expect from a cloning process to not modify the original instance, even if the modifications are transient and the original state is restored. Your implementation adds nodes in the original list during the process. After the clone is ready, you clean up and restore the original list, but this approach is surprising, and a mistake could destroy the integrity of the original list.

I suggest to stick with more conventional approaches that produce a clone without modifying the original instance, for example by using an intermediary map to store the mapping of old nodes to new nodes, so that the random links can be correctly recreated.

Usability

How would you use this linked list in a program? I see several usability issues:

• The concept of a list and a node are not separated. This is confusing.
• Common methods of a list are missing. How to add a node? The implementation doesn't offer an easy way to do that, users have to do that manually. They can only do that if they know the implementation, especially the linking between the nodes.

In other words, there's a total lack of encapsulation, leading to serious usability consequences.

Conventions

Some Python conventions (PEP8) are violated, for example:

• Function and variable names should use snake_case
• There should be a blank line between functions of a class

There are others too. I suggest to go over PEP8 and follow the recommendations.

• Lin Ma: Thanks janos, appreciate for your advice. For the "more conventional approaches", is there a conventional solution which has O(n) time complexity and O(1) space time complexity for additional temporary storage?
• janos: Not that I know of.