Copy a list with random pointers

Why this matters

Copying an object sounds simple until the object points at other objects. Suppose a list node has a next pointer, which is the normal link to the following node, and also a random pointer that can point at any node in the list, or at nothing. Copying the values is easy. Copying the pointers is the hard part. If the copy's random pointer still points at the original node, the copy is not independent. Changing the original changes the copy, and freeing the original leaves the copy with a dangling pointer.

A copy that owns its own nodes and points only at its own nodes is called a deep copy. A copy that copies the pointer values and nothing else is a shallow copy. The shallow copy is the usual bug in this problem. The rest of this lesson builds a deep copy in two ways.

The first way uses a hash map. A hash map is a table that finds a value from a key quickly, usually in about one step. The map records which new node belongs to each old node. The second way uses no map. It weaves each new node into the old list, uses the weave to find the random targets, and then pulls the two lists apart again. This second way uses constant extra space, which means the extra memory does not grow with the length of the list.

The problem is a common interview question because both ideas appear in other tasks. The map idea is the usual first answer. The weave idea is the answer that shows you understand pointers.

The problem in plain words

Each node has three parts: a value, a next pointer to the following node, and a random pointer to some node. The random pointer can be null. It can point forward, point backward, point at the node itself, or point at a node with the same value as another node. The only rule is that a random pointer points at a node in the same list.

Here is a list of five nodes. The numbers 0 to 4 are positions in the list, which we use as labels in the tables and output below.

The copy must have five new nodes with the same values, in the same order. Its next pointers must lead through the new nodes. Its random pointers must lead to the new node that matches the old target. For example, the copy of position 1 must have a random pointer to the copy of position 0, not to the original position 0.

The node and the list

The lesson keeps the code short by letting a List class own every node. A List stores its nodes in a std::vector of std::unique_ptr. Each node is created with make_unique, and the vector frees all of them when the list is destroyed. The next and random fields are plain pointers. They do not own anything. This matches the problem: the links describe the shape, and the list owns the memory.

#include <cstddef>
#include <iostream>
#include <memory>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
struct Node {
    int value;
    Node* next = nullptr;
    Node* random = nullptr;
    explicit Node(int v) : value(v) {}
};
 
class List {
public:
    Node* head = nullptr;
 
    Node* add(int value) {
        storage_.push_back(std::make_unique<Node>(value));
        return storage_.back().get();
    }
 
    static List build(const std::vector<int>& values, const std::vector<int>& random_index) {
        List list;
        std::vector<Node*> nodes;
        for (int v : values) {
            nodes.push_back(list.add(v));
        }
        for (std::size_t i = 0; i < nodes.size(); ++i) {
            nodes[i]->next = (i + 1 < nodes.size()) ? nodes[i + 1] : nullptr;
            nodes[i]->random = random_index[i] >= 0 ? nodes[random_index[i]] : nullptr;
        }
        list.head = nodes.empty() ? nullptr : nodes.front();
        return list;
    }
 
private:
    std::vector<std::unique_ptr<Node>> storage_;
};

The build function takes two lists of the same length. The first gives the values. The second gives, for each node, the position of its random target, or -1 for null. For the table above, the values are 7, 13, 11, 10, 1 and the random positions are -1, 0, 4, 2, 0.

A List cannot be copied, because unique_ptr cannot be copied. It can be moved, and the functions below return a List by value, which the compiler moves for you. The heap nodes do not move when the List moves, so the raw pointers stay valid.

Two helpers print a list in a form that makes random targets easy to read. They are used in every example and in the checks.

// Position of target inside the list, -1 for null, -2 if it is not in this list.
long index_of(const Node* head, const Node* target) {
    long i = 0;
    for (const Node* p = head; p != nullptr; p = p->next, ++i) {
        if (p == target) {
            return i;
        }
    }
    return target == nullptr ? -1 : -2;
}
 
void describe(const char* label, const Node* head) {
    std::cout << label << ":";
    for (const Node* p = head; p != nullptr; p = p->next) {
        std::cout << " [" << p->value << " random=" << index_of(head, p->random) << "]";
    }
    std::cout << '\n';
}

The value -2 is a warning sign. It means a random pointer leads to a node that is not in the list being printed. You will see it in the mistakes section.

Approach 1: a hash map from old node to new node

The map approach works in two passes over the original list.

