Simple Stack and Deque implementation

Question

I implemented a single-linked and double-linked lists (like stack and deque). I would like to receive your feedback on improving the code or maybe some comments. I'm learning C++ for the third month. I will be glad to receive criticism. (sorry for google translate)

https://github.com/vansergh/lib-double-linked-list

#ifndef DLL_HPP
#define DLL_HPP

#include <iostream>

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

template <class DataType>
struct DLLNode {
public:
    DLLNode(const DLLNode<DataType>&) = delete;
    DLLNode(DLLNode<DataType>&&) = delete;

    DLLNode();
    ~DLLNode();

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

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

template <class DataType>
class DLList {
public:
    typedef DLLNode<DataType> Node;
    typedef DLLNode<DataType>* NodePtr;

    DLList(const DLList&) = delete;
    DLList(DLList&&) = delete;
    
    DLList();
    ~DLList();

    void Clear();
    void PushBack(const DataType& data);
    void PushFront(const DataType& data);
    void PopBack();
    void PopFront();
    DLLNode<DataType>* Back();
    DLLNode<DataType>* Front();
    template <class OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    template <class OperationFnc>
    void FromFront(OperationFnc& operation_fnc);
    bool IsEmpty();
    unsigned long long int Size();
    void Print();
private:
    NodePtr front_{ nullptr };
    NodePtr back_{ nullptr };
    unsigned long long int size_{ 0 };
};

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

template<class DataType>
inline DLLNode<DataType>::DLLNode() :
    next{ nullptr },
    prev{ nullptr }
{
    // Default constructor
}

template<class DataType>
inline DLLNode<DataType>::~DLLNode() {
    data.~DataType();
}

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

template<class DataType>
inline DLList<DataType>::DLList() :
    front_{ new Node() },
    back_{ new Node() },
    size_{ 0 }
{
    back_->prev = front_;
    back_->data = DataType();
    front_->next = back_;
    front_->data = DataType();
}

template<class DataType>
inline DLList<DataType>::~DLList() {
    Clear();
    delete back_;
    delete front_;
}

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

template<class DataType>
inline void DLList<DataType>::PushBack(const DataType& data) {
    NodePtr newbie = new Node();
    newbie->data = DataType(data);
    NodePtr back_node = back_->prev;
    back_node->next = newbie;
    newbie->prev = back_node;
    newbie->next = back_;
    back_->prev = newbie;
    ++size_;
}

template<class DataType>
inline void DLList<DataType>::PushFront(const DataType& data) {
    NodePtr newbie = new Node();
    newbie->data = DataType(data);
    NodePtr front_node = front_->next;
    front_node->prev = newbie;
    newbie->next = front_node;
    newbie->prev = front_;
    front_->next = newbie;
    ++size_;
}

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

template<class DataType>
inline void DLList<DataType>::PopFront() {
    if (IsEmpty()) {
        return;
    }
    NodePtr front_node = front_->next;
    front_->next = front_node->next;
    front_node->next->prev = front_;
    delete front_node;
    --size_;
}

template<class DataType>
inline DLLNode<DataType>* DLList<DataType>::Back() {
    return IsEmpty() ? back_ : back_->prev;
}

template<class DataType>
inline DLLNode<DataType>* DLList<DataType>::Front() {
    return IsEmpty() ? front_ : front_->next;
}

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

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

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

template<class DataType>
inline unsigned long long int DLList<DataType>::Size() {
    return size_;
}

template<class DataType>
inline void DLList<DataType>::Print() {
    if (IsEmpty()) {
        std::cout << "List is empty";
        return;
    }
    NodePtr index = front_->next;
    while (index != back_) {
        std::cout << "[" << index->data << "]";
        if (index->next != back_) {
            std::cout << "<=>";
        }
        index = index->next;
    }    
}

#endif

https://github.com/vansergh/lib-single-linked-list

#ifndef SLL_HPP
#define SLL_HPP

#include <iostream>

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

template <class DataType>
struct SLLNode {
public:
    SLLNode(const SLLNode<DataType>&) = delete;
    SLLNode(SLLNode<DataType>&&) = delete;

