Revisions to Simple Stack and Deque implementation

Rollback to Revision 4

Source Link

edited Jul 18, 2024 at 13:33

pacmaninbw ♦

26.1k
13
47
114

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

Using double sentinels for double-linked (front_, back_) is very convenient and easy to understand code.

The methods present in the classes are quite sufficient for my tasks.

I dont want to share these classes. 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)

And many thanks to Loki Astari, for all advices

I would like to get some advicesreceive your feedback on speeding upimproving the work of these classes, if possiblecode or maybe some comments.

I'm learning C++ for the third month. I will be glad to receive criticism. (sorry for google translate)

#ifndef DLL_HPP
#define DLL_HPP

#include <iostream>

////////////////////////////////////
// DLListDLLNode declaration
//////////////////////////////////  

template <typename DataType>
class DLList {
private:

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

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

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

        DataType data;
        DLLNode* prev;
        DLLNode* next;DLLNode();
    }~DLLNode();    

    typedef DLLNodeDataType Node;data;
    typedef Node*DLLNode* NodePtr;
prev{ nullptr };
  typedef unsigned longDLLNode* longnext{ intnullptr size_t;};
};

    NodePtr front_{ nullptr };////////////////////////////////////
    NodePtr back_{// nullptrDLList };declaration
    size_t size_{////////////////////////////////// 0 };

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(DataType&&const DataType& data);
    void PushFront(DataType&&const DataType& data);
    void PopBack();
    void PopFront();
    DataType&DLLNode<DataType>* Back();
    DataType&DLLNode<DataType>* Front();
    template <typename<class OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    template <typename<class OperationFnc>
    void FromFront(OperationFnc& operation_fnc);
    bool IsEmpty() const;;
    size_tunsigned long long int Size();
 const;   void Print();
private:
    templateNodePtr <typenamefront_{ PrintFnc>nullptr };
    voidNodePtr Print(constback_{ PrintFnc&nullptr print_fnc)};
 const;   unsigned long long int size_{ 0 };
};

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

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

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

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

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

template<typenametemplate<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<typenametemplate<class DataType>
inline DLList<DataType>::~DLList() {
    Clear();
    delete back_;
    delete front_;
}

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

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

template<typenametemplate<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<typenametemplate<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<typenametemplate<class DataType>
inline DataType&DLLNode<DataType>* DLList<DataType>::Back() {
    return IsEmpty() ? back_->data : back_->prev->data;>prev;
}

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

template<typenametemplate<class DataType>
template<typenametemplate<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<typenametemplate<class DataType>
template<typenametemplate<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<typenametemplate<class DataType>
inline bool DLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<typenametemplate<class DataType>
typenameinline DLList<DataType>::size_tunsigned long long int DLList<DataType>::Size() const {
    return size_;
}

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

#endif

#ifndef SLL_HPP
#define SLL_HPP

#include <iostream>

////////////////////////////////////
// SLListSLLNode declaration
//////////////////////////////////  

template <typename<class DataType>
classstruct SLListSLLNode {
privatepublic:
    SLLNode(const SLLNode<DataType>&) = delete;
    SLLNode(SLLNode<DataType>&&) = delete;

    SLLNode();
    ~SLLNode();

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

////////////////////////////////////
    // SLLNodeSLList declaration
    //////////////////////////////////  

  template <class structDataType>
class SLLNodeSLList {
    public:
        DataType& GetData();
    private:
        friend SLList;
        SLLNode(const SLLNode&) = delete;
        SLLNode(SLLNode&&) = delete;

        SLLNode();

        DataType data;
        SLLNode* prev;
    };    

    typedef SLLNodeSLLNode<DataType> Node;
    typedef Node*SLLNode<DataType>* NodePtr;
    typedef unsigned long long int size_t;

    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

    void Clear();
    void PushBack(DataType&&const DataType& data);
    void PopBack();
    DataType&SLLNode<DataType>* Back();
    template <typename<class OperationFnc>
    void FromBack(OperationFnc& operation_fnc);
    bool IsEmpty() const;;
    size_tunsigned long long int Size();
 const;   void Print();
private:
    templateNodePtr <typenameback_{ PrintFnc>nullptr };
    voidunsigned Print(constlong PrintFnc&long print_fnc)int const;size_{ 0 };
};

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

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

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

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

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

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

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

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

template<typenametemplate<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<typenametemplate<class DataType>
inline DataType&SLLNode<DataType>* SLList<DataType>::Back() {
    return IsEmpty() ? back_->data : back_->prev->data;>prev;
}

template<typenametemplate<class DataType>
template<typenametemplate<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<typenametemplate<class DataType>
inline bool SLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<typenametemplate<class DataType>
typenameinline SLList<DataType>::size_tunsigned long long int SLList<DataType>::Size() const {
    return size_;
}

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

#endif

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

Using double sentinels for double-linked (front_, back_) is very convenient and easy to understand code.

The methods present in the classes are quite sufficient for my tasks.

I dont want to share these classes. 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)

And many thanks to Loki Astari, for all advices

I would like to get some advices on speeding up the work of these classes, if possible.

