Modern C++ Linked List

Question

I have been using this quarantine time to learn "Modern C++" (constructs, move semantics, smart pointers, etc, etc) via implementing basic data structures from scratch. As a first step, I've put together a simple (but, hopefully somewhat complete) linked list as one of the foundational pieces.

linked_list.h

#pragma once

#include <utility>

namespace data_structures
{
    template<typename  T>
    class linked_list
    {
        template<typename T>
        struct list_node
        {
            friend linked_list;

            typedef list_node<T> self_type;
            typedef list_node<T>& reference;
            typedef const list_node<T>& const_reference;
            typedef list_node<T>* pointer;

            explicit list_node( const T& val )
                : data{ std::move( val ) }
            { }

            explicit list_node( const T&& val )
                : data{ std::move( val ) }
            { }

            T data;

        private:
            pointer next_ = nullptr, prev_ = nullptr;
        };

        class iterator
        {
        public:

            using node = list_node<T>;

            typedef iterator self_type;

            typedef node& reference;
            typedef node* pointer;

            explicit iterator( pointer node ) :
                ptr_( node )
            { }

            self_type operator++()
            {
                if( ptr_ )
                    ptr_ = ptr_->next_;

                return *this;
            }

            reference operator*() { return *ptr_; }
            pointer operator->() { return ptr_; }

            bool operator==( const self_type& other ) { return ptr_ == other.ptr_; }
            bool operator!=( const self_type& other ) { return ptr_ != other.ptr_; }

        private:
            pointer ptr_;
        };

        typedef linked_list<T> self_type;
        typedef linked_list<T>& reference;
        typedef const linked_list<T>& const_reference;
        typedef linked_list<T>* pointer;

        typedef size_t size_type;

        typedef list_node<T> node_type;

        using node = typename node_type::pointer;
        using node_reference = typename node_type::reference;
        using const_node_reference = typename node_type::const_reference;
        using node_pointer = std::unique_ptr<node_type>;

        node_pointer head_, tail_;
        size_t length_{};

    public:

        linked_list();

        explicit linked_list( std::initializer_list<T> init_list );
        linked_list( const self_type& other );
        linked_list( self_type&& other ) noexcept;

        ~linked_list();

        void swap( reference other ) noexcept;

        void push_back( T item ) { insert( length_, item ); }
        void push_front( T item ) { insert( 0, item ); }
        void append( const_reference other );

        T pop_front();
        T pop_back();

        const_node_reference at( size_type position );

        void remove( T value );
        void remove_at( size_type position );

        iterator begin() { return iterator( head_->next_ ); }
        iterator end() { return iterator( tail_.get() ); }

        [[nodiscard]] const_node_reference front() const { return *head_->next_; }
        [[nodiscard]] const_node_reference back() const { return *tail_->prev_; }

        [[nodiscard]] bool empty() const { return head_->next == tail_.get(); }
        [[nodiscard]] size_type size() const { return length_; }

        reference operator=( const self_type& other ); // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
        reference operator=( self_type&& other ) noexcept;  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
        reference operator+( const self_type& other ) { append( other ); return *this; }

        void operator+=( const self_type& other ) { append( other ); }
        void operator+=( const T& value ) { push_back( value ); }

    protected:
        void insert( size_type position, T value );
        node get( size_type position );
    };

    template <typename T>
    linked_list<T>::linked_list()
    {
        head_ = std::make_unique<node_type>( T() );
        tail_ = std::make_unique<node_type>( T() );

        head_->next_ = tail_.get();
        head_->prev_ = tail_.get();

        tail_->next_ = head_.get();
        tail_->prev_ = head_.get();
    }

    template <typename T>
    linked_list<T>::linked_list( const std::initializer_list<T> init_list ) :
        linked_list()
    {
        for( auto& item : init_list )
        {
            push_back( item );
        }
    }

