Reverse Deque C++.Implementation based on linked list

Question

I have implemented deque through linked list. Below You can see my code:

#include <iostream>
using namespace std;

struct Node
{
    int mData;
    Node* pPrev, *pNext;
    Node()
    {
        this->mData = mData;
        pPrev = pNext = NULL;
    }
    Node(int value)
    {
        mData = value;
        pPrev = pNext = NULL;
    }
};

class Deque
{
private:
    Node *pFront, *pRear;
    int mSize;
public:
    Deque()
    {
        pFront = pRear = NULL;
        mSize = 0;
    }
    void pushFront(int data)
    {
        Node* newNode = new Node(data);
        if (newNode == NULL)
        {
            cout << "Error";
        }
        else
        {
            if (pFront == NULL)
            {
                pRear = pFront = newNode;
            }
            else
            {
                newNode->pNext = pFront;
                pFront->pPrev = newNode;
                pFront = newNode;
            }
            mSize++;
        }
    }
    void pushLast(int data)
    {
        Node* newNode = new Node(data);
        if (newNode == NULL)
        {
            cout << "Error";
        }
        else
        {
            if (pRear == NULL)
            {
                pFront = pRear = newNode;
            }
            else
            {
                newNode->pPrev = pRear;
                pRear->pNext = newNode;
                pRear = newNode;
            }
            mSize++;
        }
    }
    void deleteFront()
    {
        if (isEmpty())
        {
            cout << "Deque is empty";
        }
        else
        {
            Node* temp = pFront;
            pFront = pFront->pNext;

            if (pFront == NULL)
            {
                pRear = NULL;
            }
            else
            {
                pFront->pPrev = NULL;
            }
            free(temp);
            mSize--;
        }
    
    }
    void deleteLast()
    {
        if (isEmpty())
        {
            cout << "Deque is empty";
        }
        else
        {
            Node* temp = pRear;
            pRear = pRear->pPrev;

            if (pRear == NULL)
            {
                pFront = NULL;
            }
            else
            {
                pRear->pNext = NULL;
            }
            free(temp);
            mSize--;
        }
    }
    int getFront() 
    {
        if (isEmpty())
        {
            cout << "Deque is empty";
        }
        else
        {
        return pFront->mData;
        }

    }
    int getLast() 
    {
        if (isEmpty())
        {
            cout << "Deque is empty";
        }
        else
        {
            return pRear->mData;
        }

    }
    void swap() 
    {
        if (isEmpty())
        {
            cout << "Deque is empty";
        }
        else
        {
            Node* temp = pFront;
            while (temp->pNext != NULL) {
                temp = temp->pNext;
            }
            Node* tmp2 = new Node();
            tmp2->mData = temp->mData;
            temp->mData = pFront->mData;
            temp->pNext = NULL;
            pFront->mData = tmp2->mData;
        }

    }
    bool isEmpty()
    {
        return (mSize == 0);
    }
    int getSize()
    {
        return mSize;
    }
    void reverse()
    {
        auto curr = pFront; // current pointer
        Node* prev = NULL; // previous pointer
        while (curr) {
            auto temp = curr->pNext;
            curr->pNext = prev;
            prev = curr;
            pFront = prev;
            curr = temp;
        }
    }
    bool isBelong(int data) 
    {
        Node* temp = pFront;
        while (temp != NULL)
        {
            if (data == temp->mData)
            {
                return true;

            }
            temp = temp->pNext;
        }
        return false;
    }
    void clear()
    {
        pRear = NULL;
        while (pFront != NULL)
        {
            Node* temp = pFront;
            pFront = pFront->pNext;
            delete temp;
        }
        pFront = NULL;
        mSize = 0;
    }
    void show()
    {
        Node* node = pFront;
        while (node != NULL) 
        {
            cout << node->mData << " ";
            node = node->pNext;
        }
    }
};
int main()
{
    Deque deque; int num;
    while (true)
    {
        int choice;
        cout << "\n0.Exit.\n1.Insertion(head).\n2.Insertion(rear).\n3.Deletion(head).\n4.Deletion(rear).\n5.Get head.\n6.Get rear.\n7.Check emptyness.\n8.Check size.\n9.Clear deque.\n10.Swap front and rear.\n11.Check belonginess.\n12.Reverse deque.\n";

        cin >> choice;
        switch (choice) 
        {
        case 0: return 0;
        case 1:
            cout << "Insertion to head - input value : "; cin >> num;
            deque.pushFront(num);
            deque.show();
            system("pause");
            system("cls");
            break;
        case 2:
            cout << "Insertion to rear - input value : "; cin >> num;
            deque.pushLast(num);
            deque.show();
            system("pause");
            system("cls");
            break;
        case 3:

            deque.deleteFront();
            deque.show();
            system("pause");
            system("cls");
            break;
        case 4:
            deque.deleteLast();
            deque.show();
            system("pause");
            system("cls");
            break;
        case 5:
            if (deque.isEmpty())
            {
                cout << "Deque is empty";
            }
            else
            {
            cout << "First element of deque : " << deque.getFront();
            }
            system("pause");
            system("cls");
            break;
        case 6:
            if (deque.isEmpty())
            {
                cout << "Deque is empty";
            }
            else
            {
                cout << "Last element of deque : " << deque.getLast();
            }
            system("pause");
            system("cls");
            break;
        case 7:
            if (deque.isEmpty())
            {
                cout << "Deque is empty";
            }
            else
            {
                cout << "Deque is not empty: "; deque.show();
            }
            system("pause");
            system("cls");
            break;
        case 8:
            cout << "Size of deque : " << deque.getSize();
            system("pause");
            system("cls");
            break;
        case 9:
            deque.clear();
            system("pause");
            system("cls");
            break;
        case 10:
            cout << "Deque before swap: "; deque.show(); cout << endl;
            deque.swap();
            cout << "Deque after swap: "; deque.show(); cout << endl;
            
            system("pause");
            system("cls");
            break;
        case 11:
            cout << "Input number : "; int number; cin >> number;
            if (deque.isBelong(number))
            {
                cout << number << " belongs.\n";
            }
            else
            {
                cout << number << " does not belong.\n";
            }
            system("pause");
            system("cls");
            break;
        case 12:
            cout << "Deque before reverse: ";  deque.show(); cout << endl;
            cout << "Deque after reverse: ";  deque.reverse(); deque.show(); cout << endl;
            system("pause");
            system("cls");
            break;
        default:
            cout << "There is no " << choice << " choice!" << endl;
            system("pause");
            system("cls");
            break;
        }
    }
}

