Simple Stack and Deque implementation (v2)

Question

My previous post: Simple Stack and Deque implementation

I have implemented 2 classes for my project similar to stack and deque. This is my second attempt to get advice and evaluation of my code. Maybe something can be accelerated, improved, or I made mistakes somewhere. Please rate and give your review of these 2 classes.

• Using double sentinels for double-linked (front_, back_) is very convenient and easy to use for me.
• The methods present in the classes are quite sufficient for my tasks. I need these methods only
• I don't want to share these classes for public use. They are for personal use only. So I don't need to adapt them to the standard library, concepts, put in namespace, change #ifndef guard, and other
• The code style corresponds to Google's code style (https://google.github.io/styleguide/cppguide.html) If not? tell me where
• And many thanks to Loki Astari, and other people who guided me

GitHub Repository for Stack (single-linked list): https://github.com/vansergh/lib-single-linked-list

#ifndef SLL_HPP
#define SLL_HPP

#include <initializer_list>

////////////////////////////////////
// SLList declaration
//////////////////////////////////  

template <typename DataType>
class SLList {
private:

    ////////////////////////////////////
    // SLLNode declaration
    //////////////////////////////////  

    class SLLNode {
    public:
        DataType& GetData();
    private:
        friend SLList;

        SLLNode(const SLLNode&) = delete;
        SLLNode(SLLNode&&) = delete;
        SLLNode() = delete;

        SLLNode(DataType&& in_data, SLLNode* in_prev);
        SLLNode(const DataType& in_data, SLLNode* in_prev);

        DataType data;
        SLLNode* prev;
    };

    typedef SLLNode Node;
    typedef Node* NodePtr;
    typedef unsigned long long int size_t;

    size_t size_{ 0 };
    DataType empty_;
    NodePtr back_;

    NodePtr CopyNodes_(const SLList& other);
    NodePtr InitFromList_(std::initializer_list<DataType> init_list);

public:

    SLList();
    SLList(std::initializer_list<DataType> init_list);
    SLList(const SLList& other);
    SLList(SLList&& other);
    ~SLList();

    SLList& operator=(const SLList& other);
    SLList& operator=(SLList&& other);

    void Clear();
    void PushBack(DataType&& data);
    void PushBack(const DataType& data);
    void PopBack();
    DataType& Back();
    template <typename OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    bool IsEmpty() const;
    size_t Size() const;
    template <typename PrintFnc>
    void Print(const PrintFnc& print_fnc) const;
};

////////////////////////////////////
// SLLNode defenition
//////////////////////////////////  

template<typename DataType>
inline DataType& SLList<DataType>::SLLNode::GetData() {
    return data;
}

template<typename DataType>
inline SLList<DataType>::SLLNode::SLLNode(DataType&& in_data, SLList<DataType>::SLLNode* in_prev) :
    data{ std::move(in_data) },
    prev{ in_prev }
{
    // Parametrized move constructor
}

template<typename DataType>
inline SLList<DataType>::SLLNode::SLLNode(const DataType& in_data, SLList<DataType>::SLLNode* in_prev) :
    data{ DataType(in_data) },
    prev{ in_prev }
{
    // Parametrized copy constructor
}

////////////////////////////////////
// SLList defenition
//////////////////////////////////  

template<typename DataType>
inline typename SLList<DataType>::NodePtr SLList<DataType>::CopyNodes_(const SLList& other) {
    if (other.IsEmpty()) {
        return nullptr;
    }   
    NodePtr index = other.back_->prev;
    back_ = new Node(other.back_->data, nullptr);
    while (index != nullptr) {
        back_->prev = new Node(index->data, nullptr);
        index = index->prev;
    }
    return back_;
}

template<typename DataType>
inline typename SLList<DataType>::NodePtr SLList<DataType>::InitFromList_(std::initializer_list<DataType> init_list) {
    back_ = nullptr;
    for (auto it = init_list.begin(); it != init_list.end(); ++it) {
        PushBack(*it);
    }
    return back_;
}