    template <typename T>
    linked_list<T>::linked_list( const self_type& other )
        : linked_list()
    {
        append( other );
    }

    template <typename T>
    linked_list<T>::linked_list( self_type&& other ) noexcept
        : linked_list()
    {
        swap( other );
    }

    template <typename T>
    linked_list<T>::~linked_list()
    {
        if( !head_ ) return; // destroyed from move

        for( node current = head_->next_; current != tail_.get(); )
        {
            node temp = current;

            current = current->next_;

            delete temp;
        }
    }

    template <typename T> // NOLINT(cppcoreguidelines-c-copy-assignment-signature
    typename linked_list<T>::reference linked_list<T>::operator=( const self_type& other )  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
    {
        if( this == &other ) return *this;

        auto temp( other );

        temp.swap( *this );

        return *this;
    }

    template <typename T> // NOLINT(cppcoreguidelines-c-copy-assignment-signature
    typename linked_list<T>::reference linked_list<T>::operator=( self_type&& other ) noexcept  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
    {
        if( this == &other )
            return *this;

        // clean up this
        for( node current = head_->next_; current != tail_.get(); )
        {
            node temp = current;

            current = current->next_;

            delete temp;

            length_--;
        }

        // this <- other
        head_ = std::move( other.head_ );
        tail_ = std::move( other.tail_ );
        length_ = other.length_;
        other.length_ = 0;

        return *this;
    }

    template <typename T>
    void linked_list<T>::swap( reference other ) noexcept
    {
        std::swap( head_, other.head_ );
        std::swap( tail_, other.tail_ );
        std::swap( length_, other.length_ );
    }

    template <typename T>
    void linked_list<T>::append( const_reference other )
    {
        node dest = tail_->prev_;

        for( node source = other.head_->next_; 
            source != other.tail_.get();
            source = source->next_ )
        {
            node new_node{ new node_type( source->data ) };

            if( new_node == nullptr )
                throw std::bad_alloc();

            new_node->prev_ = dest;
            dest->next_ = new_node;

            dest = new_node;
            length_++;
        }

        dest->next_ = tail_.get();
        tail_->prev_ = dest;
    }

    template <typename T>
    T linked_list<T>::pop_front()
    {
        if( length_ <= 0 )
            throw std::runtime_error( "ATTEMPT_POP_EMPTY_LIST" );

        const auto value = front().data;

        remove_at( 0 );

        return value;
    }

    template <typename T>
    T linked_list<T>::pop_back()
    {
        if( length_ <= 0 )
            throw std::runtime_error( "ATTEMPT_POP_EMPTY_LIST" );

        const auto value = back().data;

        remove_at( length_ - 1 );

        return value;
    }

    template <typename T>
    typename linked_list<T>::const_node_reference linked_list<T>::at( size_type position )
    {
        if( position >= length_ )
            throw std::runtime_error( "INVALID_LIST_POSITION" );

        return *get( position );
    }

    template <typename T>
    void linked_list<T>::insert( const size_type position, T value )
    {
        if( position > length_ + 1)
            throw std::runtime_error( "INVALID_LIST_POSITION" );

        node next = get( position );

        node new_node{ new node_type( value ) };

        if( new_node == nullptr )
            throw std::bad_alloc();

        node prev = next->prev_;

        new_node->next_ = next;
        new_node->prev_ = prev;

        prev->next_ = new_node;
        next->prev_ = new_node;

        length_++;
    }

    template <typename T>
    typename linked_list<T>::node linked_list<T>::get( const size_type position )
    {
        const auto mid = ceil( length_ / 2 );

        node node;

        if( position <= mid )
        {
            node = head_->next_;

            for( size_type index = 0; index < position; index++ )
                node = node->next_;
        }
        else
        {
            node = tail_.get();

            for( size_type index = length_; index > position; index-- )
                node = node->prev_;
        }

        return node;
    }

