# Copy Constructor for a linked list with self-referential pointers

I came across a coding challenge that looked something like this (recreating from memory, sorry)

Suppose you have the following interface for a linked list. Implement an efficient and correct copy constructor.

template <typename T>
public:
void push_back(const T& value);
private:
struct Node;

std::size_t size_;

struct Node {
/// The next node in the linked list
Node* next_;
/// A random node in the linked list
Node* random_;
T value_;
};
};


I was allowed to assume that the other functions were implemented as well as provide additional member functions as needed, and came up with this.

#include <cstddef>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <utility>
#include <random>
#include <iostream>

static std::mt19937 rng(std::random_device{}());

template <typename T>
public:

while (current) {
Node* next = current->next_;
delete current;
current = next;
}
}

void push_back(const T& value) {
++size_;
if (size_ == 1) {
std::uniform_int_distribution<size_t>d(0, 1);
head_ = new Node{nullptr, nullptr, T(value)};
} else {
while (current->next_ != nullptr) {
current = current->next_;
}

std::uniform_int_distribution<size_t> d(0, size_-1);
size_t index = d(rng);
for (size_t i = 0; i < index; ++i) {
random = random->next_;
}

current->next_ = new Node{nullptr, random, T(value)};
}
}

template <typename V>
friend
std::ostream& operator<<(std::ostream& out, const SillyLinkedList<V>& rhs);

private:
struct Node;

std::size_t size_;

struct Node {
/// The next node in the linked list
Node* next_;

/// A random node in the linked list (may be "end" == nullptr)
Node* random_;
T value_;
};
};

template <typename T>
std::ostream& operator<<(std::ostream& out, const SillyLinkedList<T>& rhs) {

while (current != nullptr) {
out << " Location: " << current << " Random: " << current->random_ << std::endl;
current = current->next_;
}
return out;
}

template <typename T>
if (rhs.size_ != 0) {
std::unordered_map<Node*, Node*> nodePositions;

nodePositions.insert(std::make_pair(nullptr, nullptr));

while (rhsCurr != nullptr) {
nodePositions.insert(std::make_pair(rhsCurr, current));
current->value_ = (rhsCurr->value_);
current->random_ = rhsCurr->random_;
current->next_ = rhsCurr->next_ == nullptr ? nullptr : new Node;
current = current->next_;
rhsCurr = rhsCurr->next_;
++size_;
}

while (current != nullptr) {
current->random_ = std::get<1>(*nodePositions.find(current->random_));
current = current->next_;
}
}
}

int main() {
for (int i = 0; i < 31; ++i) {
l.push_back(1 << i);
}
std::cout << l << std::endl;
std::cout << l2 << std::endl;
}


I'd appreciate feedback on any part of the code, however, in particular, I'd appreciate a look at the copy constructor. It's correct (as far as I can tell), but I'm not sure how clear it is what I'm doing, or if there is a better solution.

The copy constructor looks correct and efficient, except that with the given implementation, you can save the second iteration through the nodes, as rhsCurr->random_ is guaranteed to point to a node already in nodePositions (push_back always assigns random_ to a node already in the list and there's no other code that removes nodes or reassign's a node's random_ member). I would also replace std::get<1>(*nodePositions.find(current->random_)) with nodePositions.at(current->random_), which is more straightforward and will not throw in this case.

I don't really like your assignment of random_ in push_back; for the first node, you have a 50-50 chance of pointing to itself or "end", but every other node has no chance of pointing to itself. No node points to a later node in the list. An alternative is to use an unordered_map as in the copy constructor, and to re-assign random_ for every node each time the list is modified, with a uniform distribution over each node + "end".

• An immediate problem is an that rhs may loop, so

    while (rhsCurr != nullptr) {


is not enough. You need some sort of loop detection. Maybe,

        while (size_ != rsh.size_)


would suffice.

• A dummy node technique is always recommended:

    Node dummy;
Node * current = &dummy;
while (...) {
current->next = new Node(rhsCurr);
current = current->next;
nodePosition.insert(...);
rhsCurr = rhsCurr->next;
...
}


just to avoid current->next_ = rhsCurr->next_ == nullptr ? nullptr : new Node; which IMHO is pretty ugly.

• rhs can't loop with this implementation of push_back, or with any reasonable implementation of it. Users of the class have no access to Node or any node's next_ member, so the class can maintain the invariant that its nodes don't loop. – ruds Apr 8 '16 at 12:38
• @ruds Do you trust every input you are given? – vnp Apr 9 '16 at 5:29
• I trust the invariants of my own code. The only way loop detection would be necessary is if someone else created a memory buffer, twiddled the bits, cast it to a SillyLinkedList, and then called the copy constructor. This is not something worth defending against. – ruds Apr 9 '16 at 15:16