In the first pass, make one new node for each old node, copy its value, and store the pair in the map. The key is the address of the old node and the value is the address of the new node. After this pass, every old node has its copy waiting in the map, but the copies are not linked yet.

In the second pass, walk the old list again. For each old node, find its copy in the map and set the copy's next and random pointers. The next pointer of the copy is the copy of the old next node. The random pointer of the copy is the copy of the old random node. The map gives both answers in one lookup each. A null pointer maps to null.

List copy_with_map(const List& source) {
    List copy;
    std::unordered_map<const Node*, Node*> copy_of;
    for (const Node* old = source.head; old != nullptr; old = old->next) {
        copy_of[old] = copy.add(old->value);
    }
    auto mapped = [&copy_of](const Node* p) -> Node* {
        return p == nullptr ? nullptr : copy_of.at(p);
    };
    for (const Node* old = source.head; old != nullptr; old = old->next) {
        Node* made = copy_of.at(old);
        made->next = mapped(old->next);
        made->random = mapped(old->random);
    }
    copy.head = mapped(source.head);
    return copy;
}

The mapped lambda hides the null check. Without it, the code would look up a null key, which is an error. The at function is used on purpose: it throws an exception if the key is missing, so a bad random pointer stops the program rather than silently producing a bad copy. The mistakes section shows that message.

Why two passes and not one? When the code sets the random pointer for node 0, the target might be node 3. The copy of node 3 must already exist, or the code has nothing to point at. The first pass creates every copy, so the second pass can always find its targets. If you tried to do both in one pass, you would need to create a copy the first time it is needed, and that is more code, not less.

Here is the map approach on the five-node list.

List example = List::build({7, 13, 11, 10, 1}, {-1, 0, 4, 2, 0});
describe("original", example.head);
List by_map = copy_with_map(example);
describe("map copy", by_map.head);

Expected output:

original: [7 random=-1] [13 random=0] [11 random=4] [10 random=2] [1 random=0]
map copy: [7 random=-1] [13 random=0] [11 random=4] [10 random=2] [1 random=0]

The two lines match. The random positions are the same, even though every node in the copy is new. The map approach uses extra memory: the map holds one entry for each node, so its size grows with the list. The time is also one pass for the copies and one pass for the links, which is proportional to the length of the list. Each map lookup takes about one step on average.

Approach 2: weave the copies in

The second approach gets rid of the map by putting each copy right next to its original. Imagine the list A, B, C. The weave turns it into A, A', B, B', C, C', where each primed node is the copy of the node before it. Now every original node knows where its copy is, because the copy is always the node after it. That is the trick. The copy of any node is simply old->next.

The method has three steps. Each step is one walk over the list.

Step 1 inserts a copy after each original node. For node A, the copy A' gets next pointing to the old next node B, and A gets next pointing to A'. Then the walk jumps two nodes ahead, so it does not visit the copy it just made.

Step 2 sets the random pointers. For each original node A, its random target is some original node B. The copy of B is the node right after B, which is B->next. So the copy A' gets random set to A->random->next. If A has no random pointer, A' gets null.

Step 3 pulls the two lists apart. The original list gets its old next links back. The copy list is built from the copies. Each copy is linked to the copy of the next original node, which is two nodes ahead in the woven list.

List copy_interleaved(List& source) {
    List copy;
    // Step 1: A B C becomes A A' B B' C C'.
    for (Node* old = source.head; old != nullptr; old = old->next->next) {
        Node* made = copy.add(old->value);
        made->next = old->next;
        old->next = made;
    }
    // Step 2: each copy's random is the copy that sits after the original's random.
    for (Node* old = source.head; old != nullptr; old = old->next->next) {
        Node* made = old->next;
        made->random = old->random ? old->random->next : nullptr;
    }
    // Step 3: pull the two chains apart and put the original links back.
    copy.head = source.head ? source.head->next : nullptr;
    for (Node* old = source.head; old != nullptr; old = old->next) {
        Node* made = old->next;
        old->next = made->next;
        made->next = old->next ? old->next->next : nullptr;
    }
    return copy;
}

The loop in step 1 uses old->next->next as its step. After the body runs, old->next is the copy just made, and old->next->next is the next original node. The loop never reaches a null pointer in the middle of a step, because the copy is always there when the step is taken.

