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.

ruds · Accepted Answer · 2016-04-08 04:14:39Z

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

vnp · Accepted Answer · 2016-04-08 04:14:57Z

1

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.

answered Apr 8, 2016 at 4:14

vnp

58.7k4 gold badges55 silver badges144 bronze badges

1

\$\begingroup\$ 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. \$\endgroup\$

ruds
– ruds

2016-04-08 12:38:40 +00:00
Commented Apr 8, 2016 at 12:38
\$\begingroup\$ @ruds Do you trust every input you are given? \$\endgroup\$

vnp
– vnp

2016-04-09 05:29:01 +00:00
Commented Apr 9, 2016 at 5:29
1

\$\begingroup\$ 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. \$\endgroup\$

ruds
– ruds

2016-04-09 15:16:50 +00:00
Commented Apr 9, 2016 at 15:16

Add a comment |

Stack Exchange Network

Copy Constructor for a linked list with self-referential pointers

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Copy Constructor for a linked list with self-referential pointers

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions