Simplified Linked List Implementation in C++

Question

I'm learning C++, data structures and algorithms and I have implemented a (Doubly) Linked List class for practice. Some STL functionalities are deliberately missing for now (e.g. some functions overloads, rbegin/rend/crbegin/crend, relational operators and many others). I would like to know if my approach is correct before implementing other functionalities. For example, I never implemented an iterator class before, so I opted to get a review on this first version before implementing a reverse iterator. Also, I learned from a standard book how to sort an array using merge sort, but not a linked list, so I'm curious to know if my approach to List::sort (based on this pseudocode) is clear and efficient, and how I could improve it.

I'm learning C++ through a C++11 book and trying to learn C++14 and C++17 best practices on the fly. I appreciate any advice on how make it more compatible with modern best practices. I'm using g++ compiler with -std=c++17 flag.

List.h

#ifndef LIST_H
#define LIST_H

#include <initializer_list>
#include <memory>

namespace algorithms
{
    template<typename T>
    class List 
    {
    private:
        struct Node
        {
            Node() = default;
            Node(Node* right, Node* left, const T& value): next(right), prev(left), value(value)
            {}

            Node(Node* right, Node* left, T&& value): next(right), prev(left), value(std::move(value))
            {}

            Node(Node* right, Node* left): next(right), prev(left)
            {}

            template<typename... Args>
            Node(Node* right, Node* left, Args&&... args): next(right), prev(left), value(std::forward<Args>(args)...)
            {}

            Node* next { nullptr };
            Node* prev { nullptr };
            T value {};
        };
    public:
        using size_type = std::size_t;
        using reference = T&;
        using const_reference = const T&;

        class const_iterator
        {
        public:
            using iterator_category = std::bidirectional_iterator_tag;
            using value_type = T;
            using difference_type = List::size_type;
            using pointer = const value_type*;
            using reference = const value_type&;

            const_iterator() = default;

            void swap(const_iterator& iterator) noexcept
            {
                using std::swap;

                swap(node, iterator.node);
            }

            bool operator==(const const_iterator& iterator) const noexcept 
            {
                return node == iterator.node;
            }

            bool operator!=(const const_iterator& iterator) const noexcept
            {
                return node != iterator.node;
            }

            reference operator*() const
            {
                return node->value;
            }

            reference operator->() const 
            {
                return node->value;
            }

            // Prefix operators
            const_iterator& operator++()
            {
                node = node->next;
                return *this;
            }

            const_iterator& operator--()
            {
                node = node->prev;
                return *this;
            }

            // Postfix operators
            const_iterator operator++(int)
            {
                const_iterator old(*this);
                node = node->next;
                return old;
            }

            const_iterator operator--(int)
            {
                const_iterator old(*this);
                node = node->prev;
                return old;
            }
        protected:
            Node* node { nullptr };

            explicit const_iterator(Node* ptr): node(ptr)
            {}

            friend class List;
        };

        class iterator: public const_iterator 
        {
            public:
            using iterator_category = std::bidirectional_iterator_tag;
            using value_type = T;
            using difference_type = List::size_type;
            using pointer = value_type*;
            using reference = value_type&;

            iterator() = default;

            reference operator*()
            {
                return this->node->value;
            }

            const reference operator*() const
            {
                return const_iterator::operator*();
            }

            reference operator->()
            {
                return this->node->value;
            }

            const reference operator->() const
            {
                return const_iterator::operator->();
            }

            // Prefix operators
            iterator& operator++()
            {
                this->node = this->node->next;
                return *this;
            }

            iterator& operator--()
            {
                this->node = this->node->prev;
                return *this;
            }

            // Postfix operators
            iterator operator++(int)
            {
                iterator old(*this);
                ++(*this);
                return old;
            }

            iterator operator--(int)
            {
                iterator old = *this;
                ++(*this);
                return old;
            }
        protected:
            explicit iterator(Node* ptr): const_iterator(ptr)
            {}

            friend class List;
        };

        // Constructors and Destructor
        List() = default;
        List(size_type initial_size, const T& value);
        explicit List(size_type inital_size);
        template<typename InputIt>
        List(InputIt first, InputIt last);
        List(std::initializer_list<T> initializer);
        List(const List& list);
        List(List&& list) noexcept;
        List& operator=(const List& list);
        List& operator=(List&& list) noexcept;
        ~List();

        // Iterators
        iterator begin() noexcept;
        const_iterator begin() const noexcept;
        const_iterator cbegin() const noexcept;
        iterator end() noexcept;
        const_iterator end() const noexcept;
        const_iterator cend() const noexcept;

        // Capacity
        size_type size() const noexcept;
        bool empty() const noexcept;

        // Modifiers
        template<typename InputIt>
        void assign(InputIt first, InputIt last);
        void assign(std::initializer_list<T> initializer);
        iterator insert(const_iterator position, const T& value);
        iterator insert(const_iterator position, T&& value);
        template<typename InputIt>
        iterator insert(const_iterator position, InputIt first, InputIt last);
        template<typename... Args>
        iterator emplace(const_iterator position, Args&&... args);
        template<typename... Args>
        reference emplace_back(Args&&... args);
        void push_back(const T& value);
        void push_back(T&& value);
        void pop_back();
        template<typename... Args>
        reference emplace_front(Args&&... args);
        void push_front(const T& value);
        void push_front(T&& value);
        void pop_front();
        iterator erase(const_iterator position);
        iterator erase(const_iterator first, const_iterator last);
        void clear() noexcept;
        void resize(size_type new_size, const T& value);
        void resize(size_type new_size);
        void swap(List& list) noexcept;

        // Accessors
        reference front();
        const_reference front() const;
        reference back();
        const_reference back() const;

        // Operations
        // Merge two sorted lists; no copies are made
        template<typename Compare = std::less<>>
        void merge(List& list, Compare compare = Compare());
        template<typename Compare = std::less<>>
        void sort(Compare compare = Compare());
        template<typename Function>
        size_type remove_if(Function function);
        size_type remove(const T& value);
        void splice(const_iterator position, List& list, const_iterator first, const_iterator last);
        void splice(const_iterator position, List& list, const_iterator iterator);
        void splice(const_iterator position, List& list);
        void reverse() noexcept;
        size_type unique();
        template<typename BinaryFunction>
        size_type unique(BinaryFunction binary_function);
    private:
        using Alloc = std::allocator<T>;
        using NodeAlloc = typename std::allocator_traits<Alloc>::template rebind_alloc<Node>;

        NodeAlloc node_allocator;
        Node* head { create_head() };
        size_type current_size { 0 };

        Node* create_head();
        template<typename... Args>
        Node* create_node(Node* next, Node* prev, Args&&... args);
        void destroy_node(Node* node);
        template<typename... Args>
        iterator insert_internal(const_iterator position, Args&&... args);
        template<typename... Args> 
        void resize_internal(size_type new_size, Args&&... args);
        template<typename Function>
        size_type remove_if_internal(Function function);
        template<typename BinaryFunction>
        size_type unique_internal(BinaryFunction binary_function);

        // Sorting utility functions
        template<typename Compare>
        const_iterator merge_sort(const_iterator first, size_type size, Compare compare);
        template<typename Compare>
        const_iterator merge(const_iterator first1, const_iterator first2, Compare compare);
    };

    // Non-member swap function
    template<typename T>
    void swap(List<T>& left, List<T>& right) noexcept;
}

#include "List.inl"
#endif // LIST_H

List.inl

#include <iterator>

namespace algorithms
{
    // Constructors and Destructor
    template<typename T>
    List<T>::List(size_type initial_size, const T& value)
    {
        resize(initial_size, value);
    }

    template<typename T>
    List<T>::List(size_type inital_size)
    {
        resize(inital_size);
    }

    template<typename T>
    template<typename InputIt>
    List<T>::List(InputIt first, InputIt last)
    {
        insert(begin(), first, last);
    }

    template<typename T>
    List<T>::List(std::initializer_list<T> initializer): List(initializer.begin(), initializer.end())
    {}

    template<typename T>
    List<T>::List(const List& list): List(list.begin(), list.end())
    {} 

    template<typename T>
    List<T>::List(List&& list) noexcept
    {
        list.swap(*this);
    }

    template<typename T>
    List<T>& List<T>::operator=(const List& list)
    {
        List temp(list);
        temp.swap(*this);
        return *this;
    }

    template<typename T>
    List<T>& List<T>::operator=(List&& list) noexcept
    {
        list.swap(*this);
        return *this;
    }

