doubly_linked_list

#include<bits/stdc++.h>

using namespace std;

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

Node *head = NULL;
Node *last = NULL;

void createList(int n)
{
    for(int i=1; i<=n; i++)
    {
        Node * newNode = (Node*) malloc(sizeof(Node));
        int val;
        cout<<"Node "<<i<<": ";
        cin>>val;
        newNode->data = val;
        newNode->next= NULL;
        newNode->prev = NULL;

        if(head == NULL)
        {
            head = newNode;
            last = head;
        }
        else
        {
            last->next = newNode;
            newNode->prev = last;
            last = newNode;
        }
    }
    cout<<"\n\n";
}

void insertFirst(int val)
{
    Node * newNode = (Node*) malloc(sizeof(Node));
    newNode->data = val;
    newNode->next= NULL;
    newNode->prev = NULL;

    if(head == NULL)
    {
        head = newNode;
        last = head;
    }
    else
    {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
        printf("Successfully inserted!\n\n");
    }
}

void insertLast(int val)
{
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = NULL;
    newNode->prev = NULL;
    if(head == NULL)
    {
        head = newNode;
        last = head;
    }
    else
    {
        newNode->prev = last;
        last->next = newNode;
        last = newNode;
        printf("Successfully inserted!\n\n");
    }
}

void insertAt(int pos,int val)
{
    if(pos==1)
    {
        insertFirst(val);
        return;
    }
    Node * newNode = (Node*) malloc(sizeof(Node));
    newNode->data = val;
    newNode->next= NULL;
    newNode->prev = NULL;

    Node *curNode = head;

    for(int i=2; i<pos; i++)
    {
        curNode = curNode -> next;
        if(curNode == NULL)
        {
            cout<<"Insertion not possible\n";
            return;
        }
    }
    if(curNode == last) insertLast(val);
    else
    {
        newNode->next = curNode->next;
        newNode->prev = curNode;
        curNode->next->prev = newNode;
        curNode->next = newNode;
        printf("Successfully inserted!\n\n");
    }


}

void deletefirst()
{
    if(head == NULL)
    {
        cout<<"No list is created!\n";
    }
    else
    {
        if(head->next==NULL)
        {
            head = NULL;
            last = NULL;
            return;
        }
        Node *curNode = head;
        head=head->next;
        head->prev = NULL;
        free(curNode);
        printf("Successfully Deleted!\n\n");
    }
}

void deleteLast()
{
    if(head == NULL)
    {
        cout<<"No list is created!\n";
    }
    else
    {
        if(last->prev==NULL)
        {
            head = NULL;
            last = NULL;
            return;
        }
        Node *curNode = last;
        last=last->prev;
        last->next = NULL;
        free(curNode);
        printf("Successfully Deleted!\n\n");
    }
}


void deleteAt(int pos)
{
    if(head==NULL)
    {
        cout<<"No list exists!\n";
        return;
    }
    Node *curNode = head;
    for(int i=1; i<pos; i++)
    {
        curNode = curNode->next;
        if(curNode == NULL)
        {
            cout<<"Deletion not possible\n";
            return;
        }
    }
    if(curNode==head) deletefirst();
    else if(curNode==last) deleteLast();
    else
    {
        curNode->prev->next = curNode->next;
        curNode->next->prev = curNode->prev;
        free(curNode);
        printf("Successfully Deleted!\n\n");
    }
}

void printFromHead()
{
    if(head == NULL)
    {
        cout<<"No list!!\n";
    }
    else
    {
        cout<<"List from Head: ";
        Node *curNode = head;
        while(curNode != NULL)
        {
            cout<<curNode->data<<" ";
            curNode = curNode -> next;
        }
        cout<<"\n\n";
    }
}

void printFromLast()
{
    if(head == NULL)
    {
        cout<<"No list!!\n";
    }
    else
    {
        cout<<"List from Last: ";
        Node *curNode = last;
        while(curNode != NULL)
        {
            cout<<curNode->data<<" ";
            curNode = curNode -> prev;
        }
        cout<<"\n\n";
    }
}

int searchFromHead(int val)
{
    if(head==NULL)
    {
        return -1;
    }
    else
    {
        Node *curNode = head;
        int index = 1;
        while (curNode != NULL)
        {
            if(curNode->data == val)
            {
                return index;
            }
            index++;
            curNode = curNode->next;
        }
        return 0;
    }
}

int searchFromLast(int val)
{
    if(head==NULL)
    {
        return -1;
    }
    else
    {
        Node *curNode = last;
        int index = 1;
        while (curNode != NULL)
        {
            if(curNode->data == val)
            {
                return index;
            }
            index++;
            curNode = curNode->prev;
        }
        return 0;
    }
}

void freeTheList()
{
    Node *curNode = head;
    while(head != NULL)
    {
        curNode = head;
        head = head->next;
        free(curNode);
    }
}

int main(){
    printf("Enter the number of elements in the list: ");
    int n;
    scanf("%d",&n);
    printf("Create the list\n");
    createList(n);
    printFromHead();
    printFromLast();
    printf("A doubly linked list is being created!\n");

    while(1)
    {
        printf("1. Insert First\n");
        printf("2. Insert Last\n");
        printf("3. Insert At\n");
        printf("4. Delete First\n");
        printf("5. Delete Last\n");
        printf("6. Delete At\n");
        printf("7. Search From Head\n");
        printf("8. Search From Last\n");
        printf("9. Print List From Head\n");
        printf("10. Print List From Last\n");
        printf("11. Exit\n");
        printf("Enter Choice: ");
        int choice;
        scanf("%d",&choice);
        printf("\n");
        if(choice == 1)
        {
            printf("Enter the element: ");
            int val;
            scanf("%d",&val);
            insertFirst(val);
        }
        else if(choice == 2)
        {
            printf("Enter the element: ");
            int val;
            scanf("%d",&val);
            insertLast(val);
        }
        else if(choice == 3)
        {
            printf("Enter the position: ");
            int pos;
            scanf("%d",&pos);
            printf("Enter the element: ");
            int val;
            scanf("%d",&val);
            insertAt(pos,val);

        }
        else if (choice == 4) deletefirst();
        else if (choice == 5) deleteLast();
        else if (choice == 6)
        {
            printf("Enter the position: ");
            int pos;
            scanf("%d",&pos);
            deleteAt(pos);
        }
        else if(choice == 7)
        {
            printf("Enter the value: ");
            int val;
            scanf("%d",&val);
            int pos = searchFromHead(val);
            if(pos == -1) cout<<"No list exists!\n";
            else if(pos) cout<<"Position from Head: "<<pos<<"\n\n";
            else cout<<"Item not found in the list\n";
        }
        else if(choice == 8)
        {
            printf("Enter the value: ");
            int val;
            scanf("%d",&val);
            int pos = searchFromLast(val);
            if(pos == -1) cout<<"No list exists!\n";
            else if(pos) cout<<"Position from Last: "<<pos<<"\n\n";
            else cout<<"Item not found in the list\n";
        }
        else if(choice == 9) printFromHead();
        else if(choice == 10) printFromLast();
        else if(choice == 11) break;
        else printf("Wrong Choice Input!!\n\n");
    }
    freeTheList();
}