Doubly linked list reimplemented with smart pointers

Question

I need some suggestions on my reimplementation of a doubly linked list with smart pointers since I'm new to smart pointers in C++.

I read some docs on smart pointers and found out there are shared_ptr<Obj>, unique_ptr<Obj> and weak_ptr<Obj>. I only use shared_ptr<Obj> in my current code, but I'm not sure how to use unique_ptr<Obj> in my doubly linked list. I would like someone can give me some pointers on how and where to use unique_ptr<Obj> in my DLL.

class Node{
    public:
        int data;
        Node(int data){
            this->data = data;
        }
    public:
        shared_ptr<Node> prev;
        shared_ptr<Node> next;
};

class LinkedList{
    public:
        shared_ptr<Node> head;
        shared_ptr<Node> tail;
    public:
        LinkedList(){}

        void fun(){
            printf("fun()\n");
        }

        void append(shared_ptr<Node> node){
            if(!head){
                head = node;
                tail = head;
            }else{
                tail->next = node;
                node->prev = tail;
                tail = node;
            }
        }

        void print(){
            shared_ptr<Node> curr = head;
            while(curr){
                printf("[%d]\n", curr->data);
                curr = curr->next;
            }
        }
        void remove(shared_ptr<Node> node){
            shared_ptr<Node> curr = head;
            if(node && curr){
                while(curr){
                    if(curr == node){
                        if(curr->prev == nullptr){
                            if(curr->next == nullptr){
                                // [curr] 
                                node.reset();
                                head.reset();
                                tail.reset();
                            }else{
                                // [curr]->[] 
                                shared_ptr<Node> next = curr->next;
                                curr->next.reset();
                                next->prev.reset();
                                head = next;
                            }
                        }else{
                            if(curr->next == nullptr){
                                // []->[curr] 
                                shared_ptr<Node> prev = curr->prev;
                                curr->prev.reset();
                                prev->next.reset();
                                tail = prev;
                            }else{
                                // []->[curr]->[]
                                shared_ptr<Node> next = curr->next;
                                shared_ptr<Node> prev = curr->prev;
                                next->prev = prev;
                                prev->next = next;
                            }
                        }
                    }
                    curr = curr->next;
                }
            }
        }
};

Answer 1

Summary

This is obviously a personal opinion, but I don't really like the interface you've defined for your list. By defining your methods in terms of a shared_ptr<Node>, you're making the caller responsible for constructing Nodes. It seems like Node should be an implementation detail of your list. Otherwise, since the caller has complete access to the Node they can iterate the list and modify it without the LinkedList class being called at all.

I'd define the interface in terms of the Data that is to be stored, currently this is an int, so you would have something like this:

void append(int newValue)

Or you may want to define your list in terms of a template and take in a pointer of the relevant type. This could be a shared_ptr if ownership of the data doesn't pass solely to your list, or it could be a unique_ptr if the node that references it will be the owner of the Data.

Append

Looking at your current implementation, what happens if a Node is passed in that already has its prev and next pointers populated (with the given interface I could assume that I could insert a Node chain). These pointers aren't checked, they're overwritten. This is part of why I don't like the interface...

Remove

What happens if you're asked to remove a node that isn't in the list? Currently nothing. It feels like this method should either be returning an indicator that the object has been removed, or more likely throwing an exception to indicate that it hasn't..

Answer 2

I see a number of things that may help you improve your code.

Make sure to #include all required headers

This program calls printf and uses shared_ptr but does not include the corresponding headers. Fix that by adding these lines:

#include <cstdio>
#include <memory>

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. It isn't necessarily wrong to use, but be aware of when you absolutely shouldn't do it (such as in header files).

Prefer iostreams to printf

If you're writing C++, it's usually better to write using iostreams rather than printf because printf uses a very loose coupling of object to type (and incurs a runtime cost) while an iostream has a much better coupling and moves more of its processing to compile time. In this code, rather than this:

printf("[%d]\n", curr->data);

write this:

std::cout << '[' << curr->data << "]\n";

Rethink the interface

As written, the code has the following member functions:

LinkedList();
void fun();
void print();
void append(std::shared_ptr<Node> node);
void remove(std::shared_ptr<Node> node);

Is this a reasonable interface? My answer would be an emphatic "no!" First, the fun() function seems to be some kind of experiment and should probably be omitted. Second, all of the functions return void -- that doesn't really make much sense. Third, and most importantly, the use of std::shared_ptr means that the caller has to create and pass in a std::shared_ptr<Node> which isn't a very good interface design because it requires the caller to have intimate knowledge of the design of your data structure. Better would be to have an interface that allows passing just the contents of a node (an int in this case), and the print() would be better expressed as a friend function:

friend std::ostream& operator<<(std::ostream& out, const LinkedList &list);

Think carefully about object ownership

The design employs std::shared_ptr which implies multiple ownership. This might make sense for multithreaded code, but not really for a generic linked list.

Fix the bug

If the caller uses your interface like this:

LinkedList mylist;
mylist.append(std::make_shared<Node>(Node(7)));
mylist.append(nullptr);
mylist.append(std::make_shared<Node>(Node(42)));

the program crashes. That's because it never checks to make sure that the incoming pointer is not nullptr. Any time you write code that deals with pointers, it's important to make such checks.