7
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

Overview

Good.

Can't use default move operators as you do memory (resource) management within the class so you need to define your own.

You should allow the user to pass objects so they can be copied or moved into the list.

A couple of minor bugs (that should have been caught by your unit tests).

Code Review

First issue is that you forgot to call clear() first. here.

        Cdoubly_linked_list& operator=(const Cdoubly_linked_list& other) // copy assignment operator
        {
            if (*this != other)
            {
                // should call clear() here.

                Node* tmp = other.head;
                while (tmp != nullptr)
                {
                    push_back(tmp->value);
                    tmp = tmp->next;
                }
            }
            return *this;
        }

If you fix that the implementation works. BUT it does not fulfill the strong exception guarantee. i.e. if something goes wrong and the assignment fails your object is left in an inconsistent state. I would use the copy and swap idiom. This is where you copy the object into a temporary then swap with the current state.

Cdoubly_linked_list& operator=(Cdoubly_linked_list const& other)
{
    Cdoubly_linked_list tmp(other);  // Use copy constructor
                                     // to make the copy.

    // Now that you have made a copy and it worked.
    // simply swap the tmp value with *this
    swap(tmp);

    return *this;
    // The destructor of tmp will not handle the cleanup
    // of the old object.
}
void swap(Cdoubly_linked_list& other) noexcept
{
    using std::swap;
    swap(head, other.head);
    swap(tail, other.tail);
}

Because you have dynamic allocation in the class the default implementation does not work. You need to write your own versions of these operations.

        Cdoubly_linked_list(Cdoubly_linked_list&& other) = default; // move constructor
        Cdoubly_linked_list& operator=(Cdoubly_linked_list&& other) = default; // move assignment operator

But they are relatively simply to write:

Cdoubly_linked_list(Cdoubly_linked_list&& other) noexcept
    : head(nullptr)
    , tail(nullptr)
{
    swap(other);
}
Cdoubly_linked_list& operator=(Cdoubly_linked_list&& other) noexcept
{
    swap(other);
    return *this;
}

Simply swap with the object that is being moved.


This can be simplified:

        bool is_empty() // return true if list is empty
        {
            if (head == nullptr) return true;
            return false;

            // rewrite as:

            return head == nullptr;
        }

You don't check if head is nullptr!! So head->value may be UB.

            if (val == head->value) { pop_front(); return true; }

What happens if there is only one value in the list?

            Node* tmp = head->next;
            while (tmp != tail)

tmp is already nullptr and will never be equal to tail.


        void pop_front() // pop first element
        {
            if (head != nullptr)
            {
                Node* tmp = head;
                head = head->next;
                delete tmp;

This seems like a bug!

                if (head == nullptr) tail = nullptr;

I think you mean: if head == tail.

            }
        }

Pass values by const reference to prevent an unnecessaery copy here:

        void push_front(T val) // insert element at front

You may also want to allow the user to pass by r-value ref.

        void push_front(T const& val)
        void push_front(T&& val)
        void push_back(T const& val)
        void push_back(T&& val)

For advanced usage allow construction in place:

        template<typename... Args>
        void emplace_front(Args&&... args);
        template<typename... Args>
        void emplace_back(Args&&... args);

Sure this looks good:

        void push_front(T val) // insert element at front

But I think you can simplify to:

        void push_front(T const& val)
        {
            head = new Node(val, nullptr, head);
            if (tail == nullptr) {
                tail = head;
            }
        }

Same simplification

        void push_back(T const& val) // insert element at back
        {
            tail = new Node(val, tail, nullptr);
            if (head == nullptr) {
                head = tail;
            }
        }

end() should be one past the end of the container.

        it end() const // get end iterator
        {
            return it(tail);
        }

If you do this the standard algorithms are going to miss the last element in the list.

I would do:

        it end() const {return it{nullptr};}

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks for the answer. Shouldn't the default move constructor and move assignment operator work, because I dont actually have to deal with memory allocation like with the copy operations but can just copy the head and tail values? \$\endgroup\$
    – Tom Gebel
    Nov 8, 2020 at 21:44
  • 1
    \$\begingroup\$ @TomGebel. Move Assignment operator needs to de-allocate its current memory or make sure that the memory will be de-allocated. \$\endgroup\$ Nov 8, 2020 at 21:59
2
\$\begingroup\$

Overload the operator != before it's use

You seem to use operator!= which was not overloaded, a simple implementation might be

bool operator==(const Cdoubly_linked_list& other) 
{
    return head == other.head;
}

Then you can simply implement operator!= like this

bool operator!=(const Cdoubly_linked_list& other) 
{
    return !(*this == other );
}

Unnecessary call to clear()

This is just unnecessary, define the cleanup operations in the destructor and thus avoid the function call overhead


Why squeeze this into one line?

if (val == head->value) { pop_front(); return true; }

This can be written more clearly and less eye hurting like this

if (val == head->value) 
    pop_front(); 
    return true; 
}

The same case here.

if (val == tail->value) { pop_back(); return true; }

No need for `if` statement

I see you are testing if head == nullptr in this method.

bool is_empty() // return true if list is empty
{
    if (head == nullptr) return true;
    return false;
}

This can simply be written as:

bool is_empty() // return true if list is empty
{
    return head == nullptr;
}
\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the answer, but I have a question: Wouldn't it be against the DRY principle to write the clean up operations again in the destructor? I want the clear() method to exist as public. \$\endgroup\$
    – Tom Gebel
    Nov 8, 2020 at 16:45
  • \$\begingroup\$ I would suggest making it is_empty() const as you aren't modifying member variables. Maybe the [[nodiscard]] keyword too. \$\endgroup\$
    – user228914
    Nov 8, 2020 at 17:10
  • \$\begingroup\$ Follow your own advice. Get rid of the if statement in operator==. \$\endgroup\$
    – Reinderien
    Nov 8, 2020 at 17:13
  • \$\begingroup\$ @Reinderien, my bad. \$\endgroup\$ Nov 8, 2020 at 17:19
  • \$\begingroup\$ No problem - you can edit your answer and all will be well :) \$\endgroup\$
    – Reinderien
    Nov 8, 2020 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.