    template <typename T>
    void linked_list<T>::remove( T value )
    {
        for( node node = head_->next_;
            node != tail_.get();
            node = node->next_ )
        {
            if( node->data == value )
            {
                node->prev_->next_ = node->next_;
                node->next_->prev_ = node->prev_;

                delete node;

                length_--;
                break;
            }
        }
    }

    template <typename T>
    void linked_list<T>::remove_at( const size_type position )
    {
        if( position >= length_ )
            throw std::runtime_error( "REMOVE_PAST_END_ATTEMPT" );

        node node = get( position );

        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;

        delete node;

        length_--;
    }
}

A few notes:

The use of smart pointers for the sentinel nodes and not the actual list contents seemed to be the best trade-off in terms of code readability & design. I have refactored this a few times (from a singly using all unique_ptr's, to a double using a unique_ptr for the head/next node and standard references to the tail/prev node, to this current version). Happy to hear any suggestions here.

The move semantics for the list itself I am not completely in love with. For example, when initializing a new list from an existing one using std::move the old list will no longer have valid sentinel nodes as they have been 'reclaimed' by the new list, so the old one is now 'invalid' and the deconstructor has a fail-safe check to not clean itself up if this is the case. From reading how this should be implemented (the move'd object should still valid post-move, just in an 'invalid' state), I believe what I have is correct although it just seems suboptimal.

The iterator implementation I have doesn't include a const version as from what I have been reading (or, at least my interpretation I should say) is that is no longer 'best practice' to implement a const version of the iterator & cbegin/cend, and instead the consumer should use const correct iterators? (i.e., 'for(const auto& i : list )' in C++ 17+. Is my interpretation correct here?

Any and all other suggestions for improvement/functionality/readability/etc welcomed.

There is also a set of unit tests (GTest) if anyone is interested.

linkedlist_test.cpp

#include "pch.h"
#include <gtest/gtest.h>

#include "../data-structures/linked_list.h"

namespace data_structure_tests::integer_linked_list_tests
{
    typedef data_structures::linked_list<int> int_list;

    /// <summary>
    /// Testing class for singly linked list.
    /// </summary>
    class linked_list_tests :
        public ::testing::Test {

    protected:
        void SetUp() override
        {
        }

        void TearDown() override
        {
        }
    };

    //
    // Linked List Tests
    //

    TEST_F( linked_list_tests, at_head )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 0 );

        EXPECT_EQ( actual.data, 1 );
    }

    TEST_F( linked_list_tests, at_tail )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 2 );

        EXPECT_EQ( actual.data, 3 );
    }

    TEST_F( linked_list_tests, get_head )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 0 );

        EXPECT_EQ( actual.data, 1 );
    }

    TEST_F( linked_list_tests, push_front_empty )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, push_back )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 3 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_back( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 2 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, push_front )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_front( 3 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_front( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_front( 1 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 3 );
    }

    TEST_F( linked_list_tests, init_list )
    {
        auto list = int_list{ 5, 4, 3, 2, 1 };

        EXPECT_EQ( list.size(), 5 );

        EXPECT_EQ( list.front().data, 5 );
        EXPECT_EQ( list.back().data, 1 );

        EXPECT_EQ( list.at( 4 ).data, 1 );
        EXPECT_EQ( list.at( 3 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 1 ).data, 4 );
        EXPECT_EQ( list.at( 0 ).data, 5 );
    }

    TEST_F( linked_list_tests, out_of_bounds )
    {
        auto list = int_list{ 1, 2, 3, 4 };

        try
        {
            auto no_exist = list.at( 4 );

            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "INVALID_LIST_POSITION" );
        }
    }

    TEST_F( linked_list_tests, iterator )
    {
        auto list = int_list{ 0, 1, 2, 3, 4, 5 };

        auto expected = 0;

        for( const auto& node : list )
        {
            auto actual = node.data;

            EXPECT_EQ( actual, expected );

            expected++;
        }
    }

    TEST_F( linked_list_tests, add_lists )
    {
        auto list1 = int_list{ 0, 1, 2, 3, 4 };
        const auto list2 = int_list{ 5, 6, 7, 8, 9 };

        list1 = list1 + list2;

        auto expected = 0;

        for( const auto& node : list1 )
        {
            auto actual = node.data;

            EXPECT_EQ( actual, expected );

            expected++;
        }
    }

    TEST_F( linked_list_tests, append_value )
    {
        auto list = int_list{ 0, 1, 2 };

        EXPECT_EQ( list.size(), 3 );

        list += 3;

        EXPECT_EQ( list.size(), 4 );
        EXPECT_EQ( list.back().data, 3 );

        EXPECT_EQ( list.at( 0 ).data, 0 );
        EXPECT_EQ( list.at( 1 ).data, 1 );
        EXPECT_EQ( list.at( 2 ).data, 2 );
        EXPECT_EQ( list.at( 3 ).data, 3 );
    }

    TEST_F( linked_list_tests, swap )
    {
        auto list1 = int_list{ 1, 2, 3 };
        auto list2 = int_list{ 4, 5, 6 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list2.size(), 3 );

        list1.swap( list2 );

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list2.size(), 3 );

        EXPECT_EQ( list1.at( 0 ).data, 4 );
        EXPECT_EQ( list1.at( 1 ).data, 5 );
        EXPECT_EQ( list1.at( 2 ).data, 6 );

        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, copy_constructor )
    {
        auto list = int_list{ 0, 1, 2 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 0 );
        EXPECT_EQ( list.at( 1 ).data, 1 );
        EXPECT_EQ( list.at( 2 ).data, 2 );

        auto list_copy( list );

        EXPECT_EQ( list_copy.size(), 3 );
        EXPECT_EQ( list_copy.at( 0 ).data, 0 );
        EXPECT_EQ( list_copy.at( 1 ).data, 1 );
        EXPECT_EQ( list_copy.at( 2 ).data, 2 );

        list_copy.push_back( 4 );

        EXPECT_EQ( list_copy.back().data, 4 );

        EXPECT_NE( list.back().data, list_copy.back().data );
    }

    TEST_F( linked_list_tests, copy_assignment_equal )
    {
        auto list1 = int_list{ 0, 1, 2 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        auto list2 = int_list{ 3, 4, 5 };

        EXPECT_EQ( list2.size(), 3 );

        list2 = list1;

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 0 );
        EXPECT_EQ( list2.at( 1 ).data, 1 );
        EXPECT_EQ( list2.at( 2 ).data, 2 );
    }

    TEST_F( linked_list_tests, self_copy )
    {
        auto list1 = int_list{ 0, 1, 2 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        list1 = list1;

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );
    }

    TEST_F( linked_list_tests, move_assignment_operator )
    {
        auto list1 = int_list{ 1, 2, 3 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 1 );
        EXPECT_EQ( list1.at( 1 ).data, 2 );
        EXPECT_EQ( list1.at( 2 ).data, 3 );

        auto list2 = int_list{ 4, 5, 6 };

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 4 );
        EXPECT_EQ( list2.at( 1 ).data, 5 );
        EXPECT_EQ( list2.at( 2 ).data, 6 );

        list2 = std::move( list1 );

        // list1 = invalid state

        EXPECT_EQ( list1.size(), 0 ); // NOLINT(bugprone-use-after-move, hicpp-invalid-access-moved)

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, move_constructor )
    {
        auto list1 = int_list{ 1, 2, 3, 4, 5 };

        EXPECT_EQ( list1.size(), 5 );

        EXPECT_EQ( list1.at( 0 ).data, 1 );
        EXPECT_EQ( list1.at( 1 ).data, 2 );
        EXPECT_EQ( list1.at( 2 ).data, 3 );
        EXPECT_EQ( list1.at( 3 ).data, 4 );
        EXPECT_EQ( list1.at( 4 ).data, 5 );

        auto list2 = std::move( list1 );

        // list1 = invalid state

        EXPECT_EQ( list1.size(), 0 );  // NOLINT(bugprone-use-after-move, hicpp-invalid-access-moved)

        EXPECT_EQ( list2.size(), 5 );

        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
        EXPECT_EQ( list2.at( 3 ).data, 4 );
        EXPECT_EQ( list2.at( 4 ).data, 5 );
    }

    TEST_F( linked_list_tests, move_constructor_copy )
    {
        auto outer = int_list();

        {
            auto inner = int_list{ 1, 2, 3, 4, 5 };

            EXPECT_EQ( inner.size(), 5 );

            EXPECT_EQ( inner.at( 0 ).data, 1 );
            EXPECT_EQ( inner.at( 1 ).data, 2 );
            EXPECT_EQ( inner.at( 2 ).data, 3 );
            EXPECT_EQ( inner.at( 3 ).data, 4 );
            EXPECT_EQ( inner.at( 4 ).data, 5 );

            outer = std::move( inner );
        }

        EXPECT_EQ( outer.size(), 5 );
        EXPECT_EQ( outer.at( 0 ).data, 1 );
        EXPECT_EQ( outer.at( 1 ).data, 2 );
        EXPECT_EQ( outer.at( 2 ).data, 3 );
        EXPECT_EQ( outer.at( 3 ).data, 4 );
        EXPECT_EQ( outer.at( 4 ).data, 5 );
    }

    TEST_F( linked_list_tests, empty_insert_delete )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, remove_single )
    {
        auto list = int_list{ 1 };

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );

        list.remove( 1 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, remove_head_double )
    {
        auto list = int_list{ 1, 2 };

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 2 );
    }

    TEST_F( linked_list_tests, remove_tail_double )
    {
        auto list = int_list{ 1, 2 };

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove( 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, remove_head_triple )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );
    }

    TEST_F( linked_list_tests, remove_past_end )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        try
        {
            list.remove_at( 3 );
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "REMOVE_PAST_END_ATTEMPT" );
        }

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, remove_tail_triple )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        list.remove_at( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.back().data, 2 );
    }

    TEST_F( linked_list_tests, remove_middle )
    {
        auto list = int_list{ 1, 2, 3, 4, 5, 6 };

        EXPECT_EQ( list.size(), 6 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 4 );
        EXPECT_EQ( list.at( 4 ).data, 5 );
        EXPECT_EQ( list.at( 5 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 4 );

        EXPECT_EQ( list.size(), 5 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 4 );
        EXPECT_EQ( list.at( 4 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 3 );

        EXPECT_EQ( list.size(), 4 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 3 );

        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );
        EXPECT_EQ( list.at( 2 ).data, 6 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 2 );

        EXPECT_EQ( list.size(), 2 );

        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 3 );

        list.remove_at( 1 );

        EXPECT_EQ( list.size(), 1 );

        EXPECT_EQ( list.at( 0 ).data, 2 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 0 );

        EXPECT_EQ( list.front().data, 0 );
        EXPECT_EQ( list.back().data, 0 );
    }

    TEST_F( linked_list_tests, pop_front_empty )
    {
        auto list = int_list{};

        try
        {
            list.pop_back();
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "ATTEMPT_POP_EMPTY_LIST" );
        }
    }

    TEST_F( linked_list_tests, pop_back_empty )
    {
        auto list = int_list{};

        try
        {
            list.pop_back();
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "ATTEMPT_POP_EMPTY_LIST" );
        }
    }

    TEST_F( linked_list_tests, pop_front )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_front(), 1 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_front(), 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_front(), 3 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, pop_back )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_back(), 3 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_back(), 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_back(), 1 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, pop_alt )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        EXPECT_EQ( list.size(), 5 );
        EXPECT_EQ( list.pop_front(), 1 );

        EXPECT_EQ( list.size(), 4 );
        EXPECT_EQ( list.pop_back(), 5 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_front(), 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_back(), 4 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_front(), 3 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, find_element )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        const auto to_find = 3;

        auto actual = std::find_if(list.begin(), list.end(),
            [&]( const auto& node ) { return node.data == to_find; });

        EXPECT_TRUE( actual != std::end( list ) );
        EXPECT_EQ( actual->data, to_find );
    }

    TEST_F( linked_list_tests, no_find_element )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        const auto to_find = 6;

        auto actual = std::find_if( list.begin(), list.end(),
            [&]( const auto& node ) { return node.data == to_find; } );

        EXPECT_TRUE( actual == std::end( list ) );
    }
}