Step 3 is the subtle part. After the loop in step 1, the copy of A sits between A and B. In step 3, old->next = made->next; moves A's next back to B, which restores the original list. Then made->next = old->next->next; sets A' to point at B', which is the copy of B. The loop then moves to old = old->next, which is B, the next original node, and repeats. The last node has no next node after it, so its copy gets a null next pointer.

Trace the method on a three-node list with the values 1, 2, 3 and random targets 3, none, 1. After step 1, the list reads 1, 1', 2, 2', 3, 3'. In step 2, node 1 has random target 3, and the node after 3 is 3', so 1' gets random 3'. Node 2 has no random target, so 2' gets null. Node 3 has random target 1, and the node after 1 is 1', so 3' gets random 1'. Step 3 then splits the chains back into 1, 2, 3 and 1', 2', 3'.

List three = List::build({1, 2, 3}, {2, -1, 0});
List woven = copy_interleaved(three);
describe("woven copy", woven.head);

Expected output:

woven copy: [1 random=2] [2 random=-1] [3 random=0]

The copy has the same random positions as the original. Random targets are found without a map, using only the links the weave creates.

The extra memory used by this method is a few pointers, which does not grow with the length of the list. The copies themselves are the output, so they are not counted as extra. The price is that the method changes the source list while it runs. The source is restored at the end, but during the run its next pointers point at copies. A program that reads the source in another thread, or that stops in the middle, sees the woven list.

Example 1: the five-node list, both ways

The main function below runs both methods on the five-node list and checks each result. The check_copy function compares the copy with the original and returns a short message. It is shown in full in How the check works, and it is needed to read the output.

int main() {
    List example = List::build({7, 13, 11, 10, 1}, {-1, 0, 4, 2, 0});
    describe("original", example.head);
    std::cout << "forward randoms: " << count_forward_randoms(example.head) << '\n';
 
    List by_map = copy_with_map(example);
    describe("map copy", by_map.head);
    std::cout << "check: " << check_copy(example.head, by_map.head) << '\n';
 
    List by_interleave = copy_interleaved(example);
    describe("interleave copy", by_interleave.head);
    std::cout << "check: " << check_copy(example.head, by_interleave.head) << '\n';
    std::cout << "source nodes after interleave copy: " << count_nodes(example.head) << '\n';
 
    List naive = copy_naive(example);
    std::cout << "naive check: " << check_copy(example.head, naive.head) << '\n';
 
    List empty = List::build({}, {});
    List single = List::build({5}, {0});
    std::cout << "empty map: " << check_copy(empty.head, copy_with_map(empty).head) << '\n';
    List single_copy = copy_interleaved(single);
    std::cout << "single interleave: " << check_copy(single.head, single_copy.head) << '\n';
    return 0;
}

The helpers count_forward_randoms and count_nodes, and the function copy_naive, are defined in the sections below.

Expected output:

original: [7 random=-1] [13 random=0] [11 random=4] [10 random=2] [1 random=0]
forward randoms: 1
map copy: [7 random=-1] [13 random=0] [11 random=4] [10 random=2] [1 random=0]
check: ok
interleave copy: [7 random=-1] [13 random=0] [11 random=4] [10 random=2] [1 random=0]
check: ok
source nodes after interleave copy: 5
naive check: random pointer differs
empty map: ok
single interleave: ok

Both real methods pass the check. The source still has five nodes after the interleave method, which shows the links were put back. The line naive check is the mistake from the next section, and the check catches it.

The helper count_forward_randoms counts the nodes whose random target comes later in the list. For the example, only the node at position 2 (value 11) points forward, to position 4. So the count is 1.

std::size_t count_forward_randoms(const Node* head) {
    std::size_t count = 0;
    long own = 0;
    for (const Node* p = head; p != nullptr; p = p->next, ++own) {
        long target = index_of(head, p->random);
        if (target > own) {
            ++count;
        }
    }
    return count;
}
 
std::size_t count_nodes(const Node* head) {
    std::size_t n = 0;
    for (const Node* p = head; p != nullptr; p = p->next) {
        ++n;
    }
    return n;
}

Example 2: a node that points at itself

Special cases are where copy code breaks. A single node whose random pointer points at itself is a good test. Its copy must point at the copy, not at the original.

List one = List::build({5}, {0});
describe("single original", one.head);
List one_copy = copy_interleaved(one);
describe("single interleave", one_copy.head);
std::cout << "single check: " << check_copy(one.head, one_copy.head) << '\n';

Expected output:

single original: [5 random=0]
single interleave: [5 random=0]
single check: ok