    template<typename T>
    List<T>::~List()
    {
        clear();
        destroy_node(head);
    }

    // Iterators
    template<typename T>
    typename List<T>::iterator List<T>::begin() noexcept
    {
        return iterator(head->next);
    }

    template<typename T>
    typename List<T>::const_iterator List<T>::begin() const noexcept
    {
        return const_iterator(head->next);
    }

    template<typename T>
    typename List<T>::const_iterator List<T>::cbegin() const noexcept
    {
        return const_iterator(head->next);
    }

    template<typename T>
    typename List<T>::iterator List<T>::end() noexcept
    {
        return iterator(head);
    }

    template<typename T>
    typename List<T>::const_iterator List<T>::end() const noexcept
    {
        return const_iterator(head);
    }

    template<typename T>
    typename List<T>::const_iterator List<T>::cend() const noexcept
    {
        return const_iterator(head);
    }

    // Capacity
    template<typename T>
    typename List<T>::size_type List<T>::size() const noexcept
    {
        return current_size;
    }

    template<typename T>
    bool List<T>::empty() const noexcept 
    {
        return current_size == 0;
    }

    // Modifiers
    template<typename T>
    template<typename InputIt>
    void List<T>::assign(InputIt first, InputIt last)
    {
        clear();
        insert(begin(), first, last);
    }

    template<typename T>
    void List<T>::assign(std::initializer_list<T> initializer)
    {
        clear();
        insert(begin(), initializer.begin(), initializer.end());
    }

    template<typename T>
    typename List<T>::iterator List<T>::insert(const_iterator position, const T& value)
    {
        return emplace(position, value);
    }

    template<typename T>
    typename List<T>::iterator List<T>::insert(const_iterator position, T&& value)
    {
        return emplace(position, value);
    }

    template<typename T>
    template<typename InputIt>
    typename List<T>::iterator List<T>::insert(const_iterator position, InputIt first, InputIt last)
    {
        iterator iterator;
        while (first != last)
        {
            iterator = insert(position, *first++);
        }

        return iterator;
    }

    template<typename T>
    template<typename... Args>
    typename List<T>::iterator List<T>::emplace(const_iterator position, Args&&... args)
    {
        return insert_internal(position, std::forward<Args>(args)...);
    }

    template<typename T>
    template<typename... Args>
    typename List<T>::reference List<T>::emplace_back(Args&&... args)
    {
        auto iterator = insert_internal(end(), std::forward<Args>(args)...);

        return *iterator;
    }

    template<typename T>
    void List<T>::push_back(const T& value)
    {
        insert_internal(end(), value);
    }

    template<typename T>
    void List<T>::push_back(T&& value)
    {
        insert_internal(end(), value);
    }

    template<typename T>
    void List<T>::pop_back()
    {
        erase(const_iterator(head->prev));
    }

    template<typename T>
    template<typename... Args>
    typename List<T>::reference List<T>::emplace_front(Args&&... args)
    {
        auto iterator = insert_internal(begin(), std::forward<Args>(args)...);

        return *iterator;
    }

    template<typename T>
    void List<T>::push_front(const T& value)
    {
        insert_internal(begin(), value);
    }

    template<typename T>
    void List<T>::push_front(T&& value)
    {
        insert_internal(begin(), value);
    }

    template<typename T>
    void List<T>::pop_front()
    {
        erase(const_iterator(head->next));
    }

    template<typename T>
    typename List<T>::iterator List<T>::erase(const_iterator position)
    {
        auto node_to_destroy = position.node;
        auto next_node = node_to_destroy->next;
        auto prev_node = node_to_destroy->prev;

        // Link the node before position.node to the node after position.node
        prev_node->next = next_node;
        next_node->prev = prev_node;

        // Unlink the node to be destroyed from the list and destroy it
        node_to_destroy->next = node_to_destroy;
        node_to_destroy->prev = node_to_destroy;
        destroy_node(node_to_destroy);

        --current_size;

        return iterator(next_node);
    }

    template<typename T>
    typename List<T>::iterator List<T>::erase(const_iterator first, const_iterator last)
    {
        if (first == begin() && last == end())
        {
            clear();
        }
        else 
        {
            while (first != last)
            {
                first = erase(first);
            }
        }

        return iterator(last.node);
    }