Community · Accepted Answer · 2020-06-10 13:24:26Z

The code is pretty good, but there are some parts of it that aren't intuitive enough to be readed cleverly.

Don't misunderstand me, your design is good, but it is quite complex to be seen through properly. Have in account:

Our main goal is to be meaningful building the simplest.

Think of it as a martial artist, be efficient with the minimum movement. Emphatically, this allow us to make better systems and extend them.

The Good:

Modern features added to the implementation, which brings optimization.
Non use of macros (it is better to avoid them)
Non use of using namespace
Use of exceptions when needed (essential when working with data structures)

Code Review:

If you are writing a data structures project, you will find that dynamic data structures needs common linking components. In example a queue or a stack will use a Singly Linked Node or if you want a Doubly Linked Node. So, you could define list_node in other file. Commonly you will want to have classes and structures separated in distinct files.
Struct properties are public by default you really don't need to make your linked_list a friend class of list_node
Do not use typedef so frecuently, it makes the code quite messy. when you do this you hide the type and if the new typedef isn't descriptive enough it will cause trouble both reading and debuggin the code.
Be consistent with naming, I saw a field called ptr_ so you should use the _ suffix.
The best of a struct is to easily handle its members because they are public think of it, the implementation normally hide the nodes (should).
Your implementations of data structures should not return node objects.

