Double Linked List Using Smart Pointers

Question

I have decided to rewrite what I did here, following the suggestions to use smart pointers. I will rewrite the other data structures as well using smart pointers where appropriate.

I just want to see how my code stands now, I am sure there are still areas I need to improve or fix. I again want to thank this community in their effort in evaluating my code, I really appreciate it and I believe it is slowly but surely taking my coding skills to the next level.

Here is my header file:

#ifndef DOUBLELINKEDLIST_h
#define DOUBLELINKEDLIST_h


template <class T>
class DoubleLinkedList {
private:

    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;
        Node* previous = nullptr;

        template<typename... Args, typename = std::enable_if_t<std::is_constructible<T, Args&&...>::value>>
        explicit Node(std::unique_ptr<Node>&& next, Node* previous, Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value)
            : data{ std::forward<Args>(args)... }, previous{previous}, next{ std::move(next) } {}

        // disable if noncopyable<T> for cleaner error msgs
        explicit Node(const T& x, std::unique_ptr<Node>&& p = nullptr)
            : data(x)
            , next(std::move(p)) {}

        // disable if nonmovable<T> for cleaner error msgs
        explicit Node(T&& x, std::unique_ptr<Node>&& p = nullptr)
            : data(std::move(x))
            , next(std::move(p)) {}
    };
    std::unique_ptr<Node> head = nullptr;
    Node* tail = nullptr;

    void do_pop_front() {
        head = std::move(head->next);
        if (!tail) tail = head.get(); // update tail if list was empty before
    }

public:
    // Constructors
    DoubleLinkedList() = default;                                           // empty constructor 
    DoubleLinkedList(DoubleLinkedList const &source);                       // copy constructor

                                                                            // Rule of 5
    DoubleLinkedList(DoubleLinkedList &&move) noexcept;                     // move constructor
    DoubleLinkedList& operator=(DoubleLinkedList &&move) noexcept;          // move assignment operator
    ~DoubleLinkedList() noexcept;

    // Overload operators
    DoubleLinkedList& operator=(DoubleLinkedList const &rhs);

    // Create an iterator class
    class iterator;
    iterator begin();
    iterator end();
    iterator before_begin();

    // Create const iterator class
    class const_iterator;
    const_iterator cbegin() const;
    const_iterator cend() const;
    const_iterator begin() const;
    const_iterator end() const;
    const_iterator before_begin() const;
    const_iterator cbefore_begin() const;

    // Reverse iteator 
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    reverse_iterator rbegin() noexcept { return { end() }; }
    const_reverse_iterator rbegin() const noexcept { return { end() }; }
    const_reverse_iterator crbegin() const noexcept { return { end() }; }

    reverse_iterator rend() noexcept { return { begin() }; }
    const_reverse_iterator rend() const noexcept { return { begin() }; }
    const_reverse_iterator crend() const noexcept { return { begin() }; }

    // Memeber functions
    void swap(DoubleLinkedList &other) noexcept;
    bool empty() const { return head.get() == nullptr; }
    int size() const;

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

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

    template<typename... Args>
    iterator emplace(const_iterator pos, Args&&... args);

    void push_back(const T &theData);
    void push_back(T &&theData);
    void push_front(const T &theData);
    void push_front(T &&theData);
    iterator insert(const_iterator pos, const T& theData);
    iterator insert(const_iterator pos, T&& theData);
    void clear();
    void pop_front();
    void pop_back();
    iterator erase(const_iterator pos);
    bool search(const T &x);


};

template <class T>
class DoubleLinkedList<T>::iterator {
    Node* node = nullptr;
    bool end_reached = true;

public:
    friend class DoubleLinkedList<T>;

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T * ;
    using reference = T & ;

    iterator(Node* node = nullptr, bool end_reached = false) : node{ node }, end_reached{ end_reached }  {}

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

    T& operator*() const { return node->data; }
    T* operator->() const { return &node->data; }

    iterator& operator++();
    iterator operator++(int);
    iterator& operator--();
    iterator operator--(int);
};

template <class T>
class DoubleLinkedList<T>::const_iterator {
    Node* node = nullptr;
    bool end_reached = true;

public:
    friend class DoubleLinkedList<T>;

    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T *;
    using reference = const T &;

    const_iterator() = default;
    const_iterator(Node* node, bool end_reached = false) : node{ node }, end_reached { end_reached }  {}


    bool operator!=(const_iterator other) const noexcept;
    bool operator==(const_iterator other) const noexcept;

    const T& operator*() const { return node->data; }
    const T* operator->() const { return &node->data; }

