So I have tried to implement a doubly-linked list in C++. My implementation includes some basic methods (although I know there could be many more), an iterator class and an overwritten << operator. I know the code is quite big, but I would really appreciate any comments on functionality, style or anything else you think could be better.
Note: I know many people say using smart pointers is always a good idea, but I used raw pointers here, for training purposes and because I think using them in situations like this is not really wrong. Feel free to state your opinion on this, too.
Cdoubly_linked_list.h:
#ifndef CDOUBLY_LINKED_LIST
#define CDOUBLY_LINKED_LIST
#include <cstdint>
namespace list
{
template<class T>
class Cdoubly_linked_list
{
struct Node
{
Node(T _value, Node* _prev, Node* _next) : value{ _value }, prev{ _prev }, next{ _next }{};
T value;
Node* prev;
Node* next;
};
public:
Cdoubly_linked_list() : head{ nullptr }, tail{ nullptr }{}; // standard constructor
~Cdoubly_linked_list() { clear(); }; // destructor to call clear()
Cdoubly_linked_list(const Cdoubly_linked_list& other) : head{ nullptr }, tail{ nullptr } // copy constructor
{
Node* tmp = other.head;
while (tmp != nullptr)
{
push_back(tmp->value);
tmp = tmp->next;
}
}
Cdoubly_linked_list& operator=(const Cdoubly_linked_list& other) // copy assignment operator
{
if (*this != other)
{
Node* tmp = other.head;
while (tmp != nullptr)
{
push_back(tmp->value);
tmp = tmp->next;
}
}
return *this;
}
Cdoubly_linked_list(Cdoubly_linked_list&& other) = default; // move constructor
Cdoubly_linked_list& operator=(Cdoubly_linked_list&& other) = default; // move assignment operator
bool is_empty() // return true if list is empty
{
if (head == nullptr) return true;
return false;
}
void clear() // clears list and free's all memory
{
Node* tmp = head;
while (tmp != nullptr)
{
head = tmp;
tmp = tmp->next;
delete head;
}
head = tail = nullptr;
}
bool remove(T val) // delete first matching element by value and return true if succesfull
{
if (val == head->value) { pop_front(); return true; }
Node* tmp = head->next;
while (tmp != tail)
{
if (tmp->value == val)
{
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
delete tmp;
return true;
}
tmp = tmp->next;
}
if (val == tail->value) { pop_back(); return true; }
return false;
}
void pop_front() // pop first element
{
if (head != nullptr)
{
Node* tmp = head;
head = head->next;
delete tmp;
if (head == nullptr) tail = nullptr;
}
}
void pop_back() // pop last element
{
if (tail == head) pop_front();
tail = tail->prev;
delete tail->next;
tail->next = nullptr;
}
void push_front(T val) // insert element at front
{
if (head != nullptr)
{
head->prev = new Node(val, nullptr, head);
head = head->prev;
}
else
{
head = new Node(val, nullptr, nullptr);
tail = head;
}
}
void push_back(T val) // insert element at back
{
if (head != nullptr)
{
tail->next = new Node(val, tail, nullptr);
tail = tail->next;
}
else
{
head = new Node(val, nullptr, nullptr);
tail = head;
}
}
class it : private std::iterator<std::bidirectional_iterator_tag, T> // bidirectional iterator
{
public:
it(Node* _ptr = nullptr) : ptr{ _ptr } {}; // standard constructor
it(const it& other) = default; // copy constructor
it(it&& other) = default; // move constructor
it& operator=(const it& other) = default; // copy assignment operator
it& operator=(it&& other) = default; // move assignment operator
T& operator*() const // dereference operator
{
return ptr->value;
}
it& operator++() // pre-increment operator
{
ptr = ptr->next;
return *this;
}
it operator++(int) // post-increment operator
{
it copy(ptr);
ptr = ptr->next;
return copy;
}
it& operator--() // pre-decrement operator
{
ptr = ptr->prev;
return *this;
}
it operator--(int) // post-decrement operator
{
it copy(ptr);
ptr = ptr->prev;
return copy;
}
bool operator==(const it& other) // equality operator
{
return other.ptr == ptr;
}
bool operator!=(const it& other) // inequality operator
{
return other.ptr != ptr;
}
private:
Node* ptr;
};
it begin() const // get begin iterator
{
return it(head);
}
it end() const // get end iterator
{
return it(tail);
}
friend std::ostream& operator<<(std::ostream& os, Cdoubly_linked_list& list) // overload << operator
{
Node* tmp = list.head;
while (tmp != nullptr)
{
os << tmp->value << std::endl;
tmp = tmp->next;
}
return os;
}
private:
Node* head;
Node* tail;
};
}
#endif
