Doubly_circular_Linklist.cpp

#include <iostream>
#include <windows.h>
using namespace std;

struct Node
{
    int data;
    Node* next;
    Node* back;
};

bool isEmpty(Node* Head);
int InsertAtPosition(Node** Head, Node** Tail, Node* newNode, int listSize, int position);
int DeleteAtPosition(Node** Head, Node** Tail, int listSize, int position);
int DeleteByValue(Node** Head, Node** Tail, int listSize, int Value);
//---------------int Search(Node* Head, int key);

int ClearList(Node** Head, Node** Tail, int listSize);
void SortList(Node** Head, Node** Tail);
void ReverseList(Node** Head, Node** Tail,int listSize);
void PrintList(Node* Head, Node* Tail);

int main()
{
    int choice ; // for user option
    int listSize = 0;   //   How much array is filled ... data size
    int position, value, key;

    Node *Head = NULL, *Tail = NULL;
    Node* newNode = NULL;

    cout << "======================================================" <<endl;
    cout << " \n Menu Driven Program & LIST ADT \n";
    cout << "======================================================" << endl << endl;

    do
    {
        cout << "|------------------------------------|" <<endl
             << "|  1- Insert a value                 |" <<endl
             << "|  2- Delete by position             |" <<endl
             << "|  3- Delete by value                |" <<endl
             << "|  4- Print list                     |" <<endl
             << "|  5- Clear list                     |" <<endl
             << "|  6- Sort list                      |" <<endl
             << "|  7- Reverse list                   |" <<endl
             << "|  8- Exit                           |" <<endl
             << "|------------------------------------|" <<endl;
        cout << "Enter your choice : ";
        cin >> choice;
        // function calls and required working will be added here
        switch(choice)
        {
        case 1:
            cout << "Enter Value to be inserted: ";
            cin >> value;
            cout << "Enter Position for value: ";
            cin >> position;

            // if position is invalid then node must not be created
            // discussed algo part for position validity comes here
            if (position < 1 || position > listSize+1)
            {
                cout << "Invalid position !!! \n Value cannot be inserted!!!\n";
            }
            else
            {
                newNode = new Node;
                newNode->data = value;
                newNode->next = NULL;
                newNode->back = NULL;

                listSize =  InsertAtPosition(&Head, &Tail, newNode, listSize, position);

            }

            system("pause");
            break;

        case 2:
            if(isEmpty(Head))
            {
                cout <<"List is empty\n";
            }
            else
            {
                cout << "Enter Position for value: ";
                cin >> position;

                if (position < 1 || position > listSize)
                {
                    cout << "Invalid position !!! \n Value cannot be deleted!!!\n";
                }
                else
                {
                    listSize =  DeleteAtPosition(&Head, &Tail, listSize, position);
                }
            }
            system("pause");
            break;
        case 3:

            if(isEmpty(Head))
            {
                cout <<"List is empty\n";
            }
            else
            {
                cout << "Enter value for delete: ";
                cin >> value;
                int sizeReturn=DeleteByValue(&Head, &Tail, listSize, value);
                if (sizeReturn==-1)
                {
                    cout << "Value not found !!! \n Value cannot be deleted!!!\n";
                }
                else
                {
                    listSize = sizeReturn;
                    cout<<"Value is deleted.";
                }
            }
            system("pause");
            break;
        case 4:
            if(isEmpty(Head))
            {
                cout<<"List Empty:"<<endl;
            }
            else
            {
               PrintList(Head,Tail);
            }
            system("pause");
            break;

        case 5:
            listSize= ClearList(&Head, &Tail, listSize);
            if(listSize==0)
            {
                cout<<"List is cleared.";
            }
            system("pause");
            break;


        case 6:
            SortList(&Head, &Tail);
           cout <<"List is Sorted.";
            system("pause");
            break;

        case 7:
            ReverseList(&Head, &Tail,listSize);
            cout<<"List is Reversed.";
            system("pause");
            break;


        default:
            exit(0);
            break;
        }
    }
    while (choice != 8 );
    return 0;
}
bool isEmpty(Node* Head)
{
    if(Head == NULL)
        return true;
    else
        return false;
}
int InsertAtPosition(Node** Head, Node** Tail, Node* newNode, int listSize, int position)
{
    if(isEmpty(*Head)) // List is empty
    {
        *Head = newNode;
        *Tail = *Head;
        newNode->back=newNode;//to make a circle same the next and back of only one node
        newNode->next=newNode;
        listSize++;
        return listSize;
    }
    else if(position==1) //At Start in presence of more nodes
    {
        Node *HeadTemp=*Head;
        Node *TailTemp=*Tail;
        newNode->next=*Head;//Maintain the next of new node
        newNode->back=HeadTemp->back;//Maintain the back of new node with tail from previous head's back
        TailTemp->next=newNode;//save the address of head in tail's next
        HeadTemp->back=newNode;//Maintain the back of previous heads back with new node
        *Head=newNode;//place newNode in head
        listSize++;

        return listSize;
    }
    else if(position==listSize+1) // end
    {
        Node *HeadTemp=*Head;
        Node* Current= *Tail;
        newNode->next=Current->next;
        newNode->back=Current;
        Current->next=newNode;
        *Tail=newNode;
        HeadTemp->back=*Tail;
        listSize++;
        return listSize;
    }
    else//mid
    {
        Node *ptr=*Head;
        int nodeCount=1;
        while(nodeCount!=position-1)
        {
            ptr=ptr->next;
            nodeCount=nodeCount+1;

        }
        newNode->next=ptr->next;
        newNode->back=ptr;
        newNode->next->back=newNode;
        ptr->next=newNode;
        listSize++;
        return listSize;
    }
}

