4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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

\$\endgroup\$
  • 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 Apr 8 '16 at 12:38
  • \$\begingroup\$ @ruds Do you trust every input you are given? \$\endgroup\$ – vnp Apr 9 '16 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 Apr 9 '16 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.