    template<typename T>
    void List<T>::clear() noexcept
    {
        Node* node = head->next;
        head->next = head;
        head->prev = head;

        for (Node* next_node; node != head; node = next_node)
        {
            next_node = node->next;
            destroy_node(node);
        }

        current_size = 0;
    }

    template<typename T>
    void List<T>::resize(size_type new_size, const T& value)
    {
        resize_internal(new_size, value);
    }

    template<typename T>
    void List<T>::resize(size_type new_size)
    {
        resize_internal(new_size);
    }

    template<typename T>
    void List<T>::swap(List& list) noexcept
    {
        using std::swap;

        swap(this->head, list.head);
        swap(this->current_size, list.current_size);
    }

    // Accessors
    template<typename T>
    typename List<T>::reference List<T>::front()
    {
        return head->next->value;
    }

    template<typename T>
    typename List<T>::const_reference List<T>::front() const
    {
        return head->next->value;
    }

    template<typename T>
    typename List<T>::reference List<T>::back()
    {
        return head->prev->value;
    }

    template<typename T>
    typename List<T>::const_reference List<T>::back() const
    {
        return head->prev->value;
    }

    // Operations
    template<typename T>
    template<typename Compare>
    void List<T>::merge(List& list, Compare compare)
    {
        if (this == &list)
        {
            return;
        }

        iterator this_it { begin() };
        iterator other_it { list.begin() };

        while (this_it != end() && other_it != list.end())
        {
            // return true if other < this using the custom comparison function
            if (compare(*other_it, *this_it))
            {
                auto node_to_merge = other_it;
                ++other_it;
                splice(this_it, list, node_to_merge, other_it);
            }
            else
            {
                ++this_it;
            }
        }

        // If other_it did not exhaust the list, splice it to the end of the list
        if (other_it != list.end())
        {
            splice(end(), list, other_it, list.end());
        }
    }

    template<typename T>
    template<typename Compare>
    void List<T>::sort(Compare compare)
    {
        merge_sort(begin(), size(), compare);
    }

    template<typename T>
    template<typename Function>
    typename List<T>::size_type List<T>::remove_if(Function function)
    {
        return remove_if_internal(function);
    }

    template<typename T>
    typename List<T>::size_type List<T>::remove(const T& value)
    {
        return remove_if_internal([&value = value](const T& node_value) { return value == node_value; });
    }

    template<typename T>
    void List<T>::splice(const_iterator position, List& list, const_iterator first, const_iterator last)
    {
        if (this == &list)
        {
            return;
        }

        auto size_change = std::distance(first, last);

        auto position_node = position.node;
        auto prev_node = position_node->prev;
        auto first_node = first.node;
        auto last_node = last.node->prev;

        // Link the node before first.node to the node at last.node in the list passed as argument
        auto new_first = first_node->prev;
        new_first->next = last.node;
        last.node->prev = new_first;

        // Insert the nodes in range [first; last[ between position and it's previous node
        first_node->prev = prev_node;
        last_node->next = position_node;
        prev_node->next = first_node;
        position_node->prev = last_node;

        current_size += size_change;
        list.current_size -= size_change;
    }

    template<typename T>
    void List<T>::splice(const_iterator position, List& list, const_iterator iterator)
    {
        if (this == &list)
        {
            return;
        }

        splice(position, list, iterator, const_iterator(iterator.node->next));
    }

    template<typename T>
    void List<T>::splice(const_iterator position, List& list)
    {
        if (this == &list)
        {
            return;
        }

        splice(position, list, list.begin(), list.end());
    }

    template<typename T>
    void List<T>::reverse() noexcept
    {
        using std::swap;

        for (auto iterator = begin(); iterator != end(); )
        {
            auto current_node = iterator.node;
            ++iterator;
            swap(current_node->next, current_node->prev);
        }

        auto new_first = head->prev;
        auto new_last = head->next;

        head->next = new_first;
        head->prev = new_last;
    }

    template<typename T>
    typename List<T>::size_type List<T>::unique()
    {
        return unique_internal([](const T& lhs, const T& rhs) { return lhs == rhs; });
    }

    template<typename T>
    template<typename BinaryFunction>
    typename List<T>::size_type List<T>::unique(BinaryFunction binary_function)
    {
        return unique_internal(binary_function);
    }

