5 Best Ways to Copy List with Random Pointer in Python

Rate this post

πŸ’‘ Problem Formulation: In Python, a list with a random pointer refers to a data structure where each element is a node that, besides its value, contains a pointer to any other random node in the list or NULL. Cloning such a structure requires creating a deep copy of the list, such that modifying one list does not affect the other. This article aims to demonstrate five methods to effectively copy a list with a random pointer in Python, preserving the original complex references.

Method 1: Using a Dictionary to Maintain Node References

This method involves creating a hash table (dictionary in Python) to keep track of the nodes already copied. It creates a new node for each original node and uses the dictionary to manage the next and random pointers, ensuring the copied list maintains the original structure.

Here’s an example:

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None

    old_to_new = {}
    current = head
    while current:
        old_to_new[current] = Node(current.val)
        current = current.next
    current = head
    while current:
        old_to_new[current].next = old_to_new.get(current.next)
        old_to_new[current].random = old_to_new.get(current.random)
        current = current.next
    return old_to_new[head]

# Example usage
original = Node(1)
original.next = Node(2)
original.random = original.next
copied_list = copyRandomList(original)

Output:

A deep cloned list, where copied_list is a separate list with identical value and random pointers as 'original'.

This code snippet creates a custom Node class and a function copyRandomList to clone a linked list with random pointers. The dictionary old_to_new helps in mapping original nodes to their corresponding cloned nodes, ensuring a deep copy with all references intact.

Method 2: Iterative Link-Weaving Approach

The iterative link-weaving method creates cloned nodes and intersperses them between the original nodes. Then, updates the random pointers appropriately, followed by separation of the two lists. This method does not use any extra space for the hash table like Method 1.

Here’s an example:

def copyRandomList(head):
    if not head:
        return None

    # Step 1: Create new nodes
    current = head
    while current:
        new_node = Node(current.val)
        new_node.next = current.next
        current.next = new_node
        current = new_node.next

    # Step 2: Set random pointers for the new nodes
    current = head
    while current:
        current.next.random = current.random.next if current.random else None
        current = current.next.next

    # Step 3: Separate the lists
    original = head
    copy = head.next
    while original:
        next_node = original.next
        original.next = next_node.next
        original = original.next
        if next_node.next:
            next_node.next = next_node.next.next

    return copy

# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)

Output:

A deep cloned list, where copied_list is a separated and cloned list that mirrors the 'original' including random pointers without using extra space.

The code demonstrates an efficient space approach by integrating the cloning process within the original linked list. The new nodes are woven into the existing list, random pointers are adjusted, and then the list is untangled into two separate lists at the end.

Method 3: Recursive Deep Copy

This method uses recursion to deep copy each node. It creates a clone of the next and random node recursively and then fulfills the random and the next pointers step by step.

Here’s an example:

def copyRandomList(head, copies={}):
    if not head:
        return None
    if head in copies:
        return copies[head]

    node_copy = Node(head.val)
    copies[head] = node_copy
    node_copy.next = copyRandomList(head.next, copies)
    node_copy.random = copyRandomList(head.random, copies)

    return node_copy

# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)

Output:

Recursively created deep cloned list, where 'copied_list' is an independent copy of the 'original'.

This code snippet employs recursion to elegantly clone each node, carrying a dictionary copies that acts similar to a cache, preventing circular recursion and redundant copies of nodes.

Method 4: Serialization and Deserialization

This approach leverages the concept of serialization to convert the list into a format that can be easily copied and then deserialized back to a new list structure. It’s often less efficient but is an interesting alternative that demonstrates Python’s versatility.

Here’s an example:

import pickle

def copyRandomList(head):
    return pickle.loads(pickle.dumps(head))

# Example usage
# Assuming original list has been created as in Method 1
copied_list = copyRandomList(original)

Output:

The deserialized deep cloned list that reflects the structure and pointers of the 'original'.

The code uses Python’s pickle module for serialization, which will handle the deep copy process, including managing complex pointer structures transparently, albeit at a possible performance cost.

Bonus One-Liner Method 5: Using deepcopy()

The deepcopy() function from the copy module can be used to create a deep copy of the list in a single line. It is the simplest method but underneath, it is similar to the serialization method.

Here’s an example:

from copy import deepcopy

# Example usage
# Assuming original list has been created as in Method 1
copied_list = deepcopy(original)

Output:

A one-liner code to produce a deep cloned list that maintains the original list's random pointer structure.

This code snippet showcases the simplicity of Python where a single function call to deepcopy() takes care of all the complexities involved in cloning a data structure with random pointers.

Summary/Discussion

  • Method 1: Dictionary Reference Mapping. Efficient and clear. Requires O(n) additional space.
  • Method 2: Iterative Link-Weaving. Space-efficient with O(1) extra space. More complex implementation.
  • Method 3: Recursive Deep Copy. Elegant and clean. Potentially high stack usage with deep recursion.
  • Method 4: Serialization/Deserialization. Versatile and powerful. Potentially slow and not memory efficient.
  • Bonus Method 5: Using deepcopy(). Extremely simple. Underneath, it might be slower like serialization.