New doubly linked list

ddl.cpp

#include <iostream>
#include <iterator>
#include <algorithm>
#include <initializer_list>
 
template<typename T>
struct LinkedList;
 
template<typename T>
struct node
{
    node(T const& data, node* prev = nullptr, node* next = nullptr)
        : data(data)
        , prev(prev)
        , next(next)
    { }
    
    friend struct LinkedList<T>;
private:
    T data;
    node* prev;
    node* next;
};
 
template<typename T>
std::ostream& operator<<(std::ostream&, LinkedList<T> const&);
 
template<typename T>
struct LinkedList
{
    class iterator;
public:
    LinkedList() noexcept = default;
    ~LinkedList() noexcept(noexcept(std::declval<LinkedList<T>>().clear()));
    LinkedList(std::initializer_list<T>) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())));
    LinkedList(LinkedList const&) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())));
    LinkedList& operator=(LinkedList const&) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())));
    void clear();
    void push_back(T const&) noexcept(noexcept(T()));
    void push_front(T const&) noexcept(noexcept(T()));
    void insertBefore(T const&, T const&) noexcept(noexcept(T()));
    void insertAfter(T const&, T const&) noexcept(noexcept(T()));
    void remove(T const&) noexcept;
    iterator find(T const& value) noexcept;
    std::size_t size() const noexcept;
    
    iterator begin() const noexcept(noexcept(iterator(std::declval<node<T>*>())));
    iterator end() const noexcept(noexcept(iterator()));
    
    T& front() noexcept { return head->data; }
    T& back()  noexcept { return tail->data; }
    
    friend std::ostream& operator<<<T>(std::ostream&, LinkedList<T> const&);
private:
    node<T>* head      = nullptr;
    node<T>* tail      = nullptr;
    mutable std::size_t m_size = 0;
private:
    void display(std::ostream&) const;
    bool deleteNode(node<T>**) noexcept;
    void dec_size() const noexcept { if (m_size) --m_size; }
    void inc_size() const noexcept { ++m_size; }
};
 
template<typename T>
LinkedList<T>::LinkedList(std::initializer_list<T> list) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())))
{
    for (auto& c : list)
        push_back(c);
}
 
template<typename T>
LinkedList<T>::LinkedList(LinkedList<T> const& other) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())))
{
    for (node<T>* curr = other.head; curr != nullptr; curr = curr->next)
        push_back(curr->data);
}
 
template<typename T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T> const& other) noexcept(noexcept(std::declval<LinkedList<T>>().push_back(std::declval<T>())))
{
    clear();
    for (node<T>* curr = other.head; curr != nullptr; curr = curr->next)
        push_back(curr->data);
}
 
template<typename T>
LinkedList<T>::~LinkedList() noexcept(noexcept(std::declval<LinkedList<T>>().clear()))
{
    clear();
}
 
template<typename T>
void LinkedList<T>::push_back(T const& value) noexcept(noexcept(T()))
{
    node<T>* insert = new node<T>(value, tail);
           
    if (!head)
        head = insert;
    else
        tail->next = insert;
    tail = insert;
    inc_size();
}
 
template<typename T>
void LinkedList<T>::push_front(T const& value) noexcept(noexcept(T()))
{
    head = new node<T>(value, nullptr, head);
    inc_size();
}
 
template<typename T>
void LinkedList<T>::insertBefore(T const& pos, T const& data) noexcept(noexcept(T()))
{
    node<T>* curr = head;
    while (curr && curr->data != pos)
        curr = curr->next;
    
    if (curr)
    {
        node<T>* newNode = new node<T>(data, curr->prev, curr);
        if (curr->prev)
            curr->prev->next = newNode;
        else
            head = newNode;
        inc_size();
    }
}
 
template<typename T>
void LinkedList<T>::insertAfter(T const& pos, T const& data) noexcept(noexcept(T()))
{
    node<T>* curr = head;
    while (curr && curr->data != pos)
        curr = curr->next;
    
    if (curr)
    {
        node<T>* newNode = new node<T>(data, curr, curr->next);
        curr->next = newNode;
        inc_size();
    }
}
 
template<typename T>
void LinkedList<T>::display(std::ostream& os) const
{
    for (node<T>* n = head; n != nullptr; n = n->next)
        os << n->data << " ";
    os << '\n';
}
 
template<typename T>
void LinkedList<T>::clear()
{
    while (head)
    {
        node<T>* next = head->next;
        delete head;
        head = next;
        dec_size();
    }
}
 
template<typename T>
void LinkedList<T>::remove(T const& value) noexcept
{
    node<T>** curr = &head;
    while (*curr && (*curr)->data != value)
        curr = &(*curr)->next;
        
    if (deleteNode(curr))
        dec_size();
}
 
template<typename T>
bool LinkedList<T>::deleteNode(node<T>** n) noexcept
{
    if (*n)
    {
        auto prev = &(*n)->prev,
             next = &(*n)->next;
        delete *n;
        if (*prev)
            (*prev)->next = *next;
        else
            *n = *next;
        return true;
    }
    return false;
}

template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::begin() const noexcept(noexcept(iterator(std::declval<node<T>*>())))
{ return head; }
 
template<typename T>
typename LinkedList<T>::iterator LinkedList<T>::end() const noexcept(noexcept(iterator()))
{ return nullptr; }
 
template<typename T>
std::size_t LinkedList<T>::size() const noexcept
{ return m_size; }
 
template<typename T>
std::ostream& operator<<(std::ostream& os, LinkedList<T> const& list)
{
    list.display(os);
    return os;
}
 
template<typename T>
class LinkedList<T>::iterator
    : public std::iterator<
        std::bidirectional_iterator_tag,
        T
    >
{
public:
    iterator(node<T>* pos = nullptr)
        : m_pos(pos)
    { }
    
    iterator operator++(int)
    {
        iterator copy(*this);
        ++*this;
        return *this;
    }
    
    iterator& operator++()
    {
        m_pos = m_pos->next;
        return *this;
    }
    
    iterator operator--(int)
    {
        iterator copy(*this);
        --*this;
        return copy;
    }
    
    iterator& operator--()
    {
        m_pos = m_pos->prev;
        return *this;
    }
    
    T& operator*() const
    {
        return m_pos->data;
    }
    
    friend bool operator!=(iterator const& lhs, iterator const& rhs)
    { return lhs.m_pos != rhs.m_pos; }
    
    friend bool operator==(iterator const& lhs, iterator const& rhs)
    { return !(lhs == rhs); }
private:
    node<T>* m_pos;
};
 
int main()
{
    LinkedList<int> list{5, 35, 2, 78, 21, 2, 3};
    auto i = std::find(list.begin(), list.end(), 21);
    if (i != list.end())
    {
        std::cout << *i;
    }
}