C++ linked lists with smart pointers

Question

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

#include <iostream>
#include <memory>

template<typename T>
struct link
{
    T data;
    std::shared_ptr<link> 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<typename T>
class linked_list
{
public:
    linked_list() : head(nullptr) {};
    ~linked_list() {};

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

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

template<typename T>
void linked_list<T>::reverse(void)
{
    std::shared_ptr<link<T>> prev;
    std::shared_ptr<link<T>> next;

    if (head == nullptr) return;

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

template<typename T>
void linked_list<T>::show(void)
{
    std::shared_ptr<link<T>> current(head);
    while (current)
    {
        std::cout << current->data << std::endl;
        current = current->next;
    }
}


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

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

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

    return 0;
}

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

2. 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?

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

Answer 1

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

144018.cpp: In instantiation of ‘link<T>::link(T) [with T = int]’:
144018.cpp:39:20:   required from ‘void linked_list<T>::push(T) [with T = int]’
144018.cpp:78:16:   required from here
144018.cpp:10:5: warning: ‘link<int>::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<link> next = {};

---

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

template<typename T>
struct link
{
    using pointer = std::shared_ptr<link>;

    T data;
    pointer next = {};
};

template<typename T>
class linked_list
{
    using link_pointer = typename link<T>::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<typename T>
void linked_list<T>::show()
{
    auto current = head.get();
    while (current)
    {
        std::cout << current->data << std::endl;
        current = current->next.get();
    }
}

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

template<typename T>
void linked_list<T>::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<typename T>
class linked_list
{
    using link_pointer = typename link<T>::pointer;

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

template<typename T>
void linked_list<T>::push(T elem)
{
    auto new_link = new link<T>(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<T>(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 <iostream>
#include <memory>

template<typename T>
struct link
{
    using pointer = std::unique_ptr<link>;

    T data;
    pointer next = {};

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

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

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

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

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

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

template<typename T>
void linked_list<T>::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<typename T>
void linked_list<T>::show() const
{
    auto current = head.get();
    while (current)
    {
        std::cout << current->data << std::endl;
        current = current->next.get();
    }
}


int main()
{
    linked_list<int> 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!