template<typename DataType>
inline SLList<DataType>::SLList() :
    size_{ 0 },
    empty_{ DataType() },
    back_{ nullptr }
{
    // Default constructor
}

template<typename DataType>
inline SLList<DataType>::SLList(std::initializer_list<DataType> init_list) :
    size_{ 0 },
    empty_{ DataType() },
    back_{ InitFromList_(init_list) }
{
    // std::initializer_list constructor
}

template<typename DataType>
inline SLList<DataType>::SLList(const SLList& other) :
    size_{ other.size_ },
    empty_{ DataType() },
    back_{ CopyNodes_(other) }
{
    // Copy constructor
}

template<typename DataType>
inline SLList<DataType>::SLList(SLList&& other) :
    size_{ other.size_ },
    empty_{ DataType() },
    back_{ other.back_ }
{
    other.back_ = nullptr;
    other.Clear();
}

template<typename DataType>
inline SLList<DataType>::~SLList() {
    Clear();
}

template<typename DataType>
inline SLList<DataType>& SLList<DataType>::operator=(const SLList& other) {
    if (this == &other) {
        Clear();
        size_ = other.size_;
        back_ = CopyNodes_(other);
    }
    return *this;
}

template<typename DataType>
inline SLList<DataType>& SLList<DataType>::operator=(SLList&& other) {
    if (this != &other) {
        Clear();
        back_ = other.back_;
        size_ = other.size_;
        other.back_ = nullptr;
        other.Clear();
    }
    return *this;
}

template<typename DataType>
inline void SLList<DataType>::Clear() {
    NodePtr current{ nullptr };
    while (back_ != nullptr) {
        current = back_;
        back_ = back_->prev;
        delete current;
    }
    size_ = 0;
}

template<typename DataType>
inline void SLList<DataType>::PushBack(DataType&& data) {
    back_ = new Node(std::move(data), back_);
    ++size_;
}

template<typename DataType>
inline void SLList<DataType>::PushBack(const DataType& data) {
    back_ = new Node(data, back_);
    ++size_;
}

template<typename DataType>
inline void SLList<DataType>::PopBack() {
    if (IsEmpty()) {
        return;
    }
    NodePtr back_node = back_->prev;
    delete back_;
    back_ = back_node;
    --size_;
}

template<typename DataType>
inline DataType& SLList<DataType>::Back() {
    return IsEmpty() ? empty_ : back_->data;
}

template<typename DataType>
template<typename OperationFnc>
inline void SLList<DataType>::FromBack(OperationFnc& operation_fnc) {
    NodePtr index{ back_ };
    NodePtr current{ nullptr };
    while (index != nullptr) {
        current = index;
        index = index->prev;
        operation_fnc(current);
    }
}

template<typename DataType>
inline bool SLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<typename DataType>
typename SLList<DataType>::size_t SLList<DataType>::Size() const {
    return size_;
}

template<typename DataType>
template<typename PrintFnc>
inline void SLList<DataType>::Print(const PrintFnc& print_fnc) const {
    if (IsEmpty()) {
        print_fnc("List is empty");
        return;
    }
    NodePtr index = back_;
    while (index != nullptr) {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->prev != nullptr) {
            print_fnc("<-");
        }
        index = index->prev;
    }
}

#endif

GitHub Repository for Deque (double-linked list): https://github.com/vansergh/lib-double-linked-list

#ifndef DLL_HPP
#define DLL_HPP

#include <initializer_list>

// Push type (push back or push front) for initializer_list constructor
enum class InitListPushType { BACK, FRONT };

////////////////////////////////////
// DLList declaration
//////////////////////////////////  

template <typename DataType>
class DLList {
private:

    ////////////////////////////////////
    // DLLNode declaration
    //////////////////////////////////  

    class DLLNode {
    public:
        DataType& GetData();        
    private:
        friend DLList;

        DLLNode(const DLLNode&) = delete;
        DLLNode(DLLNode&&) = delete;
        DLLNode() = delete;