int DeleteAtPosition(Node** Head, Node** Tail, int listSize, int position)
{
    Node* Previous = *Head;
    Node* Current = Previous->next;
    int nodeCount = 1;
     if (Previous->next ==Previous->back) //Special case one node
    {
        *Head = NULL;
        *Tail = NULL;
        delete Current;
        listSize--;
        return listSize;
    }
    else if(position==1)//At Start in presence of more nodes
    {
        Node *tempTail=*Tail;
        *Head=Previous->next;
        Previous->next->back=Previous->back;
        tempTail->next=*Head;
        delete Previous;
        listSize--;
        return listSize;
    }
    else if(listSize==position)
    {
        Node *tempTail=*Tail;
        *Tail=tempTail->back;
        Previous->back=*Tail;
        tempTail->back->next=*Head;
        delete tempTail;
        listSize--;
        return listSize;
    }
    else
    {
        Previous=*Tail;
        Current=Previous->next;
        do
        {
            Previous=Current;
            Current=Current->next;
            nodeCount++;
            if(nodeCount==position)
            {
                Previous->next=Current->next;
                Previous->next->back=Previous;
                delete Current;
                listSize--;
                return listSize;
            }
        }while(Current!=*Tail);

    }
}
int DeleteByValue(Node** Head, Node** Tail, int listSize, int value)
{

    Node* Previous = *Head;//Will point head
    Node* Current = Previous->next;
    Node* tailPtr=*Tail;//will point tail
    if (Previous->next ==Previous->back) //Special case one node
    {
        *Head = NULL;
        *Tail = NULL;
        delete Current;
        listSize--;
        return listSize;
    }
    else if(Previous->data==value)//At Start in presence of more nodes
    {
        Node *tem=*Head;
        Node *tempTail=*Tail;
        *Head=tem->next;
        tem->next->back=tem->back;
        tempTail->next=*Head;
        delete tem;
        listSize--;
        return listSize;
    }
    else if(tailPtr->data==value)//end
    {
        Previous=*Tail;
        *Tail=Previous->back;
        Previous->back->next=*Head;
        delete Previous;
        listSize--;
        return listSize;
    }
    else//Mid
    {
        while(Current!=*Tail)
        {
            if(Previous->data==value)
            {
                Previous->next=Current->next;
                Previous->next->back=Previous;
                delete Current;
                listSize--;
                return listSize;
            }
            Previous=Current;
            Current=Current->next;
        }
        return -1;
    }

}
int ClearList(Node** Head, Node** Tail, int listSize)
{
    int rCount=listSize;
    Node *ptr=*Head;
    while(rCount!=0)
    {
        while(ptr!=*Tail)
        {
            ptr=ptr->next;
        }
        delete ptr;
        listSize--;
        rCount--;
        ptr=*Head;
    }
    *Head=NULL;
    *Tail=NULL;
    return listSize;
}


void PrintList(Node *Head,Node *Tail)
{
    Node *ptr=Tail;
    do
    {
        ptr=ptr->next;
        cout<<ptr->data;
    }
    while(ptr!=Tail);
    cout<<endl;
    ptr=Head;
    do
    {
        ptr=ptr->back;
        cout<<ptr->data;
    }
    while(ptr!=Head);
    cout<<endl;
}


void ReverseList(Node** Head, Node** Tail,int listSize)
{
    Node* Start = *Head;
     Node* End   = *Tail;
     int i = 1;
     while(i <= listSize/2)
     {
        swap(Start->data,End->data);
        Start =  Start->next;
        End   =  End->back;
        i++;
     }
}
void SortList(Node** Head, Node** Tail)
{
    Node* previous = *Head;
    Node* Start = *Head;
    do
    {
        Node* Current = *Head;
        do
        {

            if (Current-> data > previous->data )
            {
                swap(previous->data,Current ->data);

            }
            Current = Current ->next;
        }while( Current != *Tail);
        previous = previous->next;

    }while ( previous !=*Tail );
}