Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 m

PROGRAM

#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<cstdlib>
using namespace std;

struct node
{
    int info;
    struct node *next;
}*start;

class SinglyLinkedList
{
    public:
        node* createNode(int);
        void insert();
        void traverse();
        SinglyLinkedList() 
        {
            start = NULL;
        }
};

//This function is used for node creation
node *SinglyLinkedList::createNode(int value)
{
    struct node *temp, *s;
    temp = new(struct node); 
    if (temp == NULL)
    {
        cout<<"Node cannot be created "<<endl;
        return 0;
    }
    else
    {
        temp->info = value;
        temp->next = NULL;     
        return temp;
    }
}

//This function is used to insert elements covering all 3 conditions
void SinglyLinkedList::insert()
{
    int choice=0;
    int value=0,pos=0, counter = 0; 
    struct node *temp, *s, *ptr,*p;
    cout<<"Insert node at start(1)/End(2)/Specific Position(3)";
    cin>>choice;
    switch (choice)
    {
    case 1: 
            cout<<"Inserting element at start"<<endl;;
            cout<<"Enter the value to be inserted: "<<endl;
            cin>>value;
            temp = createNode(value);
            if (start == NULL)
            {
                start = temp;
                start->next = NULL;          
            } 
            else
            {
                p = start;
                start = temp;
                start->next = p;
            }
            cout<<"Element is inserted at start"<<endl;
            break;
    case 2: 
            cout<<"Inserting element at end"<<endl;
            cout<<"Enter the value to be inserted: ";
            cin>>value;
            temp = createNode(value);
            s = start;
            while (s->next != NULL)
            {         
                s = s->next;        
            }
            temp->next = NULL;
            s->next = temp;
            cout<<"Element Inserted at last"<<endl;
            break;
    case 3: 
            cout<<"Inserting element at specific position"<<endl;;
            cout<<"Enter the value to be inserted: ";
            cin>>value;
            temp = createNode(value);
            cout<<"Enter the postion at which element to be inserted: ";
            cin>>pos;
            int i;
            s = start;
            while (s != NULL)
            {
                s = s->next;
                counter++;
            }
            if (pos == 1)
            {
                if (start == NULL)
                {
                    start = temp;
                    start->next = NULL;
                }
                else
                {
                    ptr = start;
                    start = temp;
                    start->next = ptr;
                }
            }
            else if (pos > 1  && pos <= counter)
            {
                s = start;
                for (i = 1; i < pos; i++)
                {
                    ptr = s;
                    s = s->next;
                }
                ptr->next = temp;
                temp->next = s;
            }
            else
            {
                cout<<"Positon incorrect"<<endl;
            }
            break;
    default:
        break;
    }

}

//This function is used to traverse the link list and display the elements of list.
void SinglyLinkedList::traverse()
{
    struct node *temp;
    if (start == NULL)
    {
        cout<<"The List is Empty"<<endl;
        return;
    }
    temp = start;
    cout<<"Elements of list are: "<<endl;
    while (temp != NULL)
    {
        cout<<temp->info<<"->";
        temp = temp->next;
    }
    cout<<"NULL"<<endl;
}

void main()
{
int ch;
     SinglyLinkedList sl;
     while(1)
        {
             cout <<"\n1.Insert  2.Traverse 3.Exit\nEnter ur choice";
             cin >> ch;
             switch(ch)
              {
        case 1:  sl.insert();
                        break;
             case 2:  sl.traverse();
        break;
             case 3:  exit(0);
               }
         }
}

Sample Output:

1.Insert  2.Traverse 3.Exit
Enter ur choice 1
Insert node at start(1)/End(2)/Specific Position(3) 1
Inserting element at start
Enter the value to be inserted:
11
Element is inserted at start
1.Insert  2.Traverse 3.Exit
Enter ur choice 1
Insert node at start(1)/End(2)/Specific Position(3) 2
Inserting element at end
Enter the value to be inserted: 22
Element Inserted at last
1.Insert  2.Traverse 3.Exit
Enter ur choice 1
Insert node at start(1)/End(2)/Specific Position(3) 3
Inserting element at specific position
Enter the value to be inserted: 33
Enter the postion at which element to be inserted: 2

1.Insert  2.Traverse 3.Exit
Enter ur choice 2
Elements of list are:
11->33->22->NULL