Copy a list with random pointers in Python

Why it matters

Copying a list sounds simple until a node can point at any other node. Editors keep a document as a chain of blocks, and some blocks refer back to earlier blocks. Undo systems and graph-like structures do the same thing. A copy of such a structure must be a new structure. If the copy reuses the old nodes, changing the copy changes the original, and that bug is hard to find.

This lesson builds a full copy, called a deep copy, of a list where each node has a next reference and a random reference. It shows two methods. The first uses a dict and is easy to check. The second uses no dict and uses O(1) extra space, which means the extra memory does not grow with the list. The copy itself is still a new list of the same size, so the total memory used is still O(n).

Python has a standard function, copy.deepcopy, that can copy a structure like this. It is used at the end of the lesson as a check. The point of the lesson is to see how the copy is built.

The lesson stays on this one task. The recursion lesson in this module explains why a recursive copy can run past Python's recursion limit on long lists, and that is a separate problem.

Words you will need

• Node: one object in a linked list. In this lesson a node has a value, a next reference and a random reference.
• Reference: a name that points at an object. In Python every variable is a reference. Two names can point at the same object.
• Random pointer: a second reference in each node. It can point at any node in the list, an earlier one, a later one, the node itself, or nothing. The word "random" describes the layout, not a random choice made by the program.
• None: the Python value that means "points at nothing". It is the same idea as null in other languages.
• Deep copy: a copy in which every node is a new object. Nothing in the copy points at a node of the original.
• Shallow copy: a copy that reuses the original nodes. Changing a value in the copy then changes the original too.
• Identity: whether two names point at the same object. The operator is checks identity. The operator == checks equality, and for a class that does not define its own equality rule, == falls back to identity. So two different Node objects with the same value are ==-unequal here.
• Dict: Python's built-in hash map. It stores pairs of a key and a value. Looking up a key takes about the same time no matter how many pairs are stored. A key must be hashable, which means Python can compute a number for it called a hash. A plain Node object is hashable, and its hash is based on its identity.
• Interleave: to place items in alternating order, such as A B C becoming A A' B B' C C', where the apostrophe marks a copy.
• Extra space: memory used by the method beyond the input and the output. The output here is the copy, so it does not count.

The problem in plain words

Imagine a group of people in a queue. Each person has a next person in the queue. Each person also has one buddy. The buddy can be anyone in the queue, someone who came before, someone who comes later, the person themselves, or nobody. Your task is to make a second queue of new people. Each new person must have the same name as the original. Each new person's next and buddy must be the new people, not the originals.

Here is a five-node example. The notation used throughout the lesson is value[random value]. The number in brackets is the value of the node that the random pointer points at, or null when it points at nothing.

7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]

Node 7 has no random pointer. Node 13 points at node 7. Node 11 points at node 1, which comes later in the list. Node 10 points at node 11. Node 1 points at node 7, which is the first node.

The obvious plan is to walk the list once and copy each node as you go. The copy of 7 is made first. Then the copy of 13, and so on. The problem shows up at node 11. Its random pointer points at node 1, but node 1 has not been copied yet. There is no copy to point at. The walk has to either wait, or make a second pass once every copy exists. Both methods below do one of these things.

A test list in Python

The code needs a way to build a list with random pointers and print it. The function build takes the values and, for each node, the index of the node its random pointer should reach. The value -1 means the random pointer is None.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None
 
 
def build(vals, random_index):
    nodes = [Node(v) for v in vals]
    for i in range(len(vals)):
        if i + 1 < len(vals):
            nodes[i].next = nodes[i + 1]
        if random_index[i] >= 0:
            nodes[i].random = nodes[random_index[i]]
    return nodes[0] if vals else None

class Node defines a new type. __init__ runs when a node is created, and self is the node being set up. Python does not need a separate declaration for each field. The fields next and random are created inside __init__, and they start as None.

[Node(v) for v in vals] is a list comprehension. It runs Node(v) once for each value and collects the results in a list. The last line uses a conditional expression, nodes[0] if vals else None. It means "the first node if the list of values is not empty, otherwise None".

The function show prints values and random values, not identities, so two lists with the same text can still be different objects. The deep-copy check below looks at identity separately.

def show(head):
    parts = []
    cur = head
    while cur is not None:
        r = "null" if cur.random is None else str(cur.random.val)
        parts.append(f"{cur.val}[{r}]")
        cur = cur.next
    return " -> ".join(parts) if parts else "(empty)"

The f"..." text is an f-string. Anything inside braces is replaced by its value. f"{cur.val}[{r}]" gives 7[null] when cur.val is 7 and r is "null".