(sorry for google translate)

#ifndef DLL_HPP
#define DLL_HPP

////////////////////////////////////
// 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();

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

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

    NodePtr front_{ nullptr };
    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

    void Clear();
    void PushBack(DataType&& data);
    void PushFront(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() :
    next{ nullptr },
    prev{ nullptr }    
{
    // Default constructor    
}

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

template<typename 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<typename DataType>
inline DLList<DataType>::~DLList() {
    Clear();
    delete back_;
    delete front_;
}

template<typename 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<typename DataType>
inline void DLList<DataType>::PushBack(DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = data;
    NodePtr back_node = back_->prev;
    back_node->next = newbie;
    newbie->prev = back_node;
    newbie->next = back_;
    back_->prev = newbie;
    ++size_;
}

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

template<typename 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<typename 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<typename DataType>
inline DataType& DLList<DataType>::Back() {
    return IsEmpty() ? back_->data : back_->prev->data;
}

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

template<typename DataType>
template<typename 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<typename DataType>
template<typename 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<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_->next;
    while (index != back_) {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->next != back_) {
            print_fnc("<=>");
        }
        index = index->next;
    }    
}

#endif

#ifndef SLL_HPP
#define SLL_HPP

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

template <typename DataType>
class SLList {
private:

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

    struct SLLNode {
    public:
        DataType& GetData();
    private:
        friend SLList;
        SLLNode(const SLLNode&) = delete;
        SLLNode(SLLNode&&) = delete;

        SLLNode();

        DataType data;
        SLLNode* prev;
    };    

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

    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

    void Clear();
    void PushBack(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() :
    prev{ nullptr }    
{
    // Default constructor    
}

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

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

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

template<typename 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<typename DataType>
inline void SLList<DataType>::PushBack(DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = data;
    NodePtr back_node = back_->prev;
    newbie->prev = back_node;
    back_->prev = newbie;
    ++size_;
}

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

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

template<typename DataType>
template<typename 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<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_->prev;
    while (index != nullptr) {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->prev != nullptr) {
            print_fnc("<-");
        }
        index = index->prev;
    }
}

#endif

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)

#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

#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

added 929 characters in body

Source Link

edited Jul 18, 2024 at 11:52

vansergh

313
1
7

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

Using double sentinels for double-linked (front_, back_) is very convenient and easy to understand code.

The methods present in the classes are quite sufficient for my tasks.

I dont want to share these classes. 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)

And many thanks to Loki Astari, for all advices

I would like to receive your feedback on improving the code or maybeget some comments. I'm learning C++ foradvices on speeding up the third month. I will be glad to receive criticismwork of these classes, if possible. (sorry for google translate)

(sorry for google translate)

#ifndef DLL_HPP
#define DLL_HPP

#include <iostream>

////////////////////////////////////
// DLLNodeDLList declaration
//////////////////////////////////  

template <class<typename DataType>
structclass DLLNodeDLList {
publicprivate:
    DLLNode(const DLLNode<DataType>&) = delete;
    DLLNode(DLLNode<DataType>&&) = delete;

    ////////////////////////////////////
    // DLLNode(); declaration
    ~DLLNode();//////////////////////////////////  

    DataTypeclass data;DLLNode {
    DLLNode*public:
 prev{ nullptr }     DataType& GetData();
    DLLNode*private:
 next{ nullptr };     friend DLList;
};        DLLNode(const DLLNode&) = delete;
        DLLNode(DLLNode&&) = delete;

////////////////////////////////////
// DLList declaration
//////////////////////////////////      DLLNode();

template <class DataType>      DataType data;
class DLList       DLLNode* prev;
        DLLNode* next;
    };    

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

    NodePtr front_{ nullptr };
    NodePtr back_{ nullptr };
    size_t size_{ 0 };

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

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

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

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

template<classtemplate<typename DataType>
inline DLLNode<DataType>DataType& DLList<DataType>::DLLNode::GetData() :
    next{ nullptr },
    prev{ nullptr }
{
    // Defaultreturn constructordata;
}

template<classtemplate<typename DataType>
inline DLLNode<DataType>DLList<DataType>::~DLLNodeDLLNode::DLLNode() :
    next{ nullptr },
    data.~DataType();prev{ nullptr }    
{
    // Default constructor    
}

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

template<classtemplate<typename 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<classtemplate<typename DataType>
inline DLList<DataType>::~DLList() {
    Clear();
    delete back_;
    delete front_;
}

template<classtemplate<typename 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<classtemplate<typename DataType>
inline void DLList<DataType>::PushBack(const DataType&DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = DataType(data);data;
    NodePtr back_node = back_->prev;
    back_node->next = newbie;
    newbie->prev = back_node;
    newbie->next = back_;
    back_->prev = newbie;
    ++size_;
}

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

template<classtemplate<typename 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<classtemplate<typename 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<classtemplate<typename DataType>
inline DLLNode<DataType>*DataType& DLList<DataType>::Back() {
    return IsEmpty() ? back_->data : back_->prev;>prev->data;
}

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