        DLLNode(DataType&& in_data, DLLNode* in_prev, DLLNode* in_next);
        DLLNode(const DataType& in_data, DLLNode* in_prev, DLLNode* in_next);

        DataType data;
        DLLNode* prev;
        DLLNode* next;
    };

    typedef DLLNode Node;
    typedef Node* NodePtr;
    typedef unsigned long long int size_t;

    size_t size_{ 0 };
    DataType empty_;
    NodePtr front_;
    NodePtr back_;

    NodePtr CopyNodes_(const DLList& other);
    NodePtr InitFromList_(std::initializer_list<DataType> init_list, InitListPushType push_type);    

public:

    DLList();
    DLList(std::initializer_list<DataType> init_list, InitListPushType push_type = InitListPushType::BACK);
    DLList(const DLList& other);
    DLList(DLList&& other);
    ~DLList();

    DLList& operator=(const DLList& other);
    DLList& operator=(DLList&& other);

    void Clear();
    void PushBack(DataType&& data);
    void PushBack(const DataType& data);
    void PushFront(DataType&& data);
    void PushFront(const DataType& data);
    void PopBack();
    void PopFront();
    DataType& Back();
    DataType& Front();
    template <typename OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    template <typename OperationFnc>
    void FromFront(OperationFnc& operation_fnc);
    bool IsEmpty() const;
    size_t Size() const;
    template <typename PrintFnc>
    void Print(const PrintFnc& print_fnc) const;
};

////////////////////////////////////
// DLLNode defenition
//////////////////////////////////  

template<typename DataType>
inline DataType& DLList<DataType>::DLLNode::GetData() {
    return data;
}

template<typename DataType>
inline DLList<DataType>::DLLNode::DLLNode(DataType&& in_data, DLList<DataType>::DLLNode* in_prev, DLList<DataType>::DLLNode* in_next) :
    data{ std::move(in_data) },
    next{ in_prev },
    prev{ in_next }
{
    if (in_prev != nullptr) {
        in_prev->prev = this;    
    }
    if (in_next != nullptr) {
        in_next->next =  this;    
    }
}

template<typename DataType>
inline DLList<DataType>::DLLNode::DLLNode(const DataType& in_data, DLList<DataType>::DLLNode* in_prev, DLList<DataType>::DLLNode* in_next) :
    data{ DataType(in_data) },
    next{ in_prev },
    prev{ in_next }
{
    if (in_prev != nullptr) {
        in_prev->prev = this;    
    }
    if (in_next != nullptr) {
        in_next->next =  this;    
    }
}

////////////////////////////////////
// DLList defenition
//////////////////////////////////  

template<typename DataType>
inline typename DLList<DataType>::NodePtr DLList<DataType>::CopyNodes_(const DLList& other) {
    back_ = nullptr;
    if (other.IsEmpty()) {
        return nullptr;
    }
    NodePtr index = other.back_;

    back_ = new Node(index->data, nullptr, nullptr);
    front_ = back_;
    front_->next = back_;
    front_->prev = back_;
    back_->next = front_;
    back_->prev = front_;
    index = index->prev;

    while (index != other.back_) {
        back_ = new Node(index->data, front_, back_);      
        index = index->prev;
    }

    return front_;
}

template<typename DataType>
inline typename DLList<DataType>::NodePtr DLList<DataType>::InitFromList_(std::initializer_list<DataType> init_list, InitListPushType push_type) {
    front_ = nullptr;
    back_ = nullptr;
    if (push_type == InitListPushType::BACK) {
        for (auto it = init_list.begin(); it != init_list.end(); ++it) {
            PushBack(*it);
        }
    }
    else {
        for (auto it = init_list.begin(); it != init_list.end(); ++it) {
            PushFront(*it);
        }        
    }
    return front_;
}

template<typename DataType>
inline DLList<DataType>::DLList() :
    size_{ 0 },
    empty_{ DataType() },
    front_{ nullptr },
    back_{ nullptr }
{
    // Default constructor
}

