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

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

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.