    // Private
    template<typename T>
    typename List<T>::Node* List<T>::create_head()
    {
        Node* node = node_allocator.allocate(1);

        // Construct Node in storage pointed by node; node->next and node->prev points to node itself
        node_allocator.construct(node, node, node);

        return node;
    }

    template<typename T>
    template<typename... Args>
    typename List<T>::Node* List<T>::create_node(Node* next, Node* prev, Args&&... args)
    {
        Node* new_node = node_allocator.allocate(1);

        node_allocator.construct(new_node, next, prev, std::forward<Args>(args)...);

        return new_node;
    }

    template<typename T>
    void List<T>::destroy_node(Node* node)
    {
        node_allocator.destroy(node);
        node_allocator.deallocate(node, 1);
    }

    template<typename T>
    template<typename... Args>
    typename List<T>::iterator List<T>::insert_internal(const_iterator position, Args&&... args)
    {
        Node* next_node = position.node;
        Node* previous_node = next_node->prev;

        Node* new_node = create_node(next_node, previous_node, std::forward<Args>(args)...);
        previous_node->next = new_node;
        next_node->prev = new_node;

        ++current_size;

        return iterator(new_node);
    }

    template<typename T>
    template<typename... Args>
    void List<T>::resize_internal(size_type new_size, Args&&... args)
    {
        if (size() < new_size)
        {
            auto to_add = new_size - size();
            for (size_type i = 0; i < to_add; ++i)
            {
                insert_internal(end(), std::forward<Args>(args)...);
            }
        }
        else 
        {
            auto to_destroy = size() - new_size;
            for (size_type i = 0; i < to_destroy; ++i)
            {
                pop_back();
            }
        }
    }

    template<typename T>
    template<typename Function>
    typename List<T>::size_type List<T>::remove_if_internal(Function function)
    {
        auto previous_size = size();

        for (auto iterator = begin(); iterator != end(); )
        {
            if (function(*iterator))
            {
                auto to_erase = iterator;
                iterator = erase(to_erase);
            }
            else
            {
                ++iterator;
            }
        }

        return previous_size - size();
    }

    template<typename T>
    template<typename BinaryFunction>
    typename List<T>::size_type List<T>::unique_internal(BinaryFunction binary_function)
    {
        auto previous_size = size();

        auto iterator = begin();
        auto back_iterator = iterator;
        ++iterator;

        while (iterator != end())
        {
            if (binary_function(*back_iterator, *iterator))
            {
                auto to_erase = iterator;
                iterator = erase(to_erase);
            }
            else 
            {
                back_iterator = iterator;
                ++iterator;
            }
        }

        return previous_size - size();
    }

    template<typename T>
    template<typename Compare>
    typename List<T>::const_iterator List<T>::merge_sort(const_iterator first, size_type size, Compare compare)
    {
        // Base case
        if (size <= 1)
        {
            // Temporarily unlink the node from the list
            first.node->next = head;
            first.node->prev = head;
            return first;
        }

        auto half_size = size / 2;
        auto mid = std::next(first, half_size);

        first = merge_sort(first, half_size, compare);
        mid = merge_sort(mid, size - half_size, compare);

        return merge(first, mid, compare);
    }

    template<typename T>
    template<typename Compare>
    typename List<T>::const_iterator List<T>::merge(const_iterator first1, const_iterator first2, Compare compare)
    {
        Node* lesser_node;
        Node* greater_node;

        // first1 and first2 each points to the start of two sublists, both ending at head. 
        // The merge operation reorder the nodes without creating any new node; only the links
        // of the nodes are changed. At the end, the resulting list is sorted and head->next 
        // points to the start of the list and head->prev points to the end of the list.

        while (first1.node != head || first2.node != head)
        {
            if (first1.node == head)
            {
                while (first2.node->next != head)
                {
                    ++first2;
                }

                head->prev = first2.node;
                break;
            }
            else if (first2.node == head)
            {
                while (first1.node->next != head)
                {
                    ++first1;
                }

                head->prev = first1.node;
                break;
            }
            else if (compare(*first1, *first2)) // first1 < first2 using the custom comparison function
            {
                lesser_node = first1.node;
                greater_node = first2.node;
                ++first1;
            }
            else 
            {
                lesser_node = first2.node;
                greater_node = first1.node;
                ++first2;
            }

            greater_node->prev->next = lesser_node;
            lesser_node->prev = greater_node->prev;

            lesser_node->next = greater_node;
            greater_node->prev = lesser_node;
        }

        // Returns iterator to the first node at the merged list
        return const_iterator(head->next);
    }

