Circular double linked list with smart pointers in c++

Question

Is it possible to create a circular doubly-linked list using smart pointers in C++

struct Node {
  int val;
  shared_ptr<Node> next;
  weak_ptr prev;
};

shared_ptr<Node> head;

But this will have a circular reference of shared pointers and thus not deallocate correctly.

Answer 1

Make the circular linked list a class itself (with whatever operations you need to build it, like append). Have its destructor break the link by setting tail->next = nullptr. It should not matter which link you break, so if you're not using a head and tail, just set any one of them nullptr, and you're good.

In my testing, I made a circular linked list, and the nodes did not destruct. Then at the end, I added tail->next = nullptr before it exited, and all the destructors fired correctly.

Answer 2

My original posted answer was rather light on details. This one gives a proper explanation of how you can achieve a circular linked list without a memory leak and still adhere to the Rule of Zero. The answer is basically the same, using a sentinel, but the mechanism is a little more involved than I had originally let on.

The trick is to use a sentinel type that behaves just like a list node, but in fact does not really have a shared pointer to the head of the list. To achieve this, the node class should be separated into a behavior object and a state object.

class NodeState {
    std::shared_ptr<Node> next_;
    std::weak_ptr<Node> prev_;
    int value_;
    NodeState (int v) : value_(v) {}
    NodeState (std::shared_ptr<Node> p) : next_(p), prev_(p) {}
    //...
};

class Node {
    virtual ~Node () = default;
    virtual NodeState & state () = 0;
    std::shared_ptr<Node> & next () { return state().next_; }
    std::weak_ptr<Node> & prev () { return state().prev_; }
    int & value () { return state().value_; }
    void insert (const std::shared_ptr<Node> &p) {
        //...
    }
};

Now, you can define a node implementation and a sentinel implementation.

class NodeImplementation : public Node {
    NodeState state_;
    NodeState & state () { return state_; }
    NodeImplementation (int v) : state_(v) {}
    //...
};

class NodeSentinel : public Node {
    List &list_;
    NodeSentinel (List &l) : list_(l) {}
    NodeState & state () { return list_.sentinel_state_; }
};

The list itself contains a NodeState used by the sentinel object. Upon initialization, the list creates a sentinel object and initializes its state.

class List {
    //...
    NodeState sentinel_state_;
    std::shared_ptr<Node> head () { return sentinel_state_.next_; }
    std::shared_ptr<Node> sentinel () {
        return std::shared_ptr<Node>(head()->prev());
    }
    //...
public:
    List () : sentinel_state_(std::make_shared<NodeSentinel>(*this)) {}
    //...
    void push_front (int value) {
        head()->insert(std::make_shared<NodeImplementation>(value));
    }
    void push_back (int value) {
        sentinel()->insert(std::make_shared<NodeImplementation>(value));
    }
    //...
};

So, what does this organization do? It avoids the issue of a circular reference by using a sentinel node to act as the break. While the tail of the list points to the sentinel object, the sentinel object itself does not point to anything. Instead, it uses the state of the list itself to determine its next and previous neighbors.

Thus, the circular shared pointers only persists as long as the list exists. Once the list is destroyed, Item A loses its reference, and via the domino effect, Sentinel itself will be destroyed.

A fundamental point is that the sentinel object itself must never be exposed to the user of the list interface directly. It should remain internal to the list object at all times. It essentially represents end() in an STL like container, and logically, it can never be removed from the list (until the list itself is destroyed). In practice, this means removal operations on the list need to exit early if the passed in iterator represents the sentinel.

Demo

Try It Online

Answer 3

It is also possible to define a member function next() which can select between a shared or weak pointer.

#include <iostream>
#include <memory>
using namespace std;

struct T {
    int n_;
    shared_ptr<T> next_;
    weak_ptr<T> weaknext_;
    T(shared_ptr<T> next, int n) : next_(next), n_(n) {};
    auto next() {
         if (next_ == nullptr)
             return shared_ptr<T>(weaknext_);
         return next_;
    }
    ~T() { cout << n_ << "ok\n"; }
};
int main() {
    auto p0 = make_shared<T>(nullptr, 1);
    auto p1 = make_shared<T>(p0, 2);
    auto p2 = make_shared<T>(p1, 3);
    p0->weaknext_ = p2;  //makes the list circular
    auto p = p2;
    for (int i = 0; i < 5; ++i) {
        cout << p->n_ << "\n";
        p = p->next();
    }
}