Singly linked-list with smart pointers

Question

Here's my Singly Linked List

A few things:

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).
This is for school, so some operations were required. I can't change main.cpp or the general layout.
insert() works. However, I'm suspicious it's not working properly. I haven't implemented delete functionality yet.

Any comments / suggestions appreciated.

*Also sorry for the formatting. I'll try to fix it when I'm off work.

I also posted this on reddit

Also code here:

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());

}

Welcome! As per the FAQ, please embed the code you'd like to have reviewed. — Jamal♦, Oct 23 at 20:29
Please add your code to the question. This does two things 1) Puts the source in public domain see: blog.stackoverflow.com/2009/06/attribution-required 2) Makes sure the question stays relevant for future readers (If the code is on another site that site may disappear; making the work of the contributes here irrelevant and waste their time). — Loki Astari, Oct 23 at 21:17

ChrisWue · Accepted Answer · 2013-10-24 09:11:04Z

Some comments to the things you have implemented so far:

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

This is exactly what I was looking for. Thanks for taking the time to look at it! — Bogo Sort, Oct 24 at 17:43

Loki Astari · Answer 2 · 2013-10-29 05:45:39Z

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

Thanks for looking at my code. I've given it some thought and revamped the code quite a bit, however I'm not sure how to acomplish insert_front or insert at any location other than back with unique_ptrs. Any ideas? Here is my new push_back function — Bogo Sort, Oct 29 at 5:10

asked	2 months ago
viewed	193 times
active	2 months ago

Explore our sites

Singly linked-list with smart pointers

List.cpp

List.h

Main.cpp

2 Answers

Edit: Based on question comment

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ homework linked-list or ask your own question.

Hot Network Questions

Explore our sites

Singly linked-list with smart pointers

List.cpp

List.h

Main.cpp

2 Answers

Edit: Based on question comment

Your Answer

Sign up or login

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ homework linked-list or ask your own question.

Related

Hot Network Questions