The build call for the five-node example is:

original = build([7, 13, 11, 10, 1], [-1, 0, 4, 2, 0])

The random indexes are -1, 0, 4, 2, 0. Node 0 (value 7) has none. Node 1 (value 13) points at index 0 (value 7). Node 2 (value 11) points at index 4 (value 1). Node 3 (value 10) points at index 2 (value 11). Node 4 (value 1) points at index 0 (value 7).

The three comparisons below show how identity and equality work for Node.

a = Node(7)
b = Node(7)
print(a == b, a is b, a is a)

False False True

The two nodes hold the same value, but they are two objects. a == b is False, because a class with no equality rule compares by identity. a is a is True, because it is the same object. In the code below, is is used for identity checks, and that is the convention most Python code follows.

Method 1: a dict from original to copy

The dict method has two passes.

In pass 1, create one copy for each original node and store the pair original -> copy in a dict. At the end of this pass, every copy exists. Nothing is linked yet.

In pass 2, walk the original list again. For each original node, find its copy in the dict. Set the copy's next to the copy of the original's next, and set the copy's random to the copy of the original's random. Because every copy already exists, each lookup succeeds.

def copy_with_map(head):
    copies = {}
    cur = head
    while cur is not None:
        copies[cur] = Node(cur.val)
        cur = cur.next
 
    def mapped(original):
        return None if original is None else copies[original]
 
    cur = head
    while cur is not None:
        copy = copies[cur]
        copy.next = mapped(cur.next)
        copy.random = mapped(cur.random)
        cur = cur.next
    return mapped(head)

copies = {} creates an empty dict. copies[cur] = Node(cur.val) stores the new node under the old node as its key. The key is the original node object, so the lookup copies[cur] finds exactly one entry, the one made for that same node. Two nodes with the same value remain separate keys, because each Node hashes by identity.

mapped is a function defined inside copy_with_map. It can read the variable copies from the function around it, and that is why it does not need copies as a parameter. It handles None. A None pointer in the original must stay None in the copy, and copies[None] would raise a KeyError, so the check comes first.

Running this method on the five-node example gives:

map copy:             7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]

The output looks like the original, which is the goal. Looking the same is not enough, though. A shallow copy would also look the same. To check that the copy is deep, the program walks both lists and collects every original node into a set. Then it checks that no copy node, and no copy's random target, is in that set. A set holds each object once, and in on a set checks identity for objects like these, because Node does not define its own equality or hash.

def is_deep_copy(original, copy):
    originals = set()
    cur = original
    while cur is not None:
        originals.add(cur)
        cur = cur.next
    cur = copy
    while cur is not None:
        if cur in originals:
            return False
        if cur.random is not None and cur.random in originals:
            return False
        cur = cur.next
    return True

For the dict copy, the check prints:

map copy is deep:     True

The cost of this method is one pass to create the copies, one pass to link them, and one dict entry for each node. Time is O(n). Extra space is O(n), because the dict holds n entries.

Method 2: weave the copies in, then split them out

The dict costs O(n) extra space. The second method removes the dict by placing each copy right next to its original.

Take the three-node example A -> B -> C, where A's random points at C, B's random is None, and C's random points at A. Here are the stages.

Why does step 2 work without a dict? Look at A's random pointer. It points at C. The copy of C is the node right after C, which is C'. So A'.random should be C', and that is C.next. The copy of any node is always the node right after it. So the copy of original.random is original.random.next. No lookup is needed.

Here is the method in full.

def copy_interleaved(head):
    # Step 1: A -> B -> C becomes A -> A' -> B -> B' -> C -> C'.
    cur = head
    while cur is not None:
        nxt = cur.next
        copy = Node(cur.val)
        cur.next = copy
        copy.next = nxt
        cur = nxt
 
    # Step 2: a copy's random is the node after its original's random.
    cur = head
    while cur is not None:
        if cur.random is not None:
            cur.next.random = cur.random.next
        cur = cur.next.next
 
    # Step 3: take the copies out and put the original links back.
    copy_head = None if head is None else head.next
    cur = head
    while cur is not None:
        copy = cur.next
        next_original = copy.next
        cur.next = next_original
        copy.next = None if next_original is None else next_original.next
        cur = next_original
    return copy_head

Step 1 walks the original list. Before it changes cur.next, it saves the old next in nxt. It then creates the copy, puts the copy between cur and nxt, and moves on to nxt.

Step 2 walks the woven list, but moves two places at a time. cur is always an original, and cur.next is its copy. The line cur = cur.next.next skips the copy and lands on the next original. When cur is the last original, cur.next is its copy and cur.next.next is None, so the loop ends.