However, reverse() method works inappropriate way. Testing code I noticed that several methods working inappropriate way after reversing:

getRear() - returns old value;
deleteLast() - crashes.

Reverse() method based totally on same method in linked list implementation,as swap(), although it works with some problems.

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Nov 02 '22 at 20:06
An endless loop (`while (true)`), right there in `main`. If there were no other problems, there would still be [UB](https://en.cppreference.com/w/cpp/language/ub) right there. — Jesper Juhl, Nov 02 '22 at 20:08
First step should be to [enable compiler warnings](https://godbolt.org/z/Wc1xWbfT4) and address those major issues. — Drew Dormann, Nov 02 '22 at 20:09
@Qvch This statement this->mData = mData; in the default constructor does not make sense. — Vlad from Moscow, Nov 02 '22 at 20:24
@OP - Advice -- instead of writing menu systems to input the data, you should have written a very simple `main` program that simply calls those functions with hard-coded data to determine if they really work or not. That way, the program is easier to debug, and easier for anyone else to make sense of. Writing menu systems to input the data should only be done *after* you have determined that the linked list/deque works correctly. — PaulMcKenzie, Nov 02 '22 at 20:44
Also, I guess that your C++ course makes it ok to write classes that leak memory? — PaulMcKenzie, Nov 02 '22 at 20:45

Vlad from Moscow · Answer 1 · 2022-11-03T07:01:28.500

I have not looked through all your code though I am sure it has some bugs as for example in the default constructor of the class Node

Node()
{
    this->mData = mData;
    pPrev = pNext = NULL;
}

where uninitialized data member mData is assigned to itself.

Or if you are using the operator new then you should use the operator delete instead of the standard C function free as you are doing

free(temp);

Or another example. Your method reverse does not change the pointer pRear. Or the data member pPrev also is not changed for the pointer curr.

Or the method swap has a memory leak.

And so on.

I will show how the method Reverse can be implemented.

In fact what you need is to swap data members pPrev and pNext for each node of the list.

Here is a demonstration program. I have made some changes for your classes to simplify the implementation of the demonstration program. For example I have made the class Node an internal class of the class Deque (you should also do that.). In any case you can use the idea that is realized in the method Reverse in your own implementation of the method.

#include <iostream>
#include <utility>

class Deque
{
private:
    struct Node
    {
        int mData;
        Node *pPrev, *pNext;
    } *pFront = nullptr, *pRear = nullptr;
    int mSize = 0;

public:
    void Push( int data )
    {
        Node *newNode = new Node{ data, pRear, nullptr };

        if (pFront == nullptr)
        {
            pFront = newNode;
        }
        else
        {
            pRear->pNext = newNode;
        }

        pRear = newNode;
        ++mSize;
    }

    Deque & Reverse()
    {
        if (pFront && pFront->pNext)
        {
            std::swap( pFront, pRear );

            for (Node *current = pFront; current; current = current->pNext)
            {
                std::swap( current->pPrev, current->pNext );
            }
        }

        return *this;
    }

    std::ostream &Show( std::ostream &os = std::cout ) const
    {
        os << mSize << ": ";
        for (Node *current = pFront; current; current = current->pNext)
        {
            os << current->mData << " -> ";
        }

        return os << "null";
    }

    std::ostream &ShowReversed( std::ostream &os = std::cout ) const
    {
        os << mSize << ": ";
        for (Node *current = pRear; current; current = current->pPrev)
        {
            os << current->mData << " -> ";
        }

        return os << "null";
    }
};

int main( void )
{
    Deque deque;
    const int N = 10;

    for (int i = 0; i < N; i++)
    {
        deque.Push( i );
    }

    deque.Show() << '\n';
    deque.ShowReversed() << '\n';
    std::cout << '\n';

    deque.Reverse();

    deque.Show() << '\n';
    deque.ShowReversed() << '\n';
    std::cout << '\n';
}

The program output is

10: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
10: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null

10: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
10: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Unfortunatelly, I need to implement full logic without using stl functions, as You used swap() — Qvch, Nov 06 '22 at 17:32
@Qvch What does prevent you to rewrite calls of the function with your own code?! — Vlad from Moscow, Nov 06 '22 at 17:35

Reverse Deque C++.Implementation based on linked list

1 Answers1