    const_iterator& operator++();
    const_iterator operator++(int);
    const_iterator& operator--();
    const_iterator operator--(int);
};

template <class T>
DoubleLinkedList<T>::DoubleLinkedList(DoubleLinkedList<T> const &source) {
    for (Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
        push_back(loop->data);
    }
}

template <class T>
DoubleLinkedList<T>::DoubleLinkedList(DoubleLinkedList<T>&& move) noexcept {
    move.swap(*this);
}

template <class T>
DoubleLinkedList<T>& DoubleLinkedList<T>::operator=(DoubleLinkedList<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
DoubleLinkedList<T>::~DoubleLinkedList() {
    clear();
}

template <class T>
void DoubleLinkedList<T>::clear() {
    while (head) {
        do_pop_front();
    }
}

template <class T>
DoubleLinkedList<T>& DoubleLinkedList<T>::operator=(DoubleLinkedList const &rhs) {
    SingleLinkedList copy{ rhs };
    swap(copy);
    return *this;
}

template <class T>
void DoubleLinkedList<T>::swap(DoubleLinkedList &other) noexcept {
    using std::swap;
    swap(head, other.head);
    swap(tail, other.tail);
}

template <class T>
int DoubleLinkedList<T>::size() const {
    int size = 0;
    for (auto current = head.get(); current != nullptr; current = current->next.get()) {
        size++;
    }
    return size;
}

template <class T>
template <typename... Args>
void DoubleLinkedList<T>::emplace_back(Args&&... args) {
    if (!head) emplace_front(std::forward<Args>(args)...);
    else {
        tail->next = std::make_unique<Node>(nullptr, tail, std::forward<Args>(args)...);
        tail = tail->next.get();
    }
}

template <class T>
template <typename... Args>
void DoubleLinkedList<T>::emplace_front(Args&&... args) {
    head = std::make_unique<Node>(std::move(head), nullptr, std::forward<Args>(args)...);
    if (!tail) tail = head.get(); // update tail if list was empty before
}


template <class T>
template <typename... Args>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::emplace(const_iterator pos, Args&&... args) {
    if (pos.end_reached) {
        emplace_back(std::forward<Args>(args)...);
        return end();
    }

    if (!head) {
        emplace_front(std::forward<Args>(args)...);
        return begin();
    }
    std::unique_ptr<Node> newNode = std::make_unique<Node>(std::forward<Args>(args)...);
    newNode->previous = pos.node->previous;
    newNode->next = std::move(pos.node->previous->next);
    pos.node->previous = newNode.get();
    newNode->previous->next = std::move(newNode);

    return  {pos.node->previous}; 
}

template <class T>
void DoubleLinkedList<T>::push_back(const T &theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(std::move(theData));
    newNode->previous = tail;

    if (!head) {
        head = std::move(newNode);
        tail = head.get();
    }
    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}

template <class T>
void DoubleLinkedList<T>::push_back(T &&thedata) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(std::move(thedata));
    newNode->previous = tail;

    if (!head) {
        head = std::move(newNode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}


template <class T>
void DoubleLinkedList<T>::push_front(const T &theData) {
    head = std::make_unique<Node>(std::move(head), nullptr, theData);

    if (!(head->next)) {
        tail = head.get();
    }
}

template <class T>
void DoubleLinkedList<T>::push_front(T &&theData) {
    head = std::make_unique<Node>(std::move(head),nullptr,std::move(theData));

    if (!(head->next)) {
        tail = head.get();
    }
}


template <class T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::insert(const_iterator pos, const T& theData) {
    return emplace(pos, theData);
}

template <class T>
typename  DoubleLinkedList<T>::iterator DoubleLinkedList<T>::insert(const_iterator pos, T&& theData) {
    return emplace(pos, std::move(theData));
}

template <class T>
void DoubleLinkedList<T>::pop_front() {
    if (empty()) {
        throw std::out_of_range("List is Empty!!! Deletion is not possible.");
    }

    do_pop_front();
}

template <class T>
void DoubleLinkedList<T>::pop_back() {
    if (!head) {
        return;
    }

    if (head) {
        auto current = head.get();
        Node* prev = nullptr;
        while (current->next) {
            prev = current;
            current = current->next.get();
        }
        tail = prev;
        prev->next = nullptr;
    }
    else {
        throw std::out_of_range("The list is empty, nothing to delete.");
    }
}

template <class T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::erase(const_iterator pos) {
    if (pos.end_reached) {
        pop_back();
        return end();
    }

    if (pos.node && pos.node->next) {
        pos.node->next = std::move(pos.node->previous->next);
        return { pos.node->previous };
    }

    return begin();
}

template <class T>
bool DoubleLinkedList<T>::search(const T &x) {
    return std::find(begin(), end(), x) != end();
}

template <typename T>
std::ostream& operator<<(std::ostream &str, DoubleLinkedList<T>& list) {
    for (auto const& item : list) {
        str << item << "\t";
    }
    return str;
}


// Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename DoubleLinkedList<T>::iterator& DoubleLinkedList<T>::iterator::operator++() {
    if (!node) return *this;

    if (node->next) {
        node = node->next.get();
    }

    else {
        end_reached = true;         // keep last node, so we can go backwards if required
    }

    return *this;
}

template<typename T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template <class T>
typename DoubleLinkedList<T>::iterator& DoubleLinkedList<T>::iterator::operator--() {
    if (!node) return *this;

    if (end_reached) {
        end_reached = false;
    }

    else if (node->previous) {
        node = node->previous.get();
    }

    return *this;
}

template<typename T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::iterator::operator--(int) {
    auto copy = *this;
    --*this;
    return copy;
}

template<typename T>
bool DoubleLinkedList<T>::iterator::operator==(iterator other) const noexcept {
    if (end_reached) return other.end_reached;

    if (other.end_reached) return false;

    return node == other.node;
}

template<typename T>
bool DoubleLinkedList<T>::iterator::operator!=(iterator other) const noexcept {
    return !(*this == other);
}

template<class T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::begin() {
    return head.get();
}

template<class T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::end() {
    return {tail, true};
}

template <class T>
typename DoubleLinkedList<T>::iterator DoubleLinkedList<T>::before_begin() {
    return { head.get(), false };
}

// Const Iterator Implementaion////////////////////////////////////////////////
template <class T>
typename DoubleLinkedList<T>::const_iterator& DoubleLinkedList<T>::const_iterator::operator++() {
    if (!node) return *this;

    if (node->next) {
        node = node->next.get();
    }

    else {
        end_reached = true;         // keep last node, so we can go backwards if required
    }

    return *this;
}

template<typename T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::const_iterator::operator++(int) {
    auto copy = *this;
    ++*this;
    return copy;
}

template <class T>
typename DoubleLinkedList<T>::const_iterator& DoubleLinkedList<T>::const_iterator::operator--() {
    if (!node) return *this;

    if (end_reached) {
        end_reached = false;
    }

    else if (node->previous) {
        node = node->previous.get();
    }

    return *this;
}

template<class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::const_iterator::operator--(int) {
    auto copy = *this;
    --*this;
    return copy;
}

template<class T>
bool DoubleLinkedList<T>::const_iterator::operator==(const_iterator other) const noexcept {
    if (end_reached) return other.end_reached;

    if (other.end_reached) return false;

    return node == other.node;
}

template<class T >
bool DoubleLinkedList<T>::const_iterator::operator!=(const_iterator other) const noexcept {
    return !(*this == other);
}


template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::begin() const {
    return head.get();
}

template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::end() const {
    return {tail, true};
}

template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::cbegin() const {
    return begin();
}

template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::cend() const {
    return end();
}

template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::before_begin() const {
    return { head.get(), true };
}

template <class T>
typename DoubleLinkedList<T>::const_iterator DoubleLinkedList<T>::cbefore_begin() const {
    return before_begin();
}


#endif

Here is the main.cpp file:

#include <iostream>
#include <iterator>
#include <memory>
#include <utility>
#include <stdexcept>
#include <iosfwd>
#include <type_traits>
#include <ostream>
#include "SingleLinkedList.h"
#include "DoubleLinkedList.h"

int main(int argc, const char * argv[]) {

     ///////////////////////////////////////////////////////////////////////
     ///////////////////////////// Double Linked List //////////////////////
     ///////////////////////////////////////////////////////////////////////
     DoubleLinkedList<int> obj;
     obj.push_back(2);
     obj.push_back(4);
     obj.push_back(6);
     obj.push_back(8);
     obj.push_back(10);
     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"---------------displaying all nodes---------------";
     std::cout<<"\n--------------------------------------------------\n";
     std::cout << obj << "\n";

     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"----------------Inserting At Start----------------";
     std::cout<<"\n--------------------------------------------------\n";
     obj.push_front(1);
     std::cout << obj << "\n";

     std::cout << "\n--------------------------------------------------\n";
     std::cout << "-------------Get current size ---=--------------------";
     std::cout << "\n--------------------------------------------------\n";
     std::cout << obj.size() << "\n";

     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"----------------deleting at start-----------------";
     std::cout<<"\n--------------------------------------------------\n";
     obj.pop_front();
     std::cout << obj << "\n";

     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"----------------deleting at end-----------------------";
     std::cout<<"\n--------------------------------------------------\n";
     obj.pop_back();
     std::cout << obj << "\n";

     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"-------------inserting at particular--------------";
     std::cout<<"\n--------------------------------------------------\n";
     obj.insert(obj.cend(),60);
     std::cout << obj << "\n";

     std::cout<<"\n----------------------------------------------------------\n";
     std::cout<<"--------------Deleting after particular position--------------";
     std::cout<<"\n-----------------------------------------------------------\n";
     obj.erase(obj.cend());
     std::cout << obj << "\n";

      obj.search(8) ? printf("yes"):printf("no");

      std::cout << "\n--------------------------------------------------\n";
      std::cout << "--------------Testing copy----------------------------";
      std::cout << "\n--------------------------------------------------\n";
      DoubleLinkedList<int> obj1 = obj;
      std::cout << obj1 << "\n";

    std::cin.get();
}

Answer 1

It is great to see you are really taking reviews seriously and are trying to learn something and improve yourself. That really makes us reviewers like what we are doing. I may not be the best here, but I will still try :)