    // Non-member swap function
    template<typename T>
    void swap(List<T>& left, List<T>& right) noexcept
    {
        left.swap(right);
    }
}

EDIT:

As asked in the comments, the code bellow shows one example of how to use the class. It compiles and runs using g++ -std=c++17 -g -Wall main.cpp -o main. (I'm assuming that the List.h and List.inl files are in the same folder as main.cpp)

Running it with valgrind gave me no memory leaks and running it with GDB gave no errors. I've written more test cases, however I feel that the code in this post is already very long so I will post a not too large test.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include "List.h"

void test_sort()
{
    namespace algs = algorithms;

    algs::List<int> ascending { 3, 9, 1, 2, 4, 6, 5, 8, 7 };
    ascending.sort();
    assert(std::is_sorted(ascending.begin(), ascending.end()));
    assert(ascending.size() == 9); // Assertion: no element was lost during the sort
    assert(ascending.back() == 9);

    algs::List<int> descending { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 };
    descending.sort(std::greater<>());
    assert(std::is_sorted(descending.begin(), descending.end(), std::greater<>()));
    assert(descending.size() == 10);
    assert(descending.back() == -9);

    auto string_comparison = 
                [](const std::string& lhs, const std::string& rhs) 
                {
                    return lhs.size() == rhs.size() ? (lhs < rhs) : lhs.size() < rhs.size();
                };

    algs::List<std::string> strings { "deque", "list", "vector", "stack", "graph", "set", "queue", "map" };
    strings.sort(string_comparison);
    assert(std::is_sorted(strings.begin(), strings.end(), string_comparison));
    assert(strings.size() == 8);
    assert(strings.back() == "vector");
}

void test_remove()
{
    namespace algs = algorithms;

    algs::List<std::string> list { "Alpha", "Beta", "Alpha", "Gamma", "Alpha", "Delta", "Alpha" };

    auto old_size = list.size();
    auto removed = list.remove("Alpha");
    assert(list.size() + removed == old_size);

    old_size = list.size();
    removed = list.remove_if([](const auto& string) { return string.size() == 5; });
    assert(list.size() + removed == old_size);
    assert(list.size() == 1);
}

int main()
{
    test_sort();
    test_remove();
    std::cout << "End of Test" << std::endl;
    return 0;
}

Answer 1

The code looks nice! Here are my suggestions.

Testing

Your code passes your test, but there are quite a few bugs that can be easily caught by testing! Make sure that every functionality is tested so you don't miss some bugs.

The compiler flags

Right now, you are using this command to compile the code:

g++ -std=c++17 -g -Wall main.cpp -o main

There are three additional flags that you should normally use:

• -pedantic-errors — raises errors on non-standard GCC extensions, which are enabled by default.

• -Werror — turns warning into errors. It forces you to ensure that your code is warning-free.

• -Wextra — enables additional warnings that help catch common bugs.

Allocators

I see that you are playing a bit with allocators in the insertion functions. However, allocators are a way for users to customize the allocation, deallocation, construction, and destruction behavior of the container. Using a default allocator + allocator traits to allocate the nodes is a big overkill if you don't want to support allocators. Simply use new and delete:

new Node{T(std::forward<Args>(args)...), prev, next}; // instead of create_node
delete node;                                          // instead of destroy_node

If you do want to support allocators, though, then the data model of the class has to be changed. The node will consist of raw memory instead of a subobject: (just the idea, not tested)

struct Node {
    Node* prev{nullptr};
    Node* next{nullptr};
    std::aligned_storage_t<sizeof(T), alignof(T)> storage;

    T* address()
    {
        return std::launder(reinterpret_cast<T*>(&storage));
    }
    T& value()
    {
        return *address();
    }
};

Then, you use

• allocate to allocate a node,

• placement new to construct the node,

• construct to construct the element,

• destroy to destroy the element,

• ~Node to destroy the node (not needed if your Node class is trivially destructible), and

• deallocate to deallocate a node: (just the idea, not tested)

auto node_allocator()
{
    return NodeAlloc(alloc);
}

template <typename... Args>
Node* create_node(Node* prev, Node* next, Args&&... args)
{
    auto n_alloc = node_allocator();

    auto* node = NTraits::allocate(n_alloc, 1);
    ::new (node) Node{prev, next};
    NTraits::construct(n_alloc, node.address(), std::forward<Args>(args)...);

    return node;
}

void destroy_node(Node* node)
{
    NTraits::destroy(n_alloc, node.address());
    NTraits::deallocate(n_alloc, node);
}

where Allocator is the allocator template parameter, alloc is the Allocator member, and

using Traits  = std::allocator_traits<Allocator>;
using NAlloc  = typename Traits::template rebind_alloc<Node>;
using NTraits = typename Traits::template rebind_traits<Node>;

The node class

The node class is way too convoluted. Since we have aggregate initialization, the node class can be as simple as

struct Node {
    T value;
    Node* prev{nullptr};
    Node* next{nullptr};
};

And this is even more powerful than the constructors:

Node{T(args)} //      initializes value from '(args)'
Node{T{args}} //      initializes value from '{args}'
Node{{args}}  // copy-initializes value from '{args}'

In all cases, you can append the prev and next pointers. There is no redundant move involved here, thanks to guaranteed copy elision introduced in C++17.

The iterator classes

BUG This is wrong:

using difference_type = List::size_type;

difference_type has to be a signed type. Use std::ptrdiff_t instead.

When swapping builtin pointers, you can call std::swap directly. And the swap function of the iterator classes can be removed — std::swap works correctly.

operator!= is generally implemented in terms of operator==. Similarly, the postfix ++ and -- are implemented in terms of the prefix ++ and --. operator* and operator-> can be noexcept. operator-> should return a pointer, not a reference.

BUG const reference doesn't do what you expect. It is an attempt to add a top-level const to a reference type, and thus is equivalent to reference. What you want is const T&.

I don't really like making iterator derive from const_iterator — especially considering the added this-> clutter. Just writing two independent classes and adding a iterator(const_iterator) constructor seems good enough. That's primarily a matter of taste, though.

The constructors, destructor, and assignment operators

BUG The (it, it) constructor should be constrained with SFINAE. Right now List<unsigned int>(5, 5) will call the (it, it) version instead of the (size, value) version. Like this:

template <typename InputIt, typename = typename std::iterator_traits<InputIt>::iterator_category>
List(InputIt first, InputIt last);

Note: It's better to just define everything in the class IMO. Otherwise, the out-of-class definition will look like this:

template <typename T>
template <typename InputIt, typename>      // note: default template argument is not repeated
List<T>::List(InputIt first, InputIt last)
{
    insert(begin(), first, last);
}

The copy and move assignment operators can be unified with the copy-and-swap idiom:

// note: 1. take by value; 2. noexcept
List& operator=(List list) noexcept
{
    swap(list);
    return *this;
}

The noexcept here makes move assignment noexcept, but not copy assignment.

inital_size is a misspell.

begin and end

cbegin and cend should delegate to begin and end.

When defining the functions out of class, you can use a trailing return type instead of typename List<T>:::

template<typename T>
auto List<T>::begin() noexcept -> iterator

assign

The assign functions can be modified to provide strong exception guarantee:

template <typename InputIt> // also SFINAE this
void assign(InputIt first, InputIt last)
{
    *this = List(first, last); // creates new list first, destroys old elements after
}

void assign(std::initializer_list<T> ilist)
{
    *this = List(ilist);
}

Insertion

You can implement insert_internal in emplace directly. No need to separate.

push_back can use emplace_back directly.

Deletion

This feels wrong:

if (first == begin() && last == end())
{
    clear();
}

Special-casing begin and end really doesn't feel right. It should be possible to treat all iterators equally, so clear() can just be erase(begin(), end()).

resize

I can see why you extract a separate _internal here, but this is really an absurd unusual but creative usage of perfect forwarding. More seriously, insert_internal(end(), ...) can be simplified to emplace_back(...).

remove & unique

Again, there is no need to have an _internal when it is the same as the non-_internal version. [&value = value] can be simplified to [&value] in the lambda capture.

BUG There is a big problem with the remove: when an element from the list is passed as a const T& argument, it will be accessed after destruction.

List<int> list{1, 2, 1, 2};
list.remove(list.front()); // undefined behavior

One solution is to collect the removed elements as another List and destroy them together at the end.