template<typename DataType>
inline DLList<DataType>::DLList(std::initializer_list<DataType> init_list, InitListPushType push_type) :
    size_{ 0 },
    empty_{ DataType() },
    front_{ InitFromList_(init_list, push_type) }
{
    // std::initializer_list constructor
}

template<typename DataType>
inline DLList<DataType>::DLList(const DLList& other) :
    size_{ other.size_ },
    empty_{ DataType() },
    front_{ CopyNodes_(other) }
{
    // Copy constructor
}

template<typename DataType>
inline DLList<DataType>::DLList(DLList&& other) :
    size_{ other.size_ },
    empty_{ DataType() },
    front_{ other.front_ },
    back_{ other.back_ }
{
    other.back_ = nullptr;
    other.front_ = nullptr;
    other.Clear();
}

template<typename DataType>
inline DLList<DataType>::~DLList() {
    Clear();
}

template<typename DataType>
inline DLList<DataType>& DLList<DataType>::operator=(const DLList& other) {
    if (this == &other) {
        Clear();
        size_ = other.size_;
        front_ = CopyNodes_(other);
    }
    return *this;
}

template<typename DataType>
inline DLList<DataType>& DLList<DataType>::operator=(DLList&& other) {
    if (this != &other) {
        Clear();
        front_ = other.front_;
        back_ = other.back_;
        size_ = other.size_;
        other.front_ = nullptr;
        other.back_ = nullptr;
        other.Clear();
    }
    return *this;
}

template<typename DataType>
inline void DLList<DataType>::Clear() {
    if (IsEmpty()) {
        return;
    }
    if (size_ > 1) {
        NodePtr index = front_;
        NodePtr current{ nullptr };
        while (index != back_) {
            current = index;
            index = index->next;
            delete current;
        }        
    }
    delete back_;
    front_ = nullptr;
    back_ = nullptr;    
    size_ = 0;
}

template<typename DataType>
inline void DLList<DataType>::PushBack(DataType&& data) {
    back_ = new Node(std::move(data), front_, back_);
    if (size_ == 0) {
        front_ = back_;
        front_->next = back_;
        front_->prev = back_;
        back_->next = front_;
        back_->prev = front_;
    }
    ++size_;
}

template<typename DataType>
inline void DLList<DataType>::PushBack(const DataType& data) {
    back_ = new Node(data, front_, back_);
    if (size_ == 0) {
        front_ = back_;
        front_->next = back_;
        front_->prev = back_;
        back_->next = front_;
        back_->prev = front_;
    }
    ++size_;    
}

template<typename DataType>
inline void DLList<DataType>::PushFront(DataType&& data) {
    front_ = new Node(std::move(data), front_, back_);
    if (size_ == 0) {
        back_ = front_;
        back_->next = front_;
        back_->prev = front_;
        front_->next = back_;
        front_->prev = back_;
    }
    ++size_;
}

template<typename DataType>
inline void DLList<DataType>::PushFront(const DataType& data) {
    front_ = new Node(data, front_, back_);
    if (size_ == 0) {
        back_ = front_;
        back_->next = front_;
        back_->prev = front_;
        front_->next = back_;
        front_->prev = back_;
    }
    ++size_;    
}

template<typename DataType>
inline void DLList<DataType>::PopBack() {
    if (IsEmpty()) {
        return;
    }
    if (size_ == 1) {
        delete back_;
        back_ = nullptr;
        front_ = nullptr;
    }
    else {
        NodePtr back_prev = back_->prev;
        back_prev->next = back_->next;
        back_->next->prev = back_prev;
        delete back_;
        back_ = back_prev;
    }
    --size_;
}

template<typename DataType>
inline void DLList<DataType>::PopFront() {
    if (IsEmpty()) {
        return;
    }
    if (size_ == 1) {
        delete front_;
        back_ = nullptr;
        front_ = nullptr;
    }
    else {
        NodePtr front_next = front_->next;
        front_next->prev = front_->prev;
        front_->prev->next = front_next;
        delete front_;
        front_ = front_next;
    }
    --size_;
}