I very much like your approach with smart pointers (unique_ptr). I do not think that was that trivial as JDługosz stated it. I was also wondering about all the explicit constructors in Node but then spotted the emplace and then it clicked (before going down the rabbit hole of reading the previous reviews).

The main problem with the code is, that it is big and hard to review. I had to copy-paste it to editor to review it. I would personally organise it a bit differently and will tell you why:

Method declaration vs. body

It may appear to be good to first declare the class with all the methods and stuff and then later define bodies for all the methods, maybe because you got used to header + source pair. I have a bit different opinion about this. Splitting it like this, especially when the body is small, not only makes you type a lot more than you need, but it makes it harder to see the logic as well, harder to review, harder to check, harder to maintain. I can understand that the declarative part could serve as a documentation (see what it provides separated from how it does it), but there are other tools for documentation and seeing such things... (so I prefer inline body, most of the time, if it is not too big.)

Documentation

Documenting your code properly is very important and there are good tools to help you, namely doxygen. Try it. I believe you will understand how valuable /// documenting comments can be. ///< inline documentation as well But leave your hints (like // copy constructor) in normal comments or remove these completely (such things should become obvious). But do comment the logic if it is not trivial (maybe with links like this).

The rule of five or three or ... copy and swap

I can understand that you are still learning, but maybe it is time to actually understand what it does, how it does it and what are the alternatives. Just follow the link for full explanation and consider this:

