Linked List: Smart Pointer Implementation

Question

Linked list using smart pointers, iterative implementation. It amazes me how a std::forward_list does not allow the list to be walked until the last pointer is null.

I would appreciate if you could pay special attention to usage of shared_ptr.

#include <iostream>
#include <string>
#include <memory>
#include <cmath>

const int SIZE=7;

struct Node {
    int val;
    std::shared_ptr<Node> next;
};
std::shared_ptr<Node> newNode(int v) { // Create and return new node
    std::shared_ptr<Node> n(new Node);
    n->val = v;
    n->next = NULL;
    return n;
}
void print(std::shared_ptr<Node> r) { // Print the list
    while (r != NULL) {
        std::cout << r->val << ' ';
        r = r->next;
    }
    std::cout << std::endl;
}
int main() {
    std::shared_ptr<Node> root(new Node), last;
    srand(time(NULL));
    root->val = rand();
    root->next = NULL;
    last = root;
    for (int i=1; i<SIZE; ++i) { // Build the list
        last->next = newNode(rand());
        last = last->next;
    }
    last->next = NULL; 
    print(root); 
    std::cout << std::endl;
    return 0;
}

Answer 1

I would appreciate if you could pay special attention to usage of shared_ptr.

This fills me with dread. It implies that you want every node to have shared ownership. My question would be, "shared with what? another list?".

shared_ptr contains code for thread-safe reference counting. For this reason, use of a shared_ptr in a single-threaded program brings with it an unnecessary overhead.

There may be some use cases for sharing nodes - for example in a directed graph structure. In this case, almost any other container for holding node pointers would be superior to a linked list.

Before I can continue the review, I'd have to ask what the intended use-case of the list is.

After comments, here's an implementation that uses unique_ptr. Comments inline.

You will see that I have dropped the last pointer as it's not required. If you want 2-way linkage then use a ptr_type for the forward pointer and an observer_type for the back-link.

#include <iostream>
#include <string>
#include <memory>
#include <cassert>

const int SIZE=7;


// create the concept of an observer-only deleter
struct observer_only {
    template<class Any>
    void operator()(Any*) const noexcept {
        // nop
    }
};

// abstract the pointer type so we can change it if we don't like it
template<class Node> using ptr_type = std::unique_ptr<Node>;

// create the concept of an observer-only pointer
template<class Node> using observer_type = std::unique_ptr<Node, observer_only>;

// a means of converting a raw pointer to an observer
template<class Node> auto observe(Node* ptr) {
    return observer_type<Node>(ptr);
}

// a means of creating an observer to an owning pointer
template<class Node> auto observe(ptr_type<Node> const& ptr) {
    return observe(ptr.get());
}

struct Node {
    Node(int i)
            : val(i)
    {}

    // member function to add nodes provides logical encapsulation
    observer_type<Node> insert_after(ptr_type<Node>&& ptr) {
        assert(ptr.get());
        assert(ptr->next.get() == nullptr);
        ptr->next = std::move(this->next);
        this->next = std::move(ptr);
        return observe(this);
    }

    int val;
    ptr_type<Node> next = nullptr;
};

// node generator
ptr_type<Node> newNode(int v) { // Create and return new node
    ptr_type<Node> n(new Node(v));
    return n;
}

// print an observer
void print(observer_type <Node> o) { // Print the list
    for ( ; o.get() != nullptr ; o = observe(o->next))
    {
        std::cout << o->val << ' ';
    }
    std::cout << std::endl;
}

// print a node
void print(ptr_type<Node> const& r) { // Print the list
    print(observe(r));
}

// test
int main() {
    srand(time(NULL));
    auto root = newNode(rand());
    auto observer = observe(root);
    for (int i=1; i<SIZE; ++i) { // Build the list
        observer = observer->insert_after(newNode(rand()));
    }
    print(root);
    std::cout << std::endl;
    return 0;
}

Explanation of architectural approach

As requested in comments.

The the old days of assembler or C I'd have implemented a singly linked list (the second-simplest of all data structures) as merely a node containing a value and a pointer (address) to the next node. Of course we'd have to remember to destroy the node when removing it. We'd also have to remember whether a pointer "owned" (controlled the lifetime of) a node, or was merely an observer.

In modern c++, there are at least 2 enhancements available. First of course, we have RAII and smart pointers, so the destruction timing is always correct. Second, we can use types to indicate roles.

In the above code, I have two pointer types. One is an "owner" pointer and one is an "observer". These are both specialisations of unique_ptr in my code, but I could have written my own. However, using unique_ptr, I have some built in advantages:

1. a unique_ptr cannot be copied, so I cannot cause myself problems by accidentally sharing ownership.

2. even though the owning and non-owning pointers have different deleters (the observer's deleter is a no-op), they have the same interfaces. This makes generic programming easy.

In c++17, there is a template called std::observer_ptr, which is designed to perform the same role as my observer_type.

Now I can use the owner_type to handle the forward node linkages. This gives me clean RAII and firm ownership of nodes. It also mean that I can implement a remove function which returns the removed node pointer. I can then re-insert that node pointer into another list, or discard it (let it go out of scope). Either way, because it's controlled by an auto-deleting unique_ptr, the code will be correct. No leaks.

All operations on the list that do not affect lifetimes are done through an observer (there is a free function to create an observer from an owner). This provides both a visual cue to a maintainer, plus a compiler guarantee, that I won't accidentally mutate lifetimes when I am supposed to be observing or merely mutating the value held in the node.

fully linked list

OK, but how would I implement a linked list this way (i.e. with back-links as well as forward-links)?

We'd pick an 'owning' direction. Lets say forwards. Nodes would contain an owner_type pointing to and owning the next node, and an observer_type pointing to the previous node.

The list 'begin' pointer is an owner_type, the list's 'end' is an observer_type.

The Node would look something like this:

struct Node
{
    int value;  // my value type

    owner_type<Node>    next;   // pointer to the next node
    observer_type<Node> prev;   // observer of the previous node.
};

Inserting an removing nodes is the same as if they were raw pointers, it's just that we need to assign the pointers using std::move, because they're not copyable.

This is good, because it shows graphically in the code what we are trying to achieve. It forces us to spell out our intentions. If the code is later modified, it will be more difficult to introduce a logic error, because logically incorrect code won't compile.