template<typename DataType>
inline DataType& DLList<DataType>::Back() {
    return IsEmpty() ? empty_ : back_->data;
}

template<typename DataType>
inline DataType& DLList<DataType>::Front() {
    return IsEmpty() ? empty_ : front_->data;
}

template<typename DataType>
template<typename OperationFnc>
inline void DLList<DataType>::FromBack(OperationFnc& operation_fnc) {
    if (IsEmpty()) {
        return;
    }
    NodePtr index = back_;
    do {
        operation_fnc(index);
        index = index->prev;
    } while (index != back_);
}

template<typename DataType>
template<typename OperationFnc>
inline void DLList<DataType>::FromFront(OperationFnc& operation_fnc) {
    if (IsEmpty()) {
        return;
    }
    NodePtr index = front_;
    do {
        operation_fnc(index);
        index = index->next;
    } while (index != front_);
}

template<typename DataType>
inline bool DLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<typename DataType>
typename DLList<DataType>::size_t DLList<DataType>::Size() const {
    return size_;
}

template<typename DataType>
template<typename PrintFnc>
inline void DLList<DataType>::Print(const PrintFnc& print_fnc) const {
    if (IsEmpty()) {
        print_fnc("List is empty");
        return;
    }
    NodePtr index = front_;
    do {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->next != front_) {
            print_fnc("<=>");
        }
        index = index->next;
    } while (index != front_);
}

#endif

Answer 1

I don't know why you need such a stack and deque or why you wouldn't use what STL has or any other opensource library that has implementation of these. Reinventing the wheel for such basic classes isn't really a good exercise for beginners as it requires a niche knowledge that typically isn't too helpful.

In STL stack is implemented by adapting a vector while deque is usually implemented as an array of dynamically allocated fixed-sized containers. Some application have a different alternatives for deque which store data contiguously at the cost of some unnecessary features. There is a reason why it is not implemented as a linked list and the reason is that linked list is awfully slow and bad for memory fragmentation. As each node requires a memory allocation and eventual deallocation (both operations are slow) and unlike contiguous data accessing and working with such a fragmented array is also slow. Say, incase of contiguous data, when one goes through all elements consequently, the following elements a frequently are either preloaded or even come automatically with the cachelines. In case of list, the location of the next element needs to be figured out dynamically.

Linked lists have their uses - like in cases when one works with non-movable objects or when user doesn't what them to be moved for whatever reason. Which is sometimes the case but it is not a common requirement and is frequently wasteful.

Issues with writing style

You should use standard naming convention. Say if you have a std::vector<int> vec; you can traverse over all elements via convenient instructions for(int x : vec) {...}. This won't work with your code as it requires standard member functions begin/end to return iterator begin and end sentinel. There are other standart functions like push_back that with back_inserter and if you ever want to use the C++20 ranges library your class will need to satisfy a bunch of other requirements - starting with having a size member function.

Function Declaration

template <typename OperationFnc>
void FromBack(OperationFnc& operation_fnc);

template <typename OperationFnc>
void FromFront(OperationFnc& operation_fnc);

You should use here OperationFnc&& instead of OperationFnc& as in the latter user cannot pass a temporary:

data.FromFront([](auto) { ... }); // will fail to compile with `OperationFnc&`

Also if it properly supported begin/end functions and ranges library you wouldn't need these functions. You'd be able to access it like this:

for(auto&& data : my_stack) {...}

for(auto&& data : my_deque) {...}

for(auto&& data_in_reverse : std::views::reverse(my_deque)) {...}

And it if ranges library is not in the scope or you find it too much a hassle to support it, you can write a simple wrapper for the reversed iterators of the deque.

Code Guards

For most cases it is better to have #pragma once rather than include guards. See Wikipedia link for the discussion https://en.wikipedia.org/wiki/Pragma_once