doublylinkedlist.cpp

#include<stdio.h>
#include<stdlib.h>


#define NULL_VALUE -99999
#define SUCCESS_VALUE 99999

struct listNode
{
    int item;
    struct listNode * next;
    struct listNode * prev;
};

struct listNode * list;

struct listNode * tail;

void initializeList()
{
    list = 0;  //initially set to NULL
    tail = 0;
}

int insertFirst(int item) //insert at the beginning
{
    struct listNode * newNode ;
    newNode = (struct listNode*) malloc (sizeof(struct listNode)) ;
    newNode->item = item ;

    if(list==0) //inserting the first item
    {
        newNode->next = 0;
        newNode->prev = 0;
        list = newNode;
        tail = newNode;

    }
    else
    {
        newNode->next = list;
        list->prev = newNode;
        newNode->prev = 0;
        list = newNode;
    }
    return SUCCESS_VALUE ;
}

int insertLast(int item)
{
    struct listNode * temp ;
    temp = (struct listNode*) malloc (sizeof(struct listNode)) ;

    temp->item=item;

    if(list==0)
    {
        temp->next = 0;
        temp->prev = 0;
        list = temp;
        tail = temp;
    }
    else
    {
        temp->next=0;
        temp->prev=tail;

        tail->next=temp;
        tail=temp;
    }

    return SUCCESS_VALUE;

}
int insertBefore(int oldItem, int newItem)
{
    struct listNode *temp, *prev ;
    temp = list ;
    while (temp != 0)
    {
        if (temp->item == oldItem) break ;

        temp = temp->next ; //move to next node
    }
    if (temp == 0)
    {
        insertFirst(newItem) ;
        return SUCCESS_VALUE;
    } //item not found to delete
    if (temp == list)
    {
        insertLast(newItem) ;

        return SUCCESS_VALUE;

    }
    else
    {


        struct listNode * newNode,*prevnode=temp->prev;
        newNode = (struct listNode*) malloc (sizeof(struct listNode)) ;

        newNode->item=newItem;
        newNode->next=temp;
        temp->prev=newNode;
        newNode->prev=prevnode;
        prevnode->next=newNode;

        return SUCCESS_VALUE;
    }
    return SUCCESS_VALUE ;
}
struct listNode * searchItem(int item)
{
    struct listNode * temp ;
    temp = list ; //start at the beginning
    while (temp != 0)
    {
        if (temp->item == item) return temp ;
        temp = temp->next ; //move to next node
    }
    return 0 ; //0 means invalid pointer in C, also called NULL value in C
}
int deleteAfter(int item)
{
    struct listNode *newNode=searchItem(item);
    if(newNode==0||newNode->next==0)
    {
        return NULL_VALUE;
    }

    else
    {
        struct listNode *temp=newNode->next;
        newNode->next=temp->next;
        temp->next->prev=newNode;
        free(temp);

    }

}




int deleteLast()
{
    if(tail==0)return NULL_VALUE;
    if(tail->prev==0)
    {
        tail=0;
        list=0;
        return SUCCESS_VALUE;
    }
    struct listNode * temp ;
    temp = (struct listNode*) malloc (sizeof(struct listNode)) ;
    temp=tail;
    tail=tail->prev;
    tail->next=0;



    return SUCCESS_VALUE;
}




void printListForward()
{
    struct listNode * temp;
    temp = list;
    while(temp!=0)
    {
        printf("%d->", temp->item);
        temp = temp->next;
    }
    printf("\n");
}

void printListBackward()
{
    struct listNode * temp;
    temp = tail;
    while(temp!=0)
    {
        printf("<-%d", temp->item);
        temp = temp->prev;
    }
    printf("\n");
}


int main(void)
{
    initializeList();
    while(1)
    {
        printf("1. Insert new item. 2. Delete item. 3. Search item. \n");
        printf("4.Insert at last 5. Insert Before 6. Delete After Item\n");

        printf("7. Print forward. 8. Print backward. 9. exit.\n");

        int ch;
        scanf("%d",&ch);
        if(ch==1)
        {
            int item;
            scanf("%d", &item);
            insertFirst(item);
        }
        else if(ch==2)
        {
            int item = deleteLast();
            if(item!=NULL_VALUE) printf("Deleted: %d\n", item);
        }
        else if(ch==3)
        {
            int item;
            scanf("%d", &item);
            struct listNode * res = searchItem(item);
            if(res!=0) printf("Found.\n");
            else printf("Not found.\n");
        }
        else if(ch==4)
        {
            int item;
            scanf("%d",&item);
            insertLast(item);
        }
        else if(ch==5)
        {
            int old,New;
            printf("Insert oldItem:");
            scanf("%d",&old);
            printf("Insert newItem:");
            scanf("%d",&New);
            insertBefore(old,New );

        }
        else if(ch==6)
        {
            int item;
            scanf("%d",&item);
            deleteAfter(item);
        }
        else if(ch==7)
        {
            printListForward();
        }
        else if(ch==8)
        {
            printListBackward();
        }
        else if(ch==9)
        {
            break;
        }
    }

}