C++ linked lists with smart pointers

I want to know about smart pointers in C++11, so I started to write my own linked list implementation:

#include 
#include 

template
struct link
{
    T data;
    std::shared_ptr next;

    link(T value) : data(value) {}
    void add_to_end(T value)
    {
        if (next)
            next->add_to_end(value);
        else
            next.reset(new link(value));
    }

};

template
class linked_list
{
public:
    linked_list() : head(nullptr) {};
    ~linked_list() {};

    void push(T elem);
    void show(void);
    void reverse(void);
private:
    std::shared_ptr> head;
};

template
void linked_list::push(T elem)
{
    if (head == nullptr)
        head.reset(new link(elem));
    else
        head->add_to_end(elem);
}

template
void linked_list::reverse(void)
{
    std::shared_ptr> prev;
    std::shared_ptr> next;

    if (head == nullptr) return;

    while (head->next)
    {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    head->next = prev;
}

template
void linked_list::show(void)
{
    std::shared_ptr> current(head);
    while (current)
    {
        std::cout data next;
    }
}

int main(int argc, char *argv[])
{
    linked_list list;

    list.push(1);
    list.push(2);
    list.push(3);

    list.show();
    list.reverse();
    list.show();

    return 0;
}

-
I don't like to use shared pointers because they are used when multiple ownership is possible. But in linked list every node owns only the next one node. So I want to use unique_ptr. How can I use them? Unique pointers don't allow assignment which I use in my code.

-
I perform adding element into the end of list using link::add_to_end call. It looks not very good. How can I improve this code? What changes should I do if I want to write my push_front method to add into the head?

-
How else can I improve my code? What other problems does it have?

I get a warning from g++ -Weffc++:

144018.cpp: In instantiation of ‘link::link(T) [with T = int]’:
144018.cpp:39:20: required from ‘void linked_list::push(T) [with T = int]’
144018.cpp:78:16: required from here
144018.cpp:10:5: warning: ‘link::next’ should be initialized in the member initialization list [-Weffc++]
link(T value) : data(value) {}
^~~~


It's worth building with all the warnings you can stand. This one is easily fixed by declaring it as

std::shared_ptr next = {};

I found it easier to experiment with your code by encapsulating the specific pointer type within the classes:

template
struct link
{
    using pointer = std::shared_ptr;

    T data;
    pointer next = {};
};

template
class linked_list
{
    using link_pointer = typename link::pointer;

private:
    link_pointer head = {};
};

Then you can use pointer or link_pointer anywhere that auto won't do.

If I change link::pointer to be a std::unique_ptr, the errors I get are all within reverse() and show() (both of which I would implement outside of the class - the first as a specialization of std::reverse). But I'm guessing you implemented them as members for the educational value, so I'll continue. For show, you want to traverse the pointers without transferring ownership, so you can't use unique pointers for your traversal. But you know you can safely use raw pointers as long as you don't let them leak outside the objects' lifetimes:

template
void linked_list::show()
{
    auto current = head.get();
    while (current)
    {
        std::cout data next.get();
    }
}

Your reverse() method does want to take ownership, and can use std::move() to do so:

template
void linked_list::reverse()
{
    if (!head) return;

    link_pointer prev;
    link_pointer next;

    while (head->next)
    {
        next = std::move(head->next);
        head->next = std::move(prev);
        prev = std::move(head);
        head = std::move(next);
    }
    head->next = std::move(prev);
}

To add elements in O(1) time rather than O(n) time, maintain a (non-owning) pointer to the tail of the list:

template
class linked_list
{
    using link_pointer = typename link::pointer;

private:
    link_pointer head = {};
    link *tail = nullptr;
};

template
void linked_list::push(T elem)
{
    auto new_link = new link(std::move(elem));

    if (tail)
        tail->next.reset(new_link);
    else
        head.reset(new_link);
    tail = new_link;
}

Minor style points:

• You can write empty argument lists as () rather than C-style (void).

• The show() method can be const.

-
It's a bit more idiomatic to allow (raw or smart) pointer types to convert to bool than to test against nullptr:

{
    if (head)
        head->add_to_end(elem);
    else
        head.reset(new link(elem));
}

-
Constructors that immediately store their arguments can move from the argument:

link(T value) : data{std::move(value)} {}

This reduces copying (which may become more important when T is bigger than the int used in the test program).

Putting it all together, I get:

#include 
#include 

template
struct link
{
    using pointer = std::unique_ptr;

    T data;
    pointer next = {};

    link(T value) : data{std::move(value)} {}
};

template
class linked_list
{
    using link_pointer = typename link::pointer;

public:
    linked_list() = default;
    ~linked_list() = default;

    void push(T elem);
    void show() const;
    void reverse();
private:
    link_pointer head = {};
    link *tail = nullptr;
};

template
void linked_list::push(T elem)
{
    auto new_link = new link(std::move(elem));

    if (tail)
        tail->next.reset(new_link);
    else
        head.reset(new_link);
    tail = new_link;
}

template
void linked_list::reverse()
{
    if (!head) return;

    link_pointer prev;
    link_pointer next;

    while (head->next)
    {
        next = std::move(head->next);
        head->next = std::move(prev);
        prev = std::move(head);
        head = std::move(next);
    }
    head->next = std::move(prev);
}

template
void linked_list::show() const
{
    auto current = head.get();
    while (current)
    {
        std::cout data next.get();
    }
}

int main()
{
    linked_list list;

    list.push(1);
    list.push(2);
    list.push(3);

    list.show();
    list.reverse();
    list.show();
}

For your next steps, I think you'll want to add an iterator type and suitable begin() and end(). Then you'll be able to remove show() and replace it with a simple for (const auto& e: list) std::cout << e;

P.S. Thank you for providing the test program with the code - that certainly makes trying out changes easier!

StackExchange Code Review Q#144018, answer score: 5