    SLLNode();
    ~SLLNode();

    DataType data;
    SLLNode* prev{ nullptr };
};

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

template <class DataType>
class SLList {
public:
    typedef SLLNode<DataType> Node;
    typedef SLLNode<DataType>* NodePtr;

    SLList(const SLList&) = delete;
    SLList(SLList&&) = delete;
    
    SLList();
    ~SLList();

    void Clear();
    void PushBack(const DataType& data);
    void PopBack();
    SLLNode<DataType>* Back();
    template <class OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    bool IsEmpty();
    unsigned long long int Size();
    void Print();
private:
    NodePtr back_{ nullptr };
    unsigned long long int size_{ 0 };
};

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

template<class DataType>
inline SLLNode<DataType>::SLLNode() :
    prev{ nullptr }
{
    // Default constructor
}

template<class DataType>
inline SLLNode<DataType>::~SLLNode() {
    data.~DataType();
}

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

template<class DataType>
inline SLList<DataType>::SLList() :
    back_{ new Node() },
    size_{ 0 }
{
    back_->data = DataType();
}

template<class DataType>
inline SLList<DataType>::~SLList() {
    Clear();
    delete back_;
}

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

template<class DataType>
inline void SLList<DataType>::PushBack(const DataType& data) {
    NodePtr newbie = new Node();
    newbie->data = DataType(data);
    NodePtr back_node = back_->prev;
    newbie->prev = back_node;
    back_->prev = newbie;
    ++size_;
}

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

template<class DataType>
inline SLLNode<DataType>* SLList<DataType>::Back() {
    return IsEmpty() ? back_ : back_->prev;
}

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

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

template<class DataType>
inline unsigned long long int SLList<DataType>::Size() {
    return size_;
}

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

#endif

Which methods of class need to make const or any other flags?

Answer 1

ISSUES:

BUG:

Never call the destructor like this:

    data.~DataType();

---

Does Not support all types

template<typename DataType>
class DLLNode
{
    DLLNode();

    DataType data;