Step 3 is the part that is easy to get wrong. It reads the copy and the next original before it changes anything. It sets cur.next back to the next original, which restores the original list. It sets copy.next to the copy of that next original, which is the node after it, next_original.next. The last copy gets None, because its original was the last node.

Step 3 must save copy.next in next_original before it overwrites copy.next. The value in copy.next is the next original, and the walk needs it to move on. Once copy.next holds the next copy, that value is gone, so the code saves it first.

Running the method on the five-node example gives:

interleaved copy:     7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]
interleaved is deep:  True
original after both:  7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]

The third line shows that the original list is restored after the method runs. A caller who still holds the original head can use it safely.

The method uses no dict and no new list. Its only extra variables are a few names that point at nodes. Extra space is O(1), and time is O(n) because each step makes at most three passes over the list.

Harder examples: self pointers and empty lists

The first example has random pointers that go backwards, forwards and to None. Two cases are worth checking by hand.

A list with one node whose random pointer points at itself is the hardest small case. Step 1 makes A -> A'. Step 2 sets A'.random = A.random.next. Here A.random is A, and A.next is A', so A'.random becomes A'. The copy points at itself, which is correct.

single self-pointer:  5[5]

An empty list has no nodes, so both methods must return None. The code checks head is None before it reads head.next, and the dict method's loops do not run.

empty list copy:      (empty) / (empty)

The third example is a random test. The program makes 2,000 lists with 0 to 10 nodes. Each list gets random values from 0 to 19 and random pointers that may be None or may point at any node, including itself. The seed is fixed with random.seed(12), so the same lists are made on every run. For each list, both methods run. The program checks that each copy shows the expected text, that each copy is deep, and that the interleaving method leaves the original list unchanged.

random checks: 2000 cases, 0 mismatches

A random test does not prove that a method is correct. It finds the kinds of mistakes that a few hand examples miss, such as a list where every random pointer is None, or a list where the last node points at itself.

The full program

This program has everything from the lesson in one file. It runs without input, and it prints the outputs shown above.

The output of this program, on Python 3.14, is:

original:             7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]
map copy:             7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]
map copy is deep:     True
interleaved copy:     7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]
interleaved is deep:  True
original after both:  7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]
three-node map:       A[C] -> B[null] -> C[A]
single self-pointer:  5[5]
empty list copy:      (empty) / (empty)
random checks: 2000 cases, 0 mismatches

The extra space after each label comes from print with several arguments. Python puts a space between them.

The standard library gives the same deep copy with one call:

import copy
 
original = build([7, 13, 11, 10, 1], [-1, 0, 4, 2, 0])
d = copy.deepcopy(original)
print(show(d), is_deep_copy(original, d))

7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7] True

copy.deepcopy keeps a memo of the objects it has already copied, so a cycle of references does not make it loop forever. It is the right tool in a real program. Writing the method by hand shows what the copy has to do.

Common mistakes

Mistake 1: copying random in the same pass as the node. The one-pass version creates each copy and immediately looks up the copy of its random pointer. A random pointer that points forward finds nothing, because the target has not been created yet. The dict's get method returns None in that case, so the error is silent. The program does not stop. It produces the wrong result.

def one_pass(head):
    copies = {}
    prev = None
    head_copy = None
    cur = head
    while cur is not None:
        copy = Node(cur.val)
        copies[cur] = copy
        copy.random = copies.get(cur.random)
        if prev is None:
            head_copy = copy
        else:
            prev.next = copy
        prev = copy
        cur = cur.next
    return head_copy

Running this mistake on the five-node example gives:

7[null] -> 13[7] -> 11[null] -> 10[11] -> 1[7]

Node 11 lost its random pointer, because node 1 had no copy when node 11 was processed. The fix is the second pass in Method 1, or the interleaving in Method 2. Either way, every copy must exist before any random pointer is set.

Mistake 2: following random without a None check. In step 2 of the interleaving method, cur.random can be None. Reading cur.random.next then fails. Python does not have a NullPointerException. It raises AttributeError instead. Here is step 2 without the check. It assumes step 1 has already run, and on the two-node list 1[null] -> 2[null] it fails:

def step2_without_check(head):
    cur = head
    while cur is not None:
        cur.next.random = cur.random.next
        cur = cur.next.next

AttributeError: 'NoneType' object has no attribute 'next'

The message says that the object on the left of .next is None. The name 'NoneType' is Python's name for the type of None. The traceback above the message shows the line that failed, with a caret under the part that was None. The line number depends on where you saved the file. The fix is the check if cur.random is not None: that the method above has.

