linkedlistwithtail.cpp

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


#define NULL_VALUE -99999
#define SUCCESS_VALUE 99999

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

struct listNode * list;
struct listNode * tail;

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

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
}

void printList()
{
    struct listNode * temp;
    temp = list;
    while(temp!=0)
    {
        printf("%d->", temp->item);
        temp = temp->next;
    }
    printf("\n");
}
void printListBackward( listNode *node)
{
    if(node==0)
    {
        return;
    }
    printListBackward(node->next);
    printf("<-%d",node->item);
}

//add required codes to insert item at the beginning, remember to properly set the tail pointer!
int insertItem(int Item)
{
    struct listNode * newNode ;
    newNode = (struct listNode*) malloc (sizeof(struct listNode)) ;
    newNode->item = Item ;
    if(list==0)
    {
        list=newNode;
        list->next=0;
        tail=newNode;
        tail->next=0;
        return SUCCESS_VALUE;
    }
    if(list->next==0)
    {
        tail=list;
        newNode->next=list;
        list=newNode;
        return SUCCESS_VALUE;
    }
    newNode->next=list;
    list=newNode;
    return SUCCESS_VALUE;
}

//add required codes to delete item, remember to properly set the tail pointer!
int deleteAfter(int item)
{
    struct listNode *temp=searchItem(item);
    if(temp==0) return NULL_VALUE;
    if(temp ==list)
    {
        list=0;
        tail=0;
        return SUCCESS_VALUE;
    }
    if(temp==tail)
    {
        return NULL_VALUE;
    }
    struct listNode *temp1=temp->next;
    temp->next=temp->next->next;
    free(temp1);
    return SUCCESS_VALUE;

}
int deleteLast()
{
    if(tail==0)
    {
        return NULL_VALUE;

    }
    listNode *temp=list;
    while(temp->next!=tail)
    {
        temp=temp->next;
    }
    tail=temp;
    tail->next=0;

    return SUCCESS_VALUE;

}
int deleteItem(int item)
{
    struct listNode *temp, *prev ;
    temp = list ; //start at the beginning
    while (temp != 0)
    {
        if (temp->item == item) break ;
        prev = temp;
        temp = temp->next ; //move to next node
    }
    if (temp == 0) return NULL_VALUE ; //item not found to delete
    if (temp == list) //delete the first node
    {
        list = list->next ;
        free(temp) ;
    }
    else if(temp==tail){
        deleteLast();
    }
    else
    {
        prev->next = temp->next ;
        free(temp);
    }
    return SUCCESS_VALUE ;
}
int insertLast(int item)
{
    struct listNode * newNode ;
    newNode = (struct listNode*) malloc (sizeof(struct listNode)) ;
    newNode->item = item ;
    if(tail==0)
    {
        tail=newNode;
        tail->next=0;
        return SUCCESS_VALUE;
    }

    tail->next=newNode;
    newNode->next=0;
    tail=newNode;
    return SUCCESS_VALUE;
}
int insertBefore(int oldItem, int newItem)
{
    struct listNode *temp, *prev ;
    temp = list ; //start at the beginning
    while (temp != 0)
    {
        if (temp->item == oldItem) break ;
        prev = temp;
        temp = temp->next ; //move to next node
    }
    if (temp == 0)
    {
        insertItem(newItem) ;
        return SUCCESS_VALUE;
    } //item not found to delete
    if (temp == list)
    {
        insertItem(newItem) ;

        return SUCCESS_VALUE;

    }

    else
    {


        struct listNode * newNode ;
        newNode = (struct listNode*) malloc (sizeof(struct listNode)) ;
        newNode->item=newItem;
        newNode->next=temp;
        prev->next=newNode;
        return SUCCESS_VALUE;
    }
    return SUCCESS_VALUE ;
}
int main(void)
{
    initializeList();
    while(1)
    {
        printf("1. Insert new item. 2. Delete After. 3. Search item. \n");
        printf("4. Insert Last. 5.Delete Last 6. Print. 7.print reverse 8.delete Item 9.insert Before 10. exit.\n");

        int ch;
        scanf("%d",&ch);
        if(ch==1)
        {
            int item;
            scanf("%d", &item);
            insertItem(item);
        }
        else if(ch==2)
        {
            int item;
            scanf("%d", &item);
            deleteAfter(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)
        {
            deleteLast();
        }
        else if(ch==6)
        {
            printList();
            printf("\n");
        }
        else if(ch==7)
        {
            printListBackward(list );
            printf("\n");

        }
        else if(ch==10)
        {
            break;
        }
        else if(ch==8)
        {
            int item;
            scanf("%d",&item);
            deleteItem(item);
        }
        else if(ch==9){
            int old,New;
            printf("Insert oldItem:");
            scanf("%d",&old);
            printf("Insert newItem:");
            scanf("%d",&New);
            insertBefore(old,New );
        }
    }

}