   ....

Your node class assumes that DataType is default constructible. Though not technically a bug. I would say that was a bug in the design.

Overview:

Other things I think you should do.

1. Put your code in your own namespace.

Always put your code in its own namespace. This prevent clashes.

2. Naming convention.

Most (non standard) code base use the following convention.

User Defined Types: Start with a capitol letter.
User Objects (and functions / methods): Start with a lower case letter.

The type system is so important to C++ that knowing what a type is really important in all C++ code. Making it easy to distinguish types from objects with this convention is really useful. Please use this convention it will help anybody that reads your code.

Sentinels.

You use Sentinels (not value bearing nodes) in the list. But you do it in strandge way (it seems to work) but I think it can be done better. I have commented on multiple linked list in code review that do the same type of thing. Please have a read on the comments I have left these people.

My first implementation of a linked list in C++
Linked list implemented as classes, not imperative code
Linked list in C++

Things you should think about

The C++ standard library introduces "Concepts". The most relevant here is the Container concept. A linked list is technically a container. It would be nice if your linked list implemented the Container concept. This means you would need to add a few more methods and types internally, but this would also mean that your class would interact with the standard library more seamlessly.

Things you would need to add:

Types:

value_type
reference
const_reference
iterator
const_iterator
difference_type
size_type

Member functions and operators

Copy Constructor
Move Constructor
Copy Assignment
Move Assignment

begin()        // Iterators
end()
cbegin()
cend()

Ordering:     (ie. operator <=> 
Equality Test (ie. operator  == and !=

swap()
size()         Rename Size()
maz_size()
empty()        Rename IsEmpty()

Notes:

I implemented a single-linked and double-linked lists (like stack and deque)

The linked lists are distinct structures from stack and deque. Stack is more of a concept that can be implemented in many ways (linked lists is one technique) while the std::deque is a container with some unique properties that make inserting/deleting into/from the middle less expensive than vector (but its not the same as a linked list).

So please be carefully with terminology.

Code Reveiew

Its probably fine. Most of the time (until its not then cause hours of head scratching).

#ifndef DLL_HPP
#define DLL_HPP

But I would pick a longer more unique header guard. Personally I use the full namespace and the name of the header file. Some tools will auto generate a GUID for you.

---

Is this left over from debugging?

#include <iostream>

---

Sure you have a structure for a node in the list. But do you ever want to expose this node type to the user. Personally I think the answer is no. BUT you may have a use case that is useful for you. BUT if I was on your team I would argue you with you about it and make you really justify leaking an internal abstraction like this.

template <class DataType>
struct DLLNode {
public:
    DLLNode(const DLLNode<DataType>&) = delete;
    DLLNode(DLLNode<DataType>&&) = delete;

    DLLNode();
    ~DLLNode();

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

Personally I would make this a private member of DLList. I would also modify DLList to never expose a NodePtr via the public API.

---

The trouble here is that if you change something you need to change multiple places in the code. Design your code so that if you change one thing the change cascades through the types automatically without you having to touch it.

    typedef DLLNode<DataType> Node;
    typedef DLLNode<DataType>* NodePtr;

I would write like this:

    typedef DLLNode<DataType> Node;
    typedef Node*             NodePtr;

I know this is minor in this situation. But think of a much bigger class where things may be scattered through the declaration. You don't want to have to search for and modify multiple declarations. Modify one thing and all the other types depend on those before and thus get automatically updates.

---

Not sure why you don't want to copy or move the DLList?

    DLList(const DLList&) = delete;
    DLList(DLList&&) = delete;

Seems like a missed opportunity.

---

You have the copy data into the list.

    void PushBack(const DataType& data);
    void PushFront(const DataType& data);

But why can't I move data into the list? If DataType is expensive to copy but cheap to move then I would definitely prefer to be able to move the data into the list.

The change here is relatively simple:

    void PushBack(DataType&& data);
    void PushFront(DataType&& data);

This will support both copy and move operations.

---

OK. I like that pop is void this follows along with the standard implementation (If you don't know why its because it makes it very hard (I would say impossible; but if I did that somebody will come along and explain this convoluted technique were it will work) to implement thread safe operations).

    void PopBack();
    void PopFront();

Which leads me to back() and front(). Why are you exposing the internal implementation DLLNode<DataType>* (which I believe you typedefed to NodePtr!!!).

    DLLNode<DataType>* Back();
    DLLNode<DataType>* Front();

If you look at the standard version you will see that it returns the value_type. I bet you did not do that because what happens with the empty list. This way you can simply return a nullptr. But think of the sue case. This means the user has to check if you returned a nullptr before dereferencing. The other way is to say it is invalid to use back() or front() on an empty list and the user is responsible for checking by using isEmtpy().

Your users do:

   auto val = list.Front();
   if (val == nullptr) {
       std::cout << "Empty List\n";
   }
   else {
       std::cout << "Front: " << *val << "\n";
  }

Users os the standard would do:

   if (list.empty()) {
       std::cout << "Empty List\n";
   }
   else {
       std::cout << "Front: " << list.front() << "\n";
  }

Both are valid. I think the pattern used by the standard is better. But it is one of those arguable points.

---

I don't think this provides any real functionality.

    template <class OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    template <class OperationFnc>
    void FromFront(OperationFnc& operation_fnc);

They are basically pop and apply operation in one go.

    while (!list.IsEmpty()) {
        list.FromBack(doSomething);
    }

While in a standard list you would do:

     while (!list.empty()) {
        doSomething(list.back());
        list.pop_back();
    }

Personally I don't think the extra functionality provides anything to a linked list.

---

These function should all be const.

    bool                   IsEmpty() const;
    unsigned long long int Size()    const;
    void                   Print()   const;
                                  // ^^^^^^

This tells the compiler that the internal state will not change.

---

unsigned long long int

Hide that behind a named type.

1. Its to long.
2. There are some standard typedefs to help you std::size_t.
3. Do you really need unsigned.

The standard committee has long since admitted that making std::size_t an unsigned value was a mistake (it seems logical but because of all the automatic type conversions and stuff it causes nightmares).

Some rules of thumb:

Unless you really really need to don't use unsigned. Then still don't use unsigned use a bigger integer type. Reserve unsigned for flag types.

Don't assume that long is larger than int or long long is larger than long none of these things are guaranteed (guarantees below).

The only standard integer like type worth using is int. Unless you need something specific then always use an integer type with an explicit size (std::int32_t).

Don't use char as an integer. There are funny things about char. Note char could be signed or unsigned depending on system.

Hide your actual type inside your class and expose your own version of the type so if you do need to change it then you change it in one place and they cascades.

class DLList
{
    public:
        using Size = std::int32_t;
        Size size() const;

    ... 
};

---

Never call the destructor like this:

    data.~DataType();

There is a single use case where calling the destructor directly is useful this is not that situation. It is also a very advanced technique so don't use it unless you know.

Anyway. This is almost certainly WRONG. When the object DataNode is destroyed it will automatically destroy all its members (thus call their destructors). So you are effectively calling the destructor twice.

---

From above you have a DLLNode that assumes that the data being held in the list is default constructible.

DLLNode();           // Otherwise you would pass the value 
                     // into the node via the constructor.

DataType data;

You use this in the constructor of the list. To create a Sentinel style node at the beginning of the list. But not in a way I would do it.

1. Normally Sentinel don't actually have a value in them.
2. You don't need to dynamically allocate the Sentinel.
3. You should only have one Sentinel pointed to by both back_ and front_.

See one of the articles I linked above.

template<class DataType>
inline DLList<DataType>::DLList() :
    front_{ new Node() },
    back_{ new Node() },
    size_{ 0 }
{
    back_->prev = front_;
    back_->data = DataType();
    front_->next = back_;
    front_->data = DataType();
}

---

The PushBack() and PushFront() seem identical. I would factor out the identical code into its own function called by both these methods. Leave only the unique code in these functions.

---

Still with PushBack() and PushFront(). These are highly expensive operations.

Next your copy in the data object is very expensive.

    NodePtr newbie = new Node();       // In this line you default constructor a `DataType` object.


    newbie->data = DataType(data);    // In this line you create a copy of the input value.
                                      // Then you assign this newly created copy onto the value in the data node.

So effectively you are calling:

 DataType::DataType();                   // Default construct
 DataType::DataType(DataType const&);    // Copy Construct
 DataType::operator=(DataType const&);   // Assigne

If any of these methods don't exist (explicitly deleted) then your code is going to fail to compile. But also this seems very expensive when it can be done with a single call using the copy constructor.

You should implement this with:

 NodePtr newbie = new Node(dataType);    // Allow the Node to copy construct the input.

You can really simplify your code using an appropriate constructor.

template<typename T>
struct Node
{
    Node*    next;
    Node*    prev;
    T        data;


    Node(T&& data, Node* next, Node* prev)
        : next(next)
        , prev(prev)
        , data(std::move(data))   // Copy or move data into object.
    {
        next->prev = this;
        prev->next = this;
    }
};
        

inline void DLList<DataType>::PushFront(DataType&& data)
{
    // You can pass an rvalue reference forward
    // to the Node so it can then use it internally.
    // Note: front_ is a sentinel so it is always the last object
    //       in the chain.
    NodePtr newbie = new Node(std::move(data), front_, front_->prev);
}

Type Guarantees

https://stackoverflow.com/a/271132/14065