2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Why not rather using a std::list<std::shared_ptr<int>> instead? \$\endgroup\$ – πάντα ῥεῖ Jan 24 '17 at 3:06
  • 1
    \$\begingroup\$ ..or just a std::forward_list, right :D? The point is to recreate a classic linked list, which can be walked until the next pointer is NULL. Oddly, this is not possible with std::forward_list. \$\endgroup\$ – kmiklas Jan 24 '17 at 3:13
  • 2
    \$\begingroup\$ I added the "reinventing the wheel" tag which is intended for implementing something that already exists for challenge/learning purposes. Hope you get great answers! \$\endgroup\$ – Phrancis Jan 24 '17 at 3:19
  • \$\begingroup\$ Astounding to me is that a std::forward_list cannot be walked until the next pointer is NULL. That was a classic question! Also, they LOVE to ask linked list questions on interviews, and swooping a problem with a library function won't impress the hiring manager. \$\endgroup\$ – kmiklas Jan 24 '17 at 3:26
  • \$\begingroup\$ Can you explain what you mean by "Astounding to me is that a std::forward_list cannot be walked until the next pointer is NULL"? Isn't that exactly what's expressed by for (auto&& elem : myfwdlist)? \$\endgroup\$ – Quuxplusone Jan 24 '17 at 5:47
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Use case is on an interview where a linked list must be implemented--and std::forward_list is not acceptable. Traditionally, raw pointers were used to point to the next node in the list. In an effort to modernize the linked list implementation, I'm trying to replace them with smart pointers. \$\endgroup\$ – kmiklas Jan 24 '17 at 18:10
  • \$\begingroup\$ The reason why I used shared_ptr is because I will use temporary pointers to nodes for various reasons: manipulating the list, reversing it, sorting, etc. std::unique_ptr will not work here, because there will be multiple pointers to the same node. \$\endgroup\$ – kmiklas Jan 24 '17 at 18:12
  • \$\begingroup\$ @kmiklas use std::unique_ptr and std::move to move them. You don't need shared_ptr. Linked list is the simplest data structure in the book. It's never needed reference counting. \$\endgroup\$ – Richard Hodges Jan 24 '17 at 18:23
  • \$\begingroup\$ if I use unique_ptr, and need a pointer to a specific node in the list, I'm in trouble. Given the nature of singly-lists, where random access is not possible, this is common practice--and has come up twice on interviews. For example, let's say I want a temporary pointer to the 4th node. unique_ptr will not allow tmp = next (next of node 3, which points to node 4), because that would create shared ownership, which is not allowed. That's why I used shared_ptr. \$\endgroup\$ – kmiklas Jan 24 '17 at 18:52
  • 1
    \$\begingroup\$ @kmiklas updated answer with a working example that uses unique_ptr. \$\endgroup\$ – Richard Hodges Jan 24 '17 at 20:21

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.