template <class T>
class DoubleLinkedList {
public:
    // see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    DoubleLinkedList& operator=(DoubleLinkedList other) {
        swap(*this, other);
        return *this;
    }
//...
}

do_pop_front()

if (!tail) tail = head.get(); // update tail if list was empty before

Really? This does not sound right. Did you test it? ...and we are back again to documentation: there are many (at least three) versions of doubly-linked lists:

1. Null-terminated on both ends (what your version appears to be)
2. Cyclic (head->previous == tail, tail->next == head, unless empty or you make the very list an empty node, which is easiest to implement)
3. Hybrid (last->next = nullptr, first->prev == last ... this has some advantages, you need only one pointer in the list and you can still easily terminate the for-each loop on nullptr ... but not the reverse_iterator).

Which implementation is it trully? Maybe something else? You should document it:

/// Doubly Linked List with both ends null-terminated
template <class T>
class DoubleLinkedList {

or maybe use ///\brief and some other features doxygen knows (a bit like JavaDoc).

Answer 2

#include <iostream>
#include <iterator>
#include <memory>
#include <utility>
#include <stdexcept>
#include <iosfwd>
#include <type_traits>
#include <ostream>
#include "SingleLinkedList.h"
#include "DoubleLinkedList.h"

Why is all of that in your main.cpp file? You have no includes in your header file. I looked back at your previous implementations and you don't seem to have includes in any of those header files either. I'm guessing here but I believe you are relying on inclusion dependency for your implementation to work. Move your user defined header to the top of the include list and it will break functionality. Header files should be self-contained such that if I want to use your class it won't matter what order I declare it and I won't have to declare it's dependencies.

Your solution should be twofold.

1. Move all the required includes into your header file.
2. Order your includes from local to global scale.

What I mean by 2 is this:

1. h file corresponding to this cpp file (if applicable)
2. headers from the same component,
3. headers from other components,
4. system headers.

Taken verbatim from this answer.

It is also often recommended to sort headers alphabetically within each category.

*You also don't need "SingleLinkedList.h" in your Double linked list example usage file.