Doubly linked list std::unique_ptr template class implementation

Question

Inspired by the talk of Herb Sutter in CppCon2016, I decided to make a doubly linked list using templates, smart pointers, and raw pointers (for back-pointers, having a cycle of std::unique_ptrs would be a bug).

The following proof-of-concept implementation compiles and works properly.
I would love to hear your suggestions / improvements about the entire header and your design approach.

Below you can find the header and a small test main.

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <memory>
#include <initializer_list>
namespace DLL {
 template <typename T> class LinkedList{
 private:
 struct ListNode{
 std::unique_ptr<ListNode> next; //2 uniq_ptr can't point to one another.
 ListNode* prev = nullptr; //weakptr needs to be cast back to a shared_ptr to check its state.
 T data{}; //Initialize empty;
 ListNode(const T& element){
 this->data = element;
 }
 };
 public:
 std::unique_ptr<ListNode> head;
 ListNode* tail = nullptr;
 LinkedList(){}
 ~LinkedList(){}
 void append(const T& element){
 ListNode* curr = nullptr;
 if (head.get() == nullptr){ //If list is empty.
 head = std::make_unique<ListNode>(element);
 }
 else if(head.get() -> next.get() == nullptr){ //If list has one element.
 head.get() -> next = std::make_unique<ListNode>(element);
 curr = head.get() -> next.get(); //Sets raw pointer to the first element.
 curr -> prev = head.get();
 tail = curr;
 }
 else{
 tail -> next = std::make_unique<ListNode>(element);
 curr = tail -> next.get(); //Sets raw pointer to the last element.
 curr -> prev = tail;
 tail = curr;// The new last element is the tail.
 }
 }
 int remove(const T& element){ 
 ListNode* curr = nullptr;
 if (head.get() == nullptr){ //If list is empty.
 return -1; //Error: Can't remove from empty list.
 }
 //List has one or more elements.
 curr = head.get();
 while(curr != nullptr){
 if(curr -> data == element){ //Found element.
 if(curr -> prev == nullptr){ //it's head
 head = std::move(curr -> next); //Head now points to the next element.
 if (head) {
 head->prev = nullptr;
 }
 //New head's previous element points to nothing, making it a true head element.
 }
 else if(curr -> next.get() == nullptr){ //it's tail.
 tail = curr -> prev; //Reference the previous element.
 tail -> next.reset(); //Destroy the old tail element.
 if(head.get() == tail){
 tail = nullptr; //tail and head should not be the same.
 } //List contains one element.
 }
 else{//it's intermediate.
 //The next node should point to the previous one
 curr -> next -> prev = curr -> prev;
 curr -> prev -> next = std::move(curr -> next);
 //The prev node now points to the next one of current.
 }
 return 1; //Element found in list.
 }
 curr = curr -> next.get(); //Traverse the next element.
 }
 return 0; //Element not found in list.
 }
 void print() {
 ListNode* curr = head.get(); //Start from the start of the list.
 std::cout << "[ ";
 while (curr != nullptr) {
 std::cout << curr -> data << " ";
 curr = curr -> next.get();
 }
 std::cout << "]" << std::endl;
 }
 };
}
#endif

main.cpp

#include "LinkedList.h"
int main() { //Temporary Test Main will be split from the implementation file in the future
 DLL::LinkedList <int> list; //Create an empty list
 list.append(1);
 list.append(2);
 list.append(3);
 list.append(4);
 list.append(5);
 list.print();
 list.remove(5);
 list.print();
 list.remove(1);
 list.print();
 list.remove(3);
 list.print();
 list.remove(2);
 list.print();
 list.remove(4);
 list.print();
 return 0;
}

I compiled with g++: g++ -std=c++14 main.cpp -o out and with the VS2015 compiler.
The C++14 flag is needed for the std::make_unique call.

• Vogel612: you'll want to ask a follow up question to make sure you're not invalidating any answers that have been posted already.
• hoffmale: @Vogel612: At that time there were no answers to be invalidated (yet). And even the one that exists by now didn't mention the corrected issue.
• hoffmale: @hitter: For the future, you might want to wait a bit (e.g. 24 hours) before accepting an answer, as it takes some time to write a good review and an already accepted answer discourages others who might write a better one ;)
• Deduplicator: Seems the part finally killing this idea might be the Iterator-Invalidation-rules.
• solid.py: @Deduplicator The idea is fully implemented now with more methods and most of hoffmale recommendations. It's not production-ready (never I attempted it to be), it was just a little expirement for me to practice some of smart pointer, template stuff I learned.