The interleave method handles this case without a special branch. Step 1 makes the weave A, A'. In step 2, the random target of A is A itself, and A->random->next is A', so A' points at itself. The copy is independent of the original.

Example 3: many nodes that point at one node

A harder case is a list where many random pointers share one target. Here every node points at the fourth node. Both methods must give each copy a random pointer to the copy of the fourth node, not to the original.

List shared = List::build({1, 2, 3, 4}, {3, 3, 3, 3});
describe("shared original", shared.head);
List shared_copy = copy_with_map(shared);
describe("shared map copy", shared_copy.head);
std::cout << "shared check: " << check_copy(shared.head, shared_copy.head) << '\n';
List shared_copy2 = copy_interleaved(shared);
std::cout << "shared interleave check: " << check_copy(shared.head, shared_copy2.head) << '\n';

Expected output:

shared original: [1 random=3] [2 random=3] [3 random=3] [4 random=3]
shared map copy: [1 random=3] [2 random=3] [3 random=3] [4 random=3]
shared check: ok
shared interleave check: ok

The map method does this with one lookup per pointer, since the map always returns the copy of the same fourth node. The interleave method does it because every random target has a copy right after it, so all four nodes read the same position.

How the check works

A copy is correct only if three things are true. The values match in order. No node of the copy is a node of the original. Each random pointer points at the same position in the copy as it did in the original. The check_copy function tests all three.

std::string check_copy(const Node* original, const Node* copy) {
    std::unordered_set<const Node*> original_nodes;
    for (const Node* p = original; p != nullptr; p = p->next) {
        original_nodes.insert(p);
    }
    const Node* a = original;
    const Node* b = copy;
    while (a != nullptr && b != nullptr) {
        if (a->value != b->value) {
            return "value differs";
        }
        if (original_nodes.contains(b)) {
            return "copy shares a node with the original";
        }
        if (index_of(original, a->random) != index_of(copy, b->random)) {
            return "random pointer differs";
        }
        a = a->next;
        b = b->next;
    }
    if (a != nullptr || b != nullptr) {
        return "length differs";
    }
    return "ok";
}

The random test uses index_of on both lists. If the copy's random pointer points at an original node, index_of(copy, b->random) returns -2, which does not match the position in the original. This is how the check finds a shallow copy.

Common mistakes

Copying the random pointer as it is

The most common mistake is to copy the random pointer with a plain assignment, made->random = old->random;. The copy then points at the original list. The function below is the map method with that one line changed.

List copy_naive(const List& source) {
    List copy;
    std::unordered_map<const Node*, Node*> copy_of;
    for (const Node* old = source.head; old != nullptr; old = old->next) {
        copy_of[old] = copy.add(old->value);
    }
    for (const Node* old = source.head; old != nullptr; old = old->next) {
        Node* made = copy_of.at(old);
        made->next = old->next ? copy_of.at(old->next) : nullptr;
        made->random = old->random;
    }
    copy.head = source.head ? copy_of.at(source.head) : nullptr;
    return copy;
}

Running the check on this copy prints the following.

naive check: random pointer differs

The values and the next links look right, but describe shows the bad pointers as random=-2. The random pointers are the problem. Each one points at a node in the original, and index_of on the copy returns -2, because the node is not in the copy. Changing the value of an original node would change the copy's random target too, which is a shallow copy.

Dereferencing a random pointer that is null

In the interleave method, step 2 reads old->random->next. If old->random is null, that read is a null dereference, which means reading memory through a null pointer. The code has a check for this, old->random ? ... : nullptr, and removing the check causes a crash. The program below shows the crash on a two-node list where the first node has no random target.

#include <cstddef>
#include <iostream>
#include <memory>
#include <vector>
 
struct Node {
    int value;
    Node* next = nullptr;
    Node* random = nullptr;
    explicit Node(int v) : value(v) {}
};
 
int main() {
    std::vector<std::unique_ptr<Node>> storage;
    for (int v : {7, 13}) {
        storage.push_back(std::make_unique<Node>(v));
    }
    Node* first = storage[0].get();
    Node* second = storage[1].get();
    first->next = second;
    second->next = nullptr;
    first->random = nullptr;
    second->random = first;
 
    // Interleave the copies, as the O(1) method does.
    Node* copy_first = new Node(7);
    copy_first->next = second;
    first->next = copy_first;
 
    // Step 2 without a null check on the random pointer.
    Node* old = first;
    copy_first->random = old->random->next;
    std::cout << "copied random for 7 is " << copy_first->random->value << '\n';
    delete copy_first;
    return 0;
}

