A doubly linked list implementation using C++ smart pointers

I am new to "modern" C++ and decided to learn about smart pointers by implementing a doubly linked list.

I have a few problems with this code: Should the tail pointer be a weak pointer? Should the head pointer be a unique pointer (If yes, then the node after head will have a weak_ptr to the head node, causing a unique_ptr and a weak pointer pointing to the same object)?

```
#include
#include

template
class LinkedList {
public:
LinkedList();
int GetLength() const;
void Print() const;
// TODO: Implement and return an iterator.
void Append(T data);
// TODO: Implement and return an iterator.
void Prepend(T data);
bool Delete(T data);

private:
struct ListNode {
T data;
std::shared_ptr next;
std::weak_ptr prev;

ListNode(T data) : data(data) {}
};
int length;
std::shared_ptr head;
std::shared_ptr tail;

void Delete(std::shared_ptr ptr);
};

template
LinkedList::LinkedList()
: length(0) {}

template
int LinkedList::GetLength() const {
return length;
}

template
void LinkedList::Print() const {
std::shared_ptr h(head);
std::cout data next;
}
std::cout
void LinkedList::Append(T data) {
std::shared_ptr node_ptr(std::make_shared(data));
node_ptr->prev = tail;

if (tail) {
tail->next = node_ptr;
tail = std::move(node_ptr);
} else {
tail = std::move(node_ptr);
head = tail;
}

length++;
}

template
void LinkedList::Prepend(T data) {
std::shared_ptr node_ptr(std::make_shared(data));
node_ptr->next = head;

if (head) {
head->prev = node_ptr;
head = std::move(node_ptr);
} else {
head = std::move(node_ptr);
tail = head;
}

length++;
}

template
bool LinkedList::Delete(T data) {
std::shared_ptr ptr = head;
while (ptr) {
if (ptr->data == data) {
Delete(ptr);
return true;
}

ptr = ptr->next;
}

return false;
}

template
void LinkedList::Delete(std::shared_ptr ptr) {
auto shared_prev = (ptr->prev).lock();

if (head == ptr) {

This review will focus on ListNode.
ListNode

The constructor takes its argument by copy, whether the argument is a char or a 1'000'000 element std::vector<>. Additionally, there is no exception specification.

Before:

ListNode(T data) : data(data) {}
//                 ^^^^^^^^^^ another copy is made here
//       ^^^^^^ a copy is made here

• In order to prevent the first copy, you should pass it as T const&.

• Use type traits to add an exception specification.

After:

#include  // for the std::is_nothrow_xxx family of template traits

ListNode(T const& data) // the argument is now taken by const&
noexcept(std::is_nothrow_copy_constructible::value) // correct exception specification
    : data(data) // now, only one copy is made: here.
{}

Additional remarks:

• Consider adding a constructor that takes a T&& for efficiency.

• Consider having only one constructor that directly initializes data by using a variadic template and perfect forwarding.

The std::unique_ptr<> and std::shared_ptr<> types model ownership semantics. Meaning that the smart pointer instance itself owns the memory it points to. In a linked list, the list owns the nodes and their values.

Currently, when ListNode's destructor is called, it will start a recursive chain of calls: freeing a node requires freeing its next data member, which requires freeing the next data member's next data member, and so on.

This is inefficient and limits the number of elements that your list can contain to the recursive limit that your stack allows; it is reason enough to remove ownership semantics by using raw pointers over std::shared_ptr<>.

To deal with this change, you simply define a destructor for LinkedList:

~LinkedList() noexcept(std::is_nothrow_destructible::value)
{
    for (ListNode* current = head, *next; current;)
    {
        next = current->next;
        delete current;
        current = next;
    }
}

Note that this will require you to provide the proper move and copy operations for your LinkedList type by hand as well.

From looking at your declaration (not your implementation), here's some points for:
LinkedList

• Provide a size_type alias for your container. Assuming I want to fill the linked list up to its theoretical maximum size, I need to know how many elements it can support. This is determined by the maximum value of the length data type. The only way to guess at its type is by checking GetLength()'s return type.

• The Append(), Prepend() and Delete() member functions all take their arguments by copy just like ListNode's old constructor. Consider similar fixes without forgetting to adapt the exception specification according to the operations you do.

• Your data members comply with the requirements needed to mark your default constructor as constexpr and as noexcept.

• Printing should not be a member function. Instead, provide operator






• As Loki Astari mentioned, consider using sentinel nodes in order to avoid having to check for nullptr values.






• Provide an exception specification for non-throwing functions such as GetLength()`.

StackExchange Code Review Q#143021, answer score: 6