Answer 1

Implementation issues

• There's no way to store a move-only type (or rather any non-copyable type) in the LinkedList (e.g. this means you cannot have a DLL::LinkedList<std::unique_ptr<int>>). Maybe provide overloads that accept a T&&, and/or add an emplace member function that constructs a T in place?

• Prefer using a member initializer list over assigning inside the constructor body. This allows ListNode::data to be copy-constructed directly, instead of being default-constructed and then copy-assigned. Also, it might provide better optimization opportunities and better exception guarantees (if something inside the constructor throws, already constructed members get properly destructed).

• ListNodes constructor(s) can be marked conditionally noexcept.

• Also, it might be more convenient to allow setting the next and prev pointers of a ListNode directly inside the ListNode constructor(s) (see later for an example).

An ListNode implementation supporting all above mentioned points might look something like this:

struct ListNode {
 std::unique_ptr<ListNode> next;
 ListNode* prev;
 T data;
 ListNode(std::unique_ptr<ListNode> next, ListNode* prev, const T& element) noexcept(std::is_nothrow_copy_constructible_v<T>)
 : next{std::move(next)}, prev{prev}, data{element} {}
 ListNode(std::unique_ptr<ListNode> next, ListNode* prev, T&& elemente) noexcept(std::is_nothrow_move_constructible_v<T>)
 : next{std::move(next)}, prev{prev}, data{std::move(element) {}
 template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args&&...>>
 ListNode(std::unique_ptr<ListNode> next, ListNode* prev, Args&&... args) noexcept(std::is_nothrow_constructible_v<T, Args&&...>)
 : next{std::move(next)}, prev{prev}, data{std::forward<Args>(args)...} {}
};

• LinkedLists default constructor could be = default, as no actual work is done.

• ~LinkedList() {} is problematic: Yes, it does clean up memory, but only until it hits the call stack limits due to recursion. Just try letting a LinkedList with a million (or so) elements destruct (e.g. by letting it fall out of scope).

  You might want to rewatch minutes 16:00 to around 26:00 in the video, Herb Sutter explains this problem far better than I could in this limited space.

  Since an iterative destructor implementation was requested:

  ~LinkedList() noexcept {
   while(head) head = std::move(head->next);
  }
  

• Rule of Five violation: A custom destructor is provided, but no copy-constructor, copy assignment operator, move constructor and move assignment operator.

  Move assignment and move construction are pretty easy to implement (actually, they can be = default).

  However, copy assignment and copy construction aren't quite as easy: They require T to be copy-constructible. If copying a LinkedList isn't important, you could = delete those two special functions.

• LinkedList::append(const T&) issues

  • A lot of the calls to std::unique_ptr::get are unnecessary. The only necessary ones are curr = head->next.get();, curr->prev = head.get(); and curr = tail->next.get();

  • The whole else if branch could be remove if tail would be allowed to point to the same node as head (in a LinkedList of size 1).

  • The whole pointer moving business can be simplified using the constructors of ListNode above that take those pointer values.

  • The const T& parameter only works if T itself is copy constructible. This can be checked using type traits, and the function be made unavailable (using SFINAE) if copy-construction is not supported by T.

  A simplified and cleaned up version could look something like this:

  std::enable_if_t<std::is_copy_constructible<T>::value> append(const T& element) {
   if(!head) {
   head = std::make_unique<ListNode>(nullptr, nullptr, element);
   tail = head.get();
   } else {
   tail->next = std::make_unique<ListNode>(nullptr, tail, element);
   tail = tail->next.get();
   }
  }
  

• LinkedList::remove(const T&) issues:

  • Is there a specific reason that removing a value from an empty LinkedList returns a different result than removing a non-existent value form a non-empty LinkedList?

  • Speaking about return values: Is it necessary to return one at all?