Some comments:

It is interesting the way you are reinventing the wheel, normally some people says things like "we do not need to reinvent the wheel, since it is done why..." and so, but think of it, what tire manufacturers are doing in this moment. Well passing the discussion, the answer is simple, you always need something better.

I recommend you the following Google C++ Style Guide which is something good to familiarize with. This is an standard for coding C++ elaborated by Google (if you don't have a standard you already follow)

Finally. Hope that my answer were of you like and helped you.

As mentioned before, provide specific observations about the code, and provide specific references. The good bullet points are fine, what are possible issues in the code, they should be bullet points, not rewriting the posters code. — pacmaninbw, Commented Apr 12, 2020 at 22:57
I see your point, you mean simplify the answer so that it be easy and fast to read ? — sɪʒɪhɪŋ βɪstɦa kxɐll, Commented Apr 13, 2020 at 13:26
Much better, you can include code as examples of your points, but don't rewrite the entire solution. — pacmaninbw, Commented Apr 13, 2020 at 13:53
I just now saw this answer after so much time has passed (a random upvote triggered a notification). I I also got a good chuckle out of the code that I thought was good at the time (I now only write C++ for custom routines in Rcpp), Your feedback is incredible, so thank you for taking the time to write that. — Brandon Moretz, Commented Aug 19, 2022 at 19:48

Stack Exchange Network

Modern C++ Linked List

linked_list.h

linkedlist_test.cpp

1 Answer 1

The Good:

Code Review:

Some comments:

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
reinventing-the-wheel
c++17
or ask your own question.

Hot Network Questions

Modern C++ Linked List

linked_list.h

linkedlist_test.cpp

1 Answer 1

The Good:

Code Review:

Some comments:

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++linked-listreinventing-the-wheelc++17 or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
reinventing-the-wheel
c++17
or ask your own question.