Doubly_Linklist.cpp

#include <iostream>
#include <windows.h>
using namespace std;
//--------->>>AAHHOOO!!!!!!!!!!...................<<<------------------------------
struct Node
{
    int data;
    Node* next;
    Node* back;
};

bool isEmpty(Node* Head,Node* Tail);
int InsertAt(Node** Head, Node** Tail, Node* newNode, int listSize, int position);
int DeleteAt(Node** Head, Node** Tail, int listSize, int position);
int Search(Node* Head, int key);

int ClearList(Node** Head, Node** Tail, int listSize);
void PrintList(Node* Head);
void ReverseList(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 a value                 |" <<endl
             << "|  3- Search a value                 |" <<endl
             << "|  4- Print list                     |" <<endl
             << "|  5- Clear list                     |" <<endl
             << "|  6- Reverse list                   |" <<endl
             << "|  7- 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;

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

                }

                system("pause");
                break;

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

                    if (position < 1 || position > listSize)
                    {
                        cout << "Invalid position !!! \n Value cannot be deleted!!!\n";
                    }
                    else
                    {
                    listSize =  DeleteAt(&Head, &Tail, listSize, position);
                    cout <<"List after delete successfully\n";
                    cout <<"List after delete\n";
                    PrintList(Head);
                    }
                }
                system("pause");
                break;

            case 3:
                 if(isEmpty(Head,Tail))
                {
                    cout <<"List is empty\n";
                }
                else
                {
                    cout << "Enter value for search: ";
                    cin >> key;
                    Search(Head,key);
                }
                     system("pause");
                break;
            case 4:
                if(isEmpty(Head,Tail))
                {
                    cout <<"List is empty\n";
                }
                else
                {
                PrintList(Head);
                }
                system("pause");
                break;

            case 5:
                if(isEmpty(Head,Tail))
                {
                    cout <<"List is empty\n";
                }
                else
                {
                listSize=ClearList(&Head,&Tail,listSize);
                }
                system("pause");
                break;
            case 6:
                 if(isEmpty(Head,Tail))
                {
                    cout <<"List is empty\n";
                }
                else
                {
                ReverseList(&Head,&Tail);
                }
                cout <<"Now List is reverse\n";
                PrintList(Head);
                system("pause");
                break;

            default:
                exit(0);
                break;
        }
    }while (choice != 8 );
    return 0;
}
bool isEmpty(Node* Head,Node* Tail)
{
    if(Head == NULL)
        return true;
    else
        return false;
}


int InsertAt(Node** Head, Node** Tail, Node* newNode, int listSize, int position)
{
    if(*Head == NULL) // List is empty special case
    {
        newNode->next=NULL;
        newNode->back=NULL;
        *Head = newNode;
        *Tail = newNode;
        listSize++;
        cout << "Insert value special case!\n";

    }
    else if(position==1)// Start            //----------------------->>>>>> List non empty
      {
        newNode->next=*Head;
        (*Head)->back=newNode;
        newNode->back=NULL;
        *Head=newNode;
        listSize++;
        cout << "Insert value start case!\n";
      }
     else if(position==listSize+1)//-------------->> end
      {
        (*Tail)->next=newNode;
        newNode->next=NULL;
        newNode->back=*Tail;
        *Tail=newNode;
        listSize++;
        cout << "Insert value end case!\n";

      }
      else//--------------------->>>>mid case
      {
           Node* prev = *Head;
           Node* current = prev->next;
           int nodeCount = 1;
           while(current!=NULL)
           {
               if(position==nodeCount)
               {
                  /** prev->next=newNode;
                  newNode->back=prev;
                  newNode->next=current;
                  current->back=newNode;
                 **/

                    newNode ->next = current;
                (current->back)->next = newNode;
                newNode->back = current->back;
                current->back = newNode;


               }
               prev=prev->next;
               current=prev;
               nodeCount++;
           }
        listSize++;
        cout << "Insert value mid case!\n";
      }
      return listSize;
}

void PrintList(Node *Head)
{
  Node* Current = Head;
    int position = 1;
    cout << "Value\t\tPosition" << endl;
    while ( Current != NULL)
    {
        cout << Current -> data <<"\t\t"<<position<<endl;
        position++;
        Current = Current ->next;
    }
}

int DeleteAt(Node** Head, Node** Tail, int listSize, int position)
{

  if((*Head)->next==NULL)//---------->>delete at special case
  {
      Node* current = *Head;
      current= *Head;
      *Tail=*Head=NULL;
      delete current;
      listSize--;
       cout <<"delete first node special case\n";

  }
  else if(position==1)//---------->>delete at first node
  {
   Node* prev = *Head;
   Node* current = prev->next;
   current->back=NULL;
   *Head=current;
   delete prev;
    listSize--;
    cout <<"delete first node successfully.\n";

  }
  else if(position==listSize)//---------->>delete at last node case
  {
   Node* current = *Tail;
   Node* prev = current->back;
   prev->next=NULL;
   *Tail=prev;

     listSize--;
    cout <<"delete last node successfully.\n";

  }
  else//---------->>delete at mid case node
  {
    Node* prev = *Head;
    Node* current = prev->next;
    int nodeCount=1;
    while(current!=*Tail)
    {
       if(position==nodeCount)
       {
           prev->next=(current->next)->back;
           (current->next)->back=prev->next;
       }
       nodeCount++;
       current=current->next;
       prev=current;
    }
     listSize--;
    cout <<"delete mid node successfully.\n";
  }
  return listSize;
}
int Search(Node* Head, int key)
{
    Node *current = Head;
    int nodeCount = 1;
    while(current!=NULL)
    {
        if(current->data==key)
        {
            cout << "Value\t\tPosition" << endl;
            cout << current -> data <<"\t\t"<<nodeCount<<endl;
        }
        current=current->next;
        nodeCount++;
    }
    return key;
}

int ClearList(Node** Head, Node** Tail, int listSize) //------------->>problem
{

    Node* Current = *Head;
                while( Current != NULL)
                {
                Node* ptr = Current;

                Current = Current ->next;
                delete ptr;
                listSize--;

            }
            *Head = NULL;
            *Tail = NULL;
    cout <<"List is clear successfully!!!....\n";
    return listSize;
}
void ReverseList(Node** Head, Node** Tail)
{
     cout <<"successfully.\n";
    Node* Current = *Head;
    Node* prev = NULL;
    Node* next = NULL;
    while(Current!=NULL)
    {
        next=Current->next;
        Current->next=prev;
        prev=Current;
        Current=next;
    }
    *Head=prev;

}