template<classtemplate<typename DataType>
template<classtemplate<typename 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<classtemplate<typename DataType>
template<classtemplate<typename 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<classtemplate<typename DataType>
inline bool DLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<classtemplate<typename DataType>
inline unsigned long longtypename intDLList<DataType>::size_t DLList<DataType>::Size() const {
    return size_;
}

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

#endif

#ifndef SLL_HPP
#define SLL_HPP

#include <iostream>

////////////////////////////////////
// SLLNodeSLList declaration
//////////////////////////////////  

template <class<typename DataType>
structclass SLLNodeSLList {
publicprivate:
    SLLNode(const SLLNode<DataType>&) = delete;
    SLLNode(SLLNode<DataType>&&) = delete;

    SLLNode();
    ~SLLNode();

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

////////////////////////////////////
    // SLListSLLNode declaration
    //////////////////////////////////  

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

        SLLNode();

        DataType data;
        SLLNode* prev;
    };    

    typedef SLLNode<DataType>SLLNode Node;
    typedef SLLNode<DataType>*Node* NodePtr;
    typedef unsigned long long int size_t;

    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

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

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

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

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

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

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

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

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

template<classtemplate<typename 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<classtemplate<typename DataType>
inline void SLList<DataType>::PushBack(const DataType&DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = DataType(data);data;
    NodePtr back_node = back_->prev;
    newbie->prev = back_node;
    back_->prev = newbie;
    ++size_;
}

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

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

template<classtemplate<typename DataType>
template<classtemplate<typename 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<classtemplate<typename DataType>
inline bool SLList<DataType>::IsEmpty() const {
    return size_ == 0;
}

template<classtemplate<typename DataType>
inline unsigned long longtypename intSLList<DataType>::size_t SLList<DataType>::Size() const {
    return size_;
}

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

#endif

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)

#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

#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

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

Using double sentinels for double-linked (front_, back_) is very convenient and easy to understand code.

The methods present in the classes are quite sufficient for my tasks.

I dont want to share these classes. 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)

And many thanks to Loki Astari, for all advices

I would like to get some advices on speeding up the work of these classes, if possible.

(sorry for google translate)

#ifndef DLL_HPP
#define DLL_HPP

////////////////////////////////////
// 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();

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

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

    NodePtr front_{ nullptr };
    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

    void Clear();
    void PushBack(DataType&& data);
    void PushFront(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() :
    next{ nullptr },
    prev{ nullptr }    
{
    // Default constructor    
}

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

template<typename 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<typename DataType>
inline DLList<DataType>::~DLList() {
    Clear();
    delete back_;
    delete front_;
}

template<typename 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<typename DataType>
inline void DLList<DataType>::PushBack(DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = data;
    NodePtr back_node = back_->prev;
    back_node->next = newbie;
    newbie->prev = back_node;
    newbie->next = back_;
    back_->prev = newbie;
    ++size_;
}

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

template<typename 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<typename 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<typename DataType>
inline DataType& DLList<DataType>::Back() {
    return IsEmpty() ? back_->data : back_->prev->data;
}

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

template<typename DataType>
template<typename 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<typename DataType>
template<typename 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<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_->next;
    while (index != back_) {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->next != back_) {
            print_fnc("<=>");
        }
        index = index->next;
    }    
}

#endif

#ifndef SLL_HPP
#define SLL_HPP

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

template <typename DataType>
class SLList {
private:

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

    struct SLLNode {
    public:
        DataType& GetData();
    private:
        friend SLList;
        SLLNode(const SLLNode&) = delete;
        SLLNode(SLLNode&&) = delete;

        SLLNode();

        DataType data;
        SLLNode* prev;
    };    

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

    NodePtr back_{ nullptr };
    size_t size_{ 0 };

public:

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

    void Clear();
    void PushBack(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() :
    prev{ nullptr }    
{
    // Default constructor    
}

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

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

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

template<typename 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<typename DataType>
inline void SLList<DataType>::PushBack(DataType&& data) {
    NodePtr newbie = new Node();
    newbie->data = data;
    NodePtr back_node = back_->prev;
    newbie->prev = back_node;
    back_->prev = newbie;
    ++size_;
}

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

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

template<typename DataType>
template<typename 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<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_->prev;
    while (index != nullptr) {
        print_fnc("[");
        print_fnc(index->data);
        print_fnc("]");
        if (index->prev != nullptr) {
            print_fnc("<-");
        }
        index = index->prev;
    }
}

#endif

deleted 31 characters in body

Source Link

edited Jul 15, 2024 at 11:42

toolic

15.8k
6
29
217

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 (don't scold me too much). I will be glad to receive criticism. (sorry for google translate)

P.S. whichWhich methods of class need to make const or any other flags?

edited tags

Link

edited Jul 15, 2024 at 7:19

Sᴀᴍ Onᴇᴌᴀ ♦

29.6k
16
46
203

Loading

added 66 characters in body

Source Link

edited Jul 14, 2024 at 20:34

vansergh

313
1
7

Loading

Source Link

asked Jul 14, 2024 at 19:24

vansergh

313
1
7

Loading

Stack Exchange Network

Return to Question