trjhtr

After watching Herb Sutter describe single-linked lists in terms of unique_ptr I decided to implement my own. In particular I want to know if my move semantics are correct and if any unnecessary copies are made. It passes my simple cases with int and I plan to add insertion/deleting later.

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node 
public:
 Node(const Type& data) : data data 
 std::unique_ptr<Node<Type>> next = nullptr;
 Type data;
;

template<typename Type>
class LinkedList 
public:
 void push_back(const Type& data) 
 if (!head) 
 head = std::make_unique<Node<Type>>(data);
 return;
 

 Node<Type>* end = head.get();

 while (end->next) 
 end = end->next.get();
 

 end->next = std::make_unique<Node<Type>>(data);
 

 Type pop_back() 
 if (!head) 
 throw;
 

 Node<Type>* end = head.get();
 Node<Type>* previous = nullptr;

 while (end->next) 
 previous = end;
 end = end->next.get();
 

 const Type data = end->data;

 if (previous) 
 previous->next = nullptr;
 

 return data;
 

 void push_front(const Type& data) 
 if (!head) 
 head = std::make_unique<Node<Type>>(data);
 return;
 

 std::unique_ptr<Node<Type>> new_head = std::make_unique<Node<Type>>(data);
 new_head->next = std::move(head);
 head = std::move(new_head);
 

 Type pop_front() 
 if (!head) 
 throw;
 

 const Type data = head->data;
 head = std::move(head->next);
 return data;
 

 std::size_t size() const 
 if (!head) 
 return 0;
 

 std::size_t size = 1;
 Node<Type>* traverse = head.get();

 while (traverse->next) 
 traverse = traverse->next.get();
 size++;
 

 return size;
 

 /* iterative destroy to avoid recursive deletes */
 void destroy() 
 if (!head) 
 return;
 

 while (head->next) 
 head = std::move(head->next);
 

 head = nullptr;
 

private:
 std::unique_ptr<Node<Type>> head = nullptr;
;

Edit: With Deduplicator's response I ended up with this code

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node 
public:
 Node(const Type& data) : data data 
 std::unique_ptr<Node<Type>> next = nullptr;
 Type data;
;

template<typename Type>
class LinkedList 
public:
 void push_back(const Type& data) 
 auto end = &head;

 while (*end) 
 end = &(*end)->next;
 

 *end = std::make_unique<Node<Type>>(data);
 

 Type pop_back() 
 auto end = &head;
 auto previous = &head;

 while (*end) 
 previous = end;
 end = &(*end)->next;
 

 const Type data = (*previous)->data;
 *previous = nullptr;
 return data;
 

 void push_front(const Type& data) 
 auto new_head = std::make_unique<Node<Type>>(data);
 new_head->next = std::move(head);
 head = std::move(new_head);
 

 Type pop_front() 
 const Type data = head->data;
 head = std::move(head->next);
 return data;
 

 ~LinkedList() 
 auto end = &head;

 while (*end) 
 *end = std::move((*end)->next);
 
 

private:
 std::unique_ptr<Node<Type>> head = nullptr;
;

Almost always auto. Only write down the specific type when you have to, it's shorter, clearer, and less error-prone.

You currently handle an empty list as a special case. Don't, it's neither efficient nor elegant.

Instead, use a pointer to pointer, and everything is simplified. As an example:

void push_back(const Type& data) 
 auto p = &head;
 while (*p)
 p = &(*p)->next;
 *p = std::make_unique<Node<Type>>(data);

Good of you to avoid recursive descent in the dtor. But, you know that's not spelled destroy()?

While this is somewhat unrelated to what you want from this review, here is something I don't like:

std::size_t size() const 
 if (!head) 
 return 0;
 

 std::size_t size = 1;
 Node<Type>* traverse = head.get();

 while (traverse->next) 
 traverse = traverse->next.get();
 size++;
 

 return size;

This function is currently very complex, in terms of readability and performance. If the client had a loop that repeatedly needed the size of the linked list after modifying it, this would slow the code down. Instead, I suggest that you keep a private member variable called size in your class. Every time you add an element to your list, you increment this variable. Similarly, you decrement this variable when you delete something. Thus this function would then become O(1):

std::size_t size() const 
 return size;

This matches the behavior of the STL. However, adding such a member could bloat your class, as @Frank pointed out. If you want to really follow the STL, then I would remove the size function altogether, as std::forward_list does for these reasons.