  • The whole logic of remove could be split into two helper functions: 1) Finding the nodes whose value matches and 2) removing a specific node.

    Finding a node (or removing a specific node) are operations that will likely be reused in the future anyways, so this will likely help implementing additional features.

  • Again, like in append, some of the removal logic could be simplified if tail were allowed to point to the same node as head.

  Example fixup:

  private:
   ListNode* find_node(const T& value, ListNode* current) const {
   while(current) {
   if(current->data == value) return current;
   current = current->next.get();
   }
   return nullptr;
   }
   void remove_node(ListNode* node) {
   if(node->next) {
   node->next->prev = node->prev;
   } else {
   tail = node->prev;
   }
   // the assignments below reset the original owner, thus node will be dangling afterwards!
   if(node->prev) {
   node->prev->next = std::move(node->next);
   } else {
   head = std::move(node->next);
   }
   }
  public:
   void remove(const T& value) {
   for(auto node = find_node(head.get()); node; node = find_node(value, node)) {
   auto temp = node;
   node = node->next.get();
   remove_node(temp);
   }
   }
  

  Much more readable, and easier to reason about, isn't it?

• LinkedList::print: While this function might be nice for debugging, it doesn't seem to be in the general scope of the LinkedList class: If there is any way of iteration over the nodes, the print function can easily be implemented outside of LinkedList (if/where needed).

  If there really is a need for LinkedList to support text output, try to implement friend std::ostream& operator<<(std::ostream&, const DLL::LinkedList&) instead.

Naming

The common C++ standard library naming conventions would suggest push_back instead of append.

Design

A lot of common linked list operations are missing:

• push_front
• emplace_back

• emplace_front

• insert (*)

• emplace (*)
• erase (*)

• find (*)

• Iterators

(*) These functions might be easier to implement (without leaking ListNode*s) or perform better if using iterators.

• Deduplicator: 1. You know the templated ctor for ListNode makes both non-templated ones you added superfluous? 2. Anyway, removing them all would allow for Aggregate-initialization. No need for the boilerplate. 3. It Looks like a POC, so probably only a small part of the interface exists yet.
• hoffmale: @Deduplicator: Correct on all counts. Re #3: I mostly provided those design hints in case this gets expanded further.
• hoffmale: @hitter: Just did.
• hoffmale: @Deduplicator: Wait a sec, Re #2: That would prevent you from using std::make_unique, which the templated constructor still allows.
• Deduplicator: Hm, why? Anyway, how bout those iterators?

Answer 2

Well, there's a reason I wouldn't ever use a smart-pointer which isn't a shared-pointer or self-relative as base for a doubly-linked-list:

Most of the time, one has to work around the smart-pointer to get things done efficiently, or with the right semantics at all. Some examples from your code:

1. Your list-destructor is deeply recursive, needing \$O(n)\$ stack-space. An iterative version would only need a miniscule fixed amount of stack-space and be faster too. That can be fixed without going to different pointers, but you are fighting against them.
2. You must handle an empty list, specifically inserting or removing the first node, as a special case. Special-casing leads to repetition and loss of efficiency.
3. You will have difficulties creating a standard iterator-interface for your list: Iterators to nodes are fine, but what about the end-iterator? The container-requirements say that all iterators to elements have to stay valid after container-swap (std::array obviously has an exception).

Base your list-class and its nodes on something like the following instead, and do your memory-management manually or with shared-pointers when building that basic abstraction.

struct node_base {
 node_base *next, *prev;
};
template <class T>
class linked_list {
 struct node { node_base links; T data; };
 node_base links { &links, &links };
 void fix_links() noexcept {
 if (links.next != links.prev)
 links.next->prev = links.prev->next = &links;
 else
 links.next = links.prev = &links;
 }
public:
 linked_list() = default;
 ~linked_list() {
 while (auto p = links.next; p != &links)
 delete (node*)std::exchange(p, p->next);
 }
...

Printing the list should be done by a free non-friend function using the now easily implemented iterator-interface. And it should probably be done in template <class T> std::ostream& operator<<(std::ostream& os, linked_list<T> const& ll).

Naturally, your proof-of-concept still misses most of its interface. Still, those you have should all follow the standard-library as closely as reasonable, in order to take advantage of all the template-magic and to follow the rule of least surprise.

• hoffmale: std::shared_ptr has a lot of overhead that isn't needed for a simple doubly linked list. The only exception I could see if there is a special requirement for iterators to remain valid even when the lifetime of the linked list already ended (which is very rare IME). Also, creating an bidirectional iterator over a doubly linked list is nearly trivial.
• Deduplicator: @hoffmale Indubitably using shared_ptr's would be rare, but they are one of the two types of smart-pointers relevant at all. Regarding the iterators, I would love seeing you demonstrate ones as good as std::list for the OPs definitions.