Linked List

Here's a simple implementation of Singly linked list in C++ , which includes insertion , deletion and searching .

#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <limits>
#define BAD_INPUT_CUTOFF 3

using namespace std;


struct node
{
    int data;
    struct node* next;
};

struct searchDS
{
    int occurence;
    int posit[100];
};

typedef struct node Node;
typedef struct searchDS SD;

Node *start = NULL;
Node *new1;

void print_list(Node*);
int print_no();
int count();
unsigned int getIntInRange(unsigned int min, unsigned int max, const char *prompt);

Node* create_node()
{
    Node* newnode;

    newnode = (Node*)malloc(sizeof(struct node));

    printf("\nEnter the data (numeric only): ");
    scanf("%d", &newnode -> data);
    newnode -> next = NULL;

    return newnode;
}

int isEmpty()
{
    if(start == NULL)
    {
        printf("\nList is empty");
        return true;
    }
    else
        return false;
}

Node* search(int data)
{
    Node* ptr;

    int flag = 0;

    for(ptr = start ; ptr; ptr = ptr -> next)
    {
        if(ptr -> data == data)
        {
            flag = 1;
            printf("\nData %d found at %x ",data,ptr);
        }
    }

    if(flag == 1 )
    {
        return ptr;
    }
    else
    {
        printf("\nData %d not found !!!",data);
        return NULL;
    }
}

void adv_search(int data, SD* sp)
{

    Node *ptr,*prev;

    int i ,j, pos = 1;

    if(start ==  NULL)
    {
        printf("\nList is empty ");
        return;
    }
    sp->occurence = 0;

    for(i=0,ptr = start; (ptr); ptr = ptr->next,pos++)
    {
        if(ptr -> data == data)
        {
            (sp->occurence)++;
            sp->posit[i++] = pos ;
        }
    }

    if(sp->occurence == 0)
    {
        printf("\nData %d not in the list!!!",data);
        return;
    }
    printf("\nOcc: %d , Positions : ", sp->occurence);
    for(j=0; j<i; j++)
        printf("%d, ",sp->posit[j]);
    printf("\n");
}

void insert_beg()
{
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    if(start == NULL)
    {
        start = new1;
        print_list(start);
        return;
    }
    else
    {
        new1 -> next = start ;
        start = new1;
        print_list(start);
        return;
    }
}
void insert_end()
{
    Node *ptr,*prev;
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    if(start == NULL)
    {
        start = new1;
        print_list(start);
        return;
    }
    else
    {
        for(prev = start , ptr = start -> next ; ptr ; prev = ptr , ptr = ptr -> next);

        prev -> next = new1;
        print_list(start);
    }
}
void insert_at_pos()
{
    Node *ptr , *prev;
    int pos,i;
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    printf("\nWhat position do you want to enter ? ");
    scanf("%d",&pos);

    if (pos < 1 || pos > print_no())
    {
        printf("\n Inserting failed! Out of bounds!!!");
        return;
    }
    else if(pos == 1)
    {
        new1 -> next = start;
        start = new1;
        print_list(start);
    }
    else if(pos > 1)
    {
        for(i = 1 ,prev = start, ptr = start -> next; (ptr) && (i < pos -1); prev = ptr , ptr = ptr->next,i++);
        prev -> next = new1 ;
        new1 -> next = ptr ;

        print_list(start);
    }
}

void delete_node_by_pos()
{
    Node *prev, *ptr, *temp;
    int pos,i;
    //printf("\n In function %s\n",__func__);

    if(isEmpty() != true)
    {
        printf("\nEnter the node no. you want to delete: ");
        scanf("%d",&pos);

        if (pos < 1 || pos > count())
        {
            printf("\n Deletion failed! Out of bounds!!!");
            return;
        }
        else if(pos == 1)
        {
            temp = start;
            start = start -> next;
            free(temp);
            print_list(start);
        }
        else if(pos > 1)
        {
            for(i = 1 ,prev = start, ptr = start -> next; (ptr) && (i < pos -1); prev = ptr , ptr = ptr->next,i++)
            {
                //`printf("\n prev-> data : %d\tptr->data :%d" ,prev-> data, ptr->data);
            }
            temp = ptr;
            prev -> next = ptr -> next;
            free(temp);
            print_list(start);
        }
    }
}

