A doubly linked list implementation using C++ smart pointers

Question

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 <iostream>
#include <memory>
template <typename T>
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<ListNode> next;
 std::weak_ptr<ListNode> prev;
 ListNode(T data) : data(data) {}
 };
 int length;
 std::shared_ptr<ListNode> head;
 std::shared_ptr<ListNode> tail;
 void Delete(std::shared_ptr<ListNode> ptr);
};
template <typename T>
LinkedList<T>::LinkedList()
 : length(0) {}
template <typename T>
int LinkedList<T>::GetLength() const {
 return length;
}
template <typename T>
void LinkedList<T>::Print() const {
 std::shared_ptr<ListNode> h(head);
 std::cout << "List (length = " << length << "): ";
 while (h) {
 std::cout << h->data << " ";
 h = h->next;
 }
 std::cout << std::endl;
}
template <typename T>
void LinkedList<T>::Append(T data) {
 std::shared_ptr<ListNode> node_ptr(std::make_shared<ListNode>(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 <typename T>
void LinkedList<T>::Prepend(T data) {
 std::shared_ptr<ListNode> node_ptr(std::make_shared<ListNode>(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 <typename T>
bool LinkedList<T>::Delete(T data) {
 std::shared_ptr<ListNode> ptr = head;
 while (ptr) {
 if (ptr->data == data) {
 Delete(ptr);
 return true;
 }
 ptr = ptr->next;
 }
 return false;
}
template <typename T>
void LinkedList<T>::Delete(std::shared_ptr<ListNode> ptr) {
 auto shared_prev = (ptr->prev).lock();
 if (head == ptr) {
 head = ptr->next;
 }
 if (tail == ptr) {
 tail = shared_prev;
 }
 if (shared_prev) {
 shared_prev->next = ptr->next;
 }
 if (ptr->next) {
 ptr->next->prev = ptr->prev;
 }
 length--;
}

• Loki Astari: There are two main techniques for memory management. Smart Pointers and Containers. You usually don't implement the containers in terms of Smart Pointers the whole point is that the Container is doing its own resource management.
• Loki Astari: I would use a list with a sentinel. They remove the need to check for NULL everywhere.
• j4nu5: @LokiAstari Regarding your first comment: " You usually don't implement the containers in terms of Smart Pointers". If I am the guy implementing the container (e.g. STL list), I would have to use dynamic memory allocation right? And smart pointers are the safest way of doing it? Or am I missing something?
• Loki Astari: Of course you can use Smart Pointers. But Why? The job of the container is Memory management (that's its job). Also by using the Smart Pointer route your implementation of the container will "probably" be suboptimal (go back to the list. Resource release will be recursive using a Smart Pointer while the more optimal technique would be a loop).

Answer 1

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 <type_traits> // 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<T>::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<T>::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<T>

1. 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.
2. 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.
3. Your data members comply with the requirements needed to mark your default constructor as constexpr and as noexcept.
4. Printing should not be a member function. Instead, provide operator<< as a free function.
5. As Loki Astari mentioned, consider using sentinel nodes in order to avoid having to check for nullptr values.
6. Provide an exception specification for non-throwing functions such as GetLength().

Answer 2

#include <iostream>

Avoid #include <iostream> in library files. The C++ standard requires static construction of the standard streams (std::cin, std::cout, std::cerr, and the wide versions). If you want to allow functions to be streamable, consider #include <iosfwd> and reference streams through parameters.

This also means you should removing the debugging prints that litter your code. Consider using a logger that can be enabled at compile time with a switch or learn to use a debugger.

---

template <typename T>
class LinkedList {
 // methods/members
};

What good is a container if it cannot be used with existing libraries? The C++ standard outlines container requirements. You should implement any missing types, methods, and operators.

---

void Append(T data);

Pass-by-value is great when copying data is a cheap operation. It's terrible when data is an expensive copy. Prefer to pass templated variables of unknown cost by const&.

---

std::shared_ptr<ListNode> head;
std::shared_ptr<ListNode> tail;

Smart pointers are fine for ownership, but do you really need a std::shared_ptr to represent its structure? std::unique_ptr coupled with a non-owning pointer (raw pointer, C++17s std::observer_ptr) can represent the ownership abstraction for a doubly linked list.

Be aware of how smart pointers behave with the compiler generated operations. With std::shared_ptr, the destructor recurses \$O(n)\,ドル which could consume the entire stack.

{
 LinkedList<int> list;
 while (list.size() < size_to_overflow_stack) {
 list.append(0);
 }
} // Boom!

The copy operation shallow copies the std::shared_ptr rather than deep copying the data.

LinkedList<int> l1;
l1.Append(0); // Populate list 1
auto l2 = l1; // Copy list 1
l2.Append(0); // Populate list 2 with more data
l1.Print(); // List (length = 1): 0 0 !!!!!
l2.Print(); // List (length = 2): 0 0

If you define any of the five special member functions for classes (destructor, copy/move constructor, copy/move assignment), the compiler is not guaranteed to generate them for you, so you must define them yourself.

---

template <typename T>
class LinkedList {
 int length;
public:
 LinkedList() : length(0) {}
 // append, delete, etc
}

When defining members with constants by default, prefer default member initializers over the other forms of initialization.

You may omit explicitly defining the compiler generated constructor if you have no other constructor defined.

template <typename T>
class LinkedList {
 int length{}; // Member is directly default initialized to 0
public:
 // No other ctors, so no need to explicitly define defaulted ctor.
 // LinkedList() = default;
 // append, delete, etc
}