Mistake 3: skipping step 3. If the code stops after step 2, the copies stay woven into the original list. The copy is still correct, but the original list now has six nodes, and each value appears twice when the original is walked. Anyone who holds the original head sees the copies too. Step 3 exists to undo the weaving.

Mistake 4: copying the random pointer as it is. A common slip is copy.random = cur.random. This makes the copy point into the original list, so the copy is shallow. The random pointer looks right when printed, because the values match. is_deep_copy catches it, because the copy's random target is one of the original nodes. Changing the copy's random target in that case would change the original list.

def shallow_random(head):
    copies = {}
    cur = head
    while cur is not None:
        copies[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur is not None:
        copy = copies[cur]
        copy.next = copies.get(cur.next)
        copy.random = cur.random
        cur = cur.next
    return copies.get(head)

7[null] -> 13[7] -> 11[1] -> 10[11] -> 1[7]

is_deep_copy on that copy returns False.

Mistake 5: a key class that defines __eq__. The dict method works because Node uses identity for equality and for hashing. Suppose a later change added an __eq__ method that compares values. Python then sets the class's hash to None unless the class also defines __hash__, and a dict refuses the key:

class KeyWithEq:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None
 
    def __eq__(self, other):
        return isinstance(other, KeyWithEq) and self.val == other.val
 
 
{KeyWithEq(7): "copy"}

TypeError: cannot use 'KeyWithEq' as a dict key (unhashable type: 'KeyWithEq')

If the class also defines __hash__ based on the value, the dict accepts it, and a wrong copy can be returned. Two different nodes that hold 7 then count as the same key:

class KeyWithEqHash:
    def __init__(self, val):
        self.val = val
 
    def __eq__(self, other):
        return isinstance(other, KeyWithEqHash) and self.val == other.val
 
    def __hash__(self):
        return hash(self.val)
 
 
a = KeyWithEqHash(7)
b = KeyWithEqHash(7)
d = {a: "copy of a"}
print("lookup of b gives", repr(d.get(b)))
print("same object:", a is b, "equal by value:", a == b)

lookup of b gives 'copy of a'
same object: False equal by value: True

The two nodes are different objects, but the dict returns the copy made for a when asked for b. If the nodes must be dict keys, keep the default identity behavior, or do not give the class an __eq__ at all.

Practice

Exercise 1. Take three nodes, A with random pointing at C, B with random None, and C with random pointing at A. Write the list after step 1 of the interleaving method. Then write each copy's random pointer after step 2.

Show the answer

After step 1 the list is A -> A' -> B -> B' -> C -> C'. In step 2, A'.random is A.random.next, which is C.next, so it is C'. B'.random is None, because B.random is None. C'.random is C.random.next, which is A.next, so it is A'. The result is A'.random = C', B'.random = None, C'.random = A'.

Exercise 2. Why can a single pass that copies next and random together fail when a random pointer points forward?

Show the answer

When the walk reaches a node whose random pointer points forward, the target node has not been copied yet. The lookup finds no copy, so the random pointer is set to None or to a wrong value. Both methods avoid this by creating every copy before any random pointer is set, either in a separate pass (the dict) or by placing each copy next to its original (the interleaving).

Exercise 3. How many new Node objects does copy_with_map create for a list of five nodes? How many entries does the dict hold at the end of pass 1?

Show the answer

It creates five new nodes, one for each original, and the dict holds five entries, one mapping each original to its copy. The original five nodes are not counted as new.

Exercise 4. Suppose step 3 of copy_interleaved is removed. For the three-node example, how many nodes does the original head reach when walked with next, and what do they hold?

Show the answer

The walk from the original head visits six nodes: A, A', B, B', C, C'. The original values appear twice, and the copies are visible from the original head. The copies are still correct, but the original list has been changed.

Exercise 5. What does copy_interleaved return for a list with one node, value 9, whose random pointer is None?

Show the answer

Step 1 makes 9 -> 9'. Step 2 skips the node, because its random pointer is None. Step 3 restores 9 and gives 9' a None next. The method returns the copy, and its output is 9[null].

Summary

• A deep copy makes a new node for every original node, and no copy points into the original list.
• The dict method makes all copies in one pass, then links them in a second pass, using O(n) extra space.
• The interleaving method places each copy right after its original, so the copy of original.random is original.random.next. It uses O(1) extra space.
• Step 3 of the interleaving method must restore the original links, or the original list is left changed.
• Both methods need a None check on every random pointer, and both need every copy to exist before any random pointer is set.