void delete_node_by_data()
{
    Node *ptr,*prev,*temp;
    int info, ch;
    SD sp;
    static int visited = 0;
    //printf("\n In function %s\n",__func__);

    if(isEmpty() != true)
    {
        printf("\nEnter the data you want to delete: ");
        scanf("%d",&info);
        adv_search(info, &sp);

        {
            if(start -> data == info )
            {
                temp = start;
                start = start -> next;
                free(temp);
                print_list(start);
                return;
            }
            for(prev = start , ptr = start -> next ; ptr ; prev = ptr , ptr = ptr -> next)
            {
                if( ptr -> data == info)
                {
                    temp = ptr;
                    prev -> next = ptr -> next;
                    free(temp);
                    print_list(start);
                    return;
                }
            }
        }
        print_list(start);
    }
}


void print_list(Node* start)
{
    Node *ptr;
//printf("\n In function %s\n",__func__);

    printf("\n");
    for(ptr = start; ptr ; ptr = ptr ->next )
    {
        printf("-> %d ",ptr->data);
    }
    printf("\n");
}
int print_no()
{
//printf("\n In function %s\n",__func__);
    printf("\nThe total no. of members in the list are : %d \n", count());
}

int count()
{

    Node *ptr;
    int count = 0;

    ptr = start ;
    while(ptr!=NULL)
    {
        ptr = ptr -> next;
        count++;
    }

    return count;
}

Node* reverse(Node* root)
{
    Node* ret_val;

    if ( root == NULL || root->next == NULL )
    {
        return root;
    }
    ret_val = reverse ( root -> next );

    root -> next->next = root;
    root->next = NULL;
    return ret_val;
}

unsigned int getIntInRange(unsigned int min, unsigned int max, 
                           const char *prompt)
{
    int input, //used to get input
        bad_count=0; //used to keep track of how many bad attempts.
    do
    {
        cout << prompt; //print out our prompt
        cin >> input; //get the input
        if (!cin.good() || input < min || input > max)
        {
            cout << "\nInvalid Input!" << std::endl;
            cin.clear(); //resets the state flag
            cin.ignore(numeric_limits<streamsize>::max(),'\n'); 
                        //clears out the buffer
            bad_count++; //User made a bad input, count it
            input = 0; // user did not enter a valid number
        }
    }
    while (input == 0 && bad_count < BAD_INPUT_CUTOFF);
    return input;
}

int main()
{
    int choice,searchKey,info;
    SD sp;
    Node* temp;
    while(1)
    {

        printf("\n1.Insert a node at beg\n2.Insert a node at end
                \n3.Insert a node at a given position\n4.Delete a 
                node by data\n5.Delete a node by position\n6.Print
                the list\n7.Print the no. of elements\n8.Reverse the 
                list\n9.Search \n10.Advanced Search\n11.Exit\n");

         choice  = getIntInRange(1,11,"\n Choose your option (1-11):\n");

        switch(choice)
        {
        case 1 :
            insert_beg();
            break;
        case 2 :
            insert_end();
            break;
        case 3 :
            insert_at_pos();
            break;
        case 4 :
            delete_node_by_data();
            break;
        case 5 :
            delete_node_by_pos();
            break;
        case 6 :
            print_list(start);
            break;
        case 7 :
            print_no();
            break;
        case 8 :
            start = reverse(start);
            print_list(start);
            break;
        case 9 :
            printf("\nEnter the data you want to search : ");
            scanf("%d",&searchKey);

            if(search(searchKey)!=NULL)
                printf("\nData %d at %x",searchKey , search(searchKey));

            break;
        case 10 :
            printf("\nEnter the data you want to search : ");
            scanf("%d",&searchKey);
            adv_search(searchKey,&sp);
            break;
        case 11 :
            exit(0);

        default :
            printf("\nInvalid input !!!\n");
            break;

        }
    }
}