trjhtr

This is a working but very simple doubly linked list. I wrote it to get more familiar with certain language concepts and because I've never made one in C++. (For convenience reasons this is not split into separate files for declaration/definition)

Things I'm mainly interested in:

• Is the overall implementation correct?




• Are the various constructors/operators implemented correctly? I'm still not very sure about these so this is an important concern.




• How is const usage?




• Where, if possible, can constexpr be used to make this more robust?




• Is this well written/easy to read? What could be improved to make it better in that regard?

and anything else you notice.

Code:

#include <iostream>
#include <cassert>
#include <initializer_list>
#include <utility>

template<typename T>
class DoublyLinkedList 
public:
 DoublyLinkedList()
 : headnullptr
 , tailnullptr
 , list_size0
 

 DoublyLinkedList(std::initializer_list<T> init_list)
 : DoublyLinkedList
 
 for (auto const& value : init_list) 
 push_back(value);
 
 

 DoublyLinkedList(DoublyLinkedList const& rhs)
 : DoublyLinkedList
 
 Node* node = rhs.head;
 while (node) 
 push_back(node->data);
 node = node->next;
 
 

 DoublyLinkedList(DoublyLinkedList&& rhs) noexcept
 : headrhs.head
 , tailrhs.tail
 , list_sizerhs.list_size
 
 rhs.head = nullptr;
 rhs.tail = nullptr;
 rhs.list_size = 0;
 

 ~DoublyLinkedList() noexcept 
 clear();
 

 DoublyLinkedList& operator=(DoublyLinkedList const& rhs) 
 DoublyLinkedList tmp(rhs);
 *this = std::move(tmp);
 return *this;
 

 DoublyLinkedList& operator=(DoublyLinkedList&& rhs) noexcept 
 if (this == &rhs) 
 return *this;
 

 clear();

 head = rhs.head;
 tail = rhs.tail;
 list_size = rhs.list_size;

 rhs.head = nullptr;
 rhs.tail = nullptr;
 rhs.list_size = 0;

 return *this;
 

 bool is_empty() const 
 return head == nullptr;
 

 int const& size() const 
 return list_size;
 

 void clear() 
 Node* node = head;
 while (node) 
 Node* delete_this = node;
 node = node->next;
 delete delete_this;
 

 head = nullptr;
 tail = nullptr;

 list_size = 0;
 

 void push_front(T const& value) 
 if (!head) 
 head = new Nodenullptr, nullptr, value;
 tail = head;
 
 else 
 head->prev = new Nodehead, nullptr, value;
 head = head->prev;
 

 ++list_size;
 

 void push_back(T const& value) 
 if (!tail) 
 push_front(value);
 return;
 

 tail->next = new Nodenullptr, tail, value;
 tail = tail->next;

 ++list_size;
 

 void insert_after(int const& position, T const& value) 
 int i = 0;
 Node* node = head;
 while (node) 
 if (i++ == position) 
 Node* new_node = new Nodenode->next, node, value;
 new_node->next->prev = new_node;
 node->next = new_node;
 ++list_size;
 return;
 
 node = node->next;
 
 

 void erase(int const& position) 
 if (position <= 0) 
 pop_front();
 return;
 

 if (position >= list_size - 1) 
 pop_back();
 return;
 

 int i = 1;
 Node* node = head->next;
 while (node) 
 if (i++ == position) 
 node->prev->next = node->next;
 node->next->prev = node->prev;
 delete node;
 --list_size;
 return;
 
 node = node->next;
 
 

 void pop_front() 
 if (head->next) 
 Node* node = head->next;
 delete head;
 head = node;
 head->prev = nullptr;
 
 else 
 delete head;
 head = nullptr;
 tail = nullptr;
 
 --list_size;
 

 void pop_back() 
 if (tail->prev) 
 Node* node = tail->prev;
 delete tail;
 tail = node;
 tail->next = nullptr;
 
 else 
 delete tail;
 tail = nullptr;
 head = nullptr;
 
 --list_size;
 

 T& front() const 
 return head->data;
 

 T& back() const 
 return tail->data;
 

 int find_first_of(int const& start, T const& value) const 

private:
 struct Node 
 Node(Node* n, Node* p, T d)
 : nextn
 , prevp
 , datad
 

 Node* next;
 Node* prev;
 T data;
 ;

 Node* head;
 Node* tail;
 int list_size;
;

int main() 
 DoublyLinkedList<int> dll1, 2, 3;
 assert(dll.size() == 3);

 assert(dll.find_first_of(0, 2) == 1);

 dll.erase(1);
 assert(dll.size() == 2);

 dll.pop_front();
 assert(dll.size() == 1);

 dll.pop_back();
 assert(dll.size() == 0);
 assert(dll.is_empty());

 dll.push_back(1);
 assert(dll.size() == 1);
 assert(!dll.is_empty());

 dll.push_back(1);
 assert(dll.size() == 2);

 dll.insert_after(0, 3);
 assert(dll.find_first_of(0, 3) == 1);

• 
  

  push_front can be streamlined. The new node will become a head no matter what, and its next will point the old head no matter what, so consider

  
  
  

  void push_front(T const& value) 
   node = new Nodehead, nullptr, value;
   if (!head) 
   tail = node;
   else 
   head->prev = node;
   
   head = node;
   ++list_size;
  
  

  
  
  

  (Same applies to push_back).

  
  


• 
  

  Same technique applies to pop_front and pop_back, e.g.:

  
  
  

  void pop_front()
  
   Node * node = head;
   head = head->next;
   delete node;
   if (head) 
   head->prev = nullptr;
   else 
   tail = nullptr;
   
   --list_size;
  
  

  
  



• I don't see the value of push_back calling push_front.




• OTOH, clear should call pop_front, just like constructors call push_back.




• Using int as a position is dangerous and limiting. Consider size_t.




• insert_after, erase, and find_first_of would benefit from the private Node * at(size_t position) utility method.




• The list sorely misses iterators. Once they are implemented, an entire <algorithm> library is to your service for free.




• I don't follow why an int parameter is passed by a reference.