Copy Constructor for a linked list with self-referential pointers

Question

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>
class SillyLinkedList {
 public:
 SillyLinkedList();
 SillyLinkedList(const SillyLinkedList<T>& rhs);
 ~SillyLinkedList();
 void push_back(const T& value);
 private:
 struct Node;
 Node* head_;
 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>
class SillyLinkedList {
 public:
 SillyLinkedList() : head_(nullptr), size_(0) {}
 SillyLinkedList(const SillyLinkedList<T>& rhs);
 ~SillyLinkedList() {
 Node* current = head_;
 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)};
 head_->random_ = d(rng) == 0 ? head_ : nullptr;
 } else {
 Node* current = head_;
 while (current->next_ != nullptr) {
 current = current->next_;
 }
 std::uniform_int_distribution<size_t> d(0, size_-1);
 size_t index = d(rng);
 Node* random = head_;
 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;
 Node* head_;
 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) {
 using NodeType = typename SillyLinkedList<T>::Node;
 NodeType* current = rhs.head_;
 while (current != nullptr) {
 out << " Location: " << current << " Random: " << current->random_ << std::endl;
 current = current->next_;
 }
 return out;
}
template <typename T>
SillyLinkedList<T>::SillyLinkedList(const SillyLinkedList<T>& rhs) : head_(nullptr), size_(0) {
 if (rhs.size_ != 0) {
 std::unordered_map<Node*, Node*> nodePositions;
 Node* rhsCurr = rhs.head_;
 head_ = new Node;
 Node* current = head_;
 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_;
 }
 current = head_;
 while (current != nullptr) {
 current->random_ = std::get<1>(*nodePositions.find(current->random_));
 current = current->next_;
 }
 }
}
int main() {
 SillyLinkedList<int> l;
 for (int i = 0; i < 31; ++i) {
 l.push_back(1 << i);
 }
 SillyLinkedList<int> l2 = l;
 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.

Answer 1

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".

Answer 2

• 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.

• ruds: 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.
• vnp: @ruds Do you trust every input you are given?
• ruds: 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.