Compiled with g++ -std=c++20 -Wall -g -fsanitize=address, the program stops with this report. The sanitizer is a checking mode of the compiler that reports bad memory use.

AddressSanitizer:DEADLYSIGNAL
==176970==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x5cedf75a69cc bp 0x7ffc42dda160 sp 0x7ffc42dda010 T0)
==176970==The signal is caused by a READ memory access.
==176970==Hint: address points to the zero page.
    #0 0x5cedf75a69cc in main mistake_null.cpp:32

The address 0x000000000008 is the next field of a null node. The process ID and the other addresses change on each run, but the words SEGV and zero page and the line number stay the same. The fix is the check in the code: a null random pointer gives a null copy pointer, and no node is read.

Looking up a random target that is not in the list

The map method uses at, and at throws an exception when the key is not in the map. This happens when a random pointer leads to a node that is not part of the list being copied. The code below, placed in main after the functions above, builds such a list on purpose.

List outside = List::build({9}, {0});
List inside = List::build({1, 2}, {-1, -1});
inside.head->random = outside.head;
List broken = copy_with_map(inside);

The program stops with this message.

terminate called after throwing an instance of 'std::out_of_range'
  what():  unordered_map::at

The message says a key was missing from the map. The cause is the input, not the copy code. A random pointer must point inside the same list. If the input may be wrong, check it first, for example with index_of, which returns -2 for a node that is not in the list. Do not catch the exception and continue, because the copy would then be incomplete.

Forgetting to put the links back

The interleave method changes the source list. If step 3 is left out, the source keeps the copies in its chain. Its next pointers then walk through the copies too, so the source has twice as many nodes as it had before the call. The example in the main function prints the node count of the source after the call. The count is 5, which shows that step 3 restored the chain. Without that step, the count would be 10.

Practice

Exercise 1. Trace the map method on the list with values 1, 2, 3 and random targets at positions 2, none, 0. Write the output of describe for the copy.

Show the answer

The copy prints map copy: [1 random=2] [2 random=-1] [3 random=0]. The random target of value 1 is value 3, and the copy keeps the same positions. The output is the same as the original list, which is the goal of a correct copy.

Exercise 2. Write the number of nodes whose random pointer points at a later node, for the list with values 7, 13, 11, 10, 1 and random targets -1, 0, 4, 2, 0. Use the function count_forward_randoms.

Show the answer

The answer is 1. Only the node at position 2 has a target at a later position, namely position 4. The output of the example main function prints forward randoms: 1.

Exercise 3. The map method does two passes. Explain in plain words why the first pass must create every copy before the second pass sets any pointer.

Show the answer

The second pass sets the next and random pointers of each copy to other copies. A random target can be any node, including a node later in the list. If the copy of that node did not exist yet, the pass would have no node to point at. The first pass makes all copies, so every lookup in the second pass finds one.

Exercise 4. In step 2 of the interleave method, the code reads old->random->next. Explain why next is the right field to read, and why the map is not needed.

Show the answer

The weave in step 1 places each copy directly after its original. So the copy of any node is the node after it. If old->random is the original target B, then B->next is B's copy. A map is not needed because the copy is found from the link that already exists in the list.

Exercise 5. Give the time and extra space used by each method, where extra space means memory beyond the copy itself. Say which method changes the source list while it runs.

Show the answer

Both methods take time proportional to the number of nodes, because each one walks the list a fixed number of times. The map method uses extra space proportional to the number of nodes, because the map holds one entry per node. The interleave method uses a fixed amount of extra space, a few pointers. The interleave method changes the source list while it runs, and restores it at the end.

Summary

• A deep copy must make new nodes and point only at new nodes. A copy of the pointer values is a shallow copy and shares nodes with the original.
• The hash map method makes all the copies in one pass and sets the links in a second pass. It uses memory proportional to the list length.
• The interleave method puts each copy right after its original, reads the random targets from those copies, and then splits the lists. It uses a fixed amount of extra memory and changes the source for a short time.
• Always check that a random pointer is null before reading through it, and make sure every random pointer points into the same list.
• Test a copy by comparing values, checking that no node is shared, and checking that every random pointer points at the same position as in the original.