Singly linked-list with smart pointers

Question

A few things:

1. I tried to do it with smart pointers because I wanted to learn about them. I'm not sure I made the right choice of type, however (and started to regret it half-way through).
2. This is for school, so some operations were required. I can't change main.cpp or the general layout.
3. insert() works. However, I'm suspicious it's not working properly. I haven't implemented delete functionality yet.

Any comments / suggestions appreciated.

Here's my singly linked list.

I've also posted this on Reddit.

List.cpp

#include "List.h"

void List::reverse_print(std::shared_ptr<Link> curr) const {
    if (curr) {
        reverse_print(curr->next);
        std::cout << curr->datum << '\n';
    }
}

void List::push_front(int val) {
    std::unique_ptr<Link> new_link(new Link(val));
    new_link->next = root;
    root = std::move(new_link);
}

void List::push_back(int val) {
    std::unique_ptr<Link> new_link(new Link(val));

    if (!root)
        root = std::move(new_link);

    else {
        std::shared_ptr<Link> curr(root);

        while (curr->next) {
            curr = curr->next;
        }

        curr->next = std::move(new_link);
    }
}

void List::insert(int val, int loc){

    if (loc > length( ) + 1 || loc < 1)
        std::cout << "Insertion location is invalid.\n";

    else {
        if (loc == 1)
            push_front(val);

        else if (loc == length() + 1)
            push_back(val);

        else {
            int node_count = 1;
            std::shared_ptr<Link> ptr(root);

            while (node_count < loc - 1) {
                ptr = ptr->next;
                ++node_count;
            }

            std::shared_ptr<Link> new_link(new Link(val));
            ptr->next = new_link;
        }
    }
}

int List::length() const { 

    int node_count = 0;
    std::shared_ptr<Link> ptr(root);

    while (ptr) {
        ptr = ptr->next;
        ++node_count;
    }

    return node_count;
}

void List::print() const {
    std::shared_ptr<Link> temp(root);

    if (!temp) {
        std::cout << "List is empty.\n";
        return;
    }

    std::cout << "Beginning.\n";

    while (temp) {
        std::cout << temp->datum << '\n';
        temp = temp->next;
    }

    std::cout << "Ending.\n"
    "Length of list : " << length() << " nodes.\n";
}

void List::reverse_print() const {
    std::cout << "Ending.\n";
    reverse_print(get_first());
    std::cout << "Beginning.\n"
    "Length of list : " << length() << " nodes.\n";
}

void List::initialize_list() const {
    if (this)  // not sure what to put here
        std::cout << "Empty list exists.\n";
}

std::shared_ptr<List::Link> List::get_first() const {
    return root;
}

void List::destroy_list() {
    root.reset();
};

bool List::empty( ) const {
    return root == nullptr;
}

/*
void delete_link( ){ }
void delete_first( ) { }
void delete_last( ) { }
*/

List.h

#ifndef LIST_H
#define LIST_H

#include <memory>
#include <iostream>

class List {
    struct Link {
        int datum;
        std::shared_ptr<Link> next;
        explicit Link(int val = 0) : datum{ val } { 
            std::cout << "Link constructor invoked.\n"; 
        }
        ~Link() { 
            std::cout << "Link destructor invoked.\n"; 
        }
    };  

    std::shared_ptr<Link> root;
    void reverse_print(std::shared_ptr<Link>) const;

    public:
        explicit List() : root{ nullptr } { 
            std::cout << "List constructor invoked.\n"; 
        }
        ~List() { 
            std::cout << "List destructor invoked.\n"; 
        }

        void push_front(int);
        void push_back(int);
        void insert(int, int);
        int length() const;
        void print() const;
        void reverse_print() const;
        void initialize_list() const;

        std::shared_ptr<Link> get_first( ) const;
        void destroy_list( );
        bool empty( ) const;

        //void delete_first( );
        //void delete_last( );
        //bool delete_link(int val);
};

#endif

Main.cpp

#include "Menu.h"
#include "List.h"

int main() {

    Menu menu;
    std::unique_ptr<List>list(new List());

    do {
        menu.display();
        menu.query_user();
        menu.process_command(list);
    } while (menu.cont());
}

Answer 1

Some comments to the things you have implemented so far:

1. reverse_print: Printing the list in reverse order recursively is an academically interesting solution but if your list is sufficiently long then your stack will explode. Use a std::stack to temporarily store the elements and then print that.
2. push_back: Currently this is O(n) because you iterate the entire list to find the last element. If you store a tail pointer which points to the last element in the list in addition to root then you can avoid that and this operation becomes O(1).
3. length(): Keep a length property in the class which you increment/decrement when a node got added/removed. Again reduces an O(n) operation to O(1).
4. insert():
   1. While it's commendable for the (application) user experience to have 1 based indices, as a programer who might use this it will be confusing. Indices into containers like arrays and vectors are 0 based in C++ land. Deviating from the standard is bad because it is unexpected.
   2. Insert is broken. You will lose all items after the insert position (new_link->next points to nothing and ptr->next now points to new_link -> all elements starting from the old ptr->next are now lost)

Answer 2

I wanted to offer a different angle, so definitely see the other answers. I'm mostly nitpicking:

1. Organize your code top-down. Show the header for the cpp file, and probably main before either. Why? So that by the time we see the guts of the code, we have a sense for what you want to do.
2. Don't omit parameter names in the header file - they help self-document your API.
3. Prefer std::make_shared to the std::shared_ptr constructor, always. Use auto to make this easy. When C++14 rolls around, use std::make_unique instead of the std::unique_ptr constructors for the same reasons.
4. Be consistent about using curly-brace initialization.
5. Use using statements in the cpp file. Recall that you can do using std::cout; to just pull in that one symbol, rather than the entire standard library. This also documents your specific dependencies on headers nicely at the top.
6. Pass std::shared_ptr's by const-reference to avoid copying them when you don't need to.
7. (Super nitpicking) Curly-brace your one line statements (ifs). It's a maintenance hazard if you don't. I've seen too many very competent programmers introduce silly bugs by doing this and mixing up their indentation. On the scale of importance maintainability >> linecount.
8. It's not at all clear why in main your List is stored inside a std::unique_ptr. If this is meant to disable copy operations, you're doing so via the wrong avenue, as a user who doesn't know better won't put it in a std::unique_ptr. Instead, actually go ahead and explicitly disable copy operations, since they would yield surprising semantics.
9. Prefer the name clear to destroy_list. It is more idiomatic (in that it matches the behavior and nomenclature of the standard library). size is also more idiomatic than length in C++.

Answer 3

Everything @ChrisWue said.

Also:

Design.
Using sharded_ptr<> does have affects on meaning (especially when copying). And I don't think you handle that correctly. Also You are building a container like structure. Usually memory management is done either by container (for groups of values) or by smart pointer (for single values). These are complementary types of memory management and intermixing them adds redundancy. You are already writing code to manage memory why add another layer on top (you can but it usually more efficient to do it manually).

So personally I would have not gone with smart pointers here (because you are building a container).

But the problem:

   List   a;
   // Do stuff with a

   List   b(a);  // Make a copy of `a`

This is not doing what you expect.
With your code both list share the underlying list of nodes. If I modify one of these objects then the other one is modified in parallel. This may be deliberate and feature but it violates the principle of least surprise and thus should be clearly documented if delibrate.

Note I: Same applies to assignment operator.
Note II: The compiler automatically generates the copy constructor and assignment operator.

I will assume the above was a mistake. Basically I believe you are using the wrong smart pointer. The list of nodes contained by the list is solely owned by the container and there is no shared ownership. A more appropriate smart pointer would have std::unique_ptr<>. If you would have used this the compiler would have complained when you tried to build as the default copy constructor would have not worked.

The reason for using a smart pointer to control memory management is that it can get quite convoluted in normal code. But because your code hides the link object internally the number of use cases is limited (nobody can abuse your object just you). So this makes memory management simpler and you can quite easily implement it yourself (but std::unique_ptr is a perfectly valid alternative in this case).

Note 3: Implement the Copy constructor. Implement assignment in terms of copy construction by using the Copy and Swap idiom.

Edit: Based on question comment

Adding an element to a list that uses std::unique_ptr

struct Node
{
    std::unique_ptr<Node> next;
};

void insert(std::unique_ptr<Node>& after, std::unique_ptr<Node>& newNode)
{
    /*
     * after:      A node in the chain.
     * newNode:    A new node (with next NULL) that needs to be added to the chain.
     *
     * This function adds `newNode` to the chain.
     * Post condition:  after->next    = newNode
     *                  newNode->next  = after(before call)->next;
     */
    std::swap(after->next, newNode->next);   // newNode->next now points to the rest of the chain.
    std::swap(after->next, newNode);         // newNode added to chain.
}