Saturday 17 September 2016

Singly Linked List: Ordered list

Singly Linked List: Ordered list


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

struct node
{
                int data;
                struct node *link;
};
typedef struct node * NODE;

NODE getnode()
{
                NODE x;
                x = (NODE)malloc(sizeof(struct node));
                if(x==NULL)
                {
                                printf("\nInsufficient memory");
                                exit(0);
                }
                x->link = NULL;
                return x;
}

NODE insert_order(NODE first)
{
                int item;
                NODE temp, cur, prev;
                temp = getnode();

                printf("\nEnter the value: ");
                scanf("%d", &item);
                temp->data = item;

                if(first==NULL)
                                return temp;
                if(item < first->data)
                {
                                temp->link = first;
                                return temp;
                }
                prev = NULL;
                cur = first;
                while(cur!=NULL && item >= cur->data)
                {
                                prev = cur;
                                cur = cur->link;
                }

                prev->link = temp;
                temp->link = cur;
                return first;
}


void display(NODE first)
{
                NODE cur;
                cur = first;
                printf("\nContents are:");
                if(cur == NULL)
                                printf("\nList is empty. Nothing to display.");
                else
                {
                                while(cur!=NULL)
                                {
                                                printf("| %d | %d | --> ", cur->data, cur->link);
                                                cur = cur->link;
                                }
                }
}

void main()
{
                int ch, i, n;
                NODE first = NULL;
                printf("\nEnter number of nodes for list: ");
                scanf("%d", &n);
                for(i=0;i<n;i++)
                                first = insert_order(first);
                display(first);
}
Output:
Enter number of nodes for list: 6

Enter the value: 12
Enter the value: 34
Enter the value: 11
Enter the value: 90
Enter the value: 12
Enter the value: 44

Contents are:

| 11 | 7870320 | --> | 12 | 7877680 | --> | 12 | 7870216 | --> | 34 | 7877696 | --> | 44 | 7877664 | --> | 90 | 0 |



Also Check,

Singly Linked List: Reverse the List

Singly Linked List: Reverse the List



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

struct node
{
                int data;
                struct node *link;
};
typedef struct node * NODE;

NODE getnode()
{
                NODE x;
                x = (NODE)malloc(sizeof(struct node));
                if(x==NULL)
                {
                                printf("\nInsufficient memory");
                                exit(0);
                }
                x->link = NULL;
                return x;
}

NODE insert(NODE first)
{
                int val;
                NODE temp, cur;
                temp = getnode();
                printf("\nEnter the value: ");
                scanf("%d",&val);
                temp->data = val;

                if(first == NULL)
                                return temp;

                cur = first;
                while(cur->link!=NULL)
                {
                                cur = cur->link;
                }
                cur->link = temp;
                return first;
}

NODE reverse(NODE first)
{
                NODE rev, temp;
                if(first==NULL)
                {
                                printf("\nList empty")   ;
                                return NULL;
                }
                rev =NULL;
                while(first!=NULL)
                {
                                temp = first;
                                first= first->link;
                                temp->link = rev;
                                rev =temp;
                }
                return rev;
}

void display(NODE first)
{
                NODE cur;
                cur = first;
                printf("\nContents are:\n");
                if(cur == NULL)
                                printf("\nList is empty. Nothing to display.");
                else
                {
                                while(cur!=NULL)
                                {
                                                printf("| %d | %d | => ", cur->data, cur->link);
                                                cur = cur->link;
                                }
                }
}

void main()
{
                int ch,i, n;
                NODE first = NULL;

                printf("\nEnter number of nodes for list: ");
                scanf("%d", &n);
                for(i=0;i<n;i++)
                                first = insert(first);
               
                printf("\nBefore Reverse: \n");
                display(first);

                first = reverse(first);

                printf("\nAfter Reverse: \n");
                display(first);
}

Output:
Enter number of nodes for list: 4

Enter the value: 11
Enter the value: 12
Enter the value: 13
Enter the value: 14

Before Reverse:
Contents are:
| 11 | 7673608 | => | 12 | 7681016 | => | 13 | 7681032 | => | 14 | 0 |

After Reverse:
Contents are:

Singly Linked List: Search for key node in list

Singly Linked List: Search for key node in the list


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

struct node
{
                int data;
                struct node *link;
};
typedef struct node * NODE;

NODE getnode()
{
                NODE x;
                x = (NODE)malloc(sizeof(struct node));
                if(x == NULL)
                {
                                printf("\nInsufficient memory");
                                exit(0);
                }
                x->link = NULL;
                return x;
}

NODE insert(NODE first)
{
                int val;
                NODE temp, cur;
                temp = getnode();

                printf("\nEnter the value: ");
                scanf("%d",&val);
                temp->data = val;

                if(first == NULL)
                                return temp;

                cur = first;
                while(cur->link!=NULL)
                {
                                cur = cur->link;
                }
                cur->link = temp;
                return first;
}

void search(NODE first)
{
                int key;
                NODE cur;
                if(first == NULL)
                {
                                printf("\nList is empty");
                                return;
                }
                printf("\nEnter the item to be searched: ");
                scanf("%d", &key);

                cur = first;
                while(cur!=NULL)
                {
                                if(cur->data == key)
                                                break;
                                cur = cur->link;
                }
                if(cur == NULL)
                                printf("\nUnsuccessful search");
                else
                                printf("\nSuccessful search");
}

void display(NODE first)
{
                NODE cur;
                cur = first;
                printf("\nContents are:");
                if(cur == NULL)
                                printf("\nList is empty. Nothing to display.");
                else
                {
                                 while(cur!=NULL)
                                {
                                                printf("| %d | %d | --> ", cur->data, cur->link);
                                                cur = cur->link;
                                }
                }
}

void main()
{
                int ch, i, n;
                NODE first = NULL;

                printf("\nEnter number of nodes for list: ");
                scanf("%d", &n);
                for(i=0;i<n;i++)
                                first = insert(first);

                display(first);
                search(first);
}

Output:

Case 1:
Enter number of nodes for list: 4
Enter the value: 11
Enter the value: 12
Enter the value: 13
Enter the value: 14

Contents are:
| 11 | 8722184 | --> | 12 | 8729608 | --> | 13 | 8729624 | --> | 14 | 0 |

Enter the item to be searched: 12
Successful search


Case 2:
Enter number of nodes for list: 4
Enter the value: 11
Enter the value: 12
Enter the value: 13
Enter the value: 14

Contents are:
| 11 | 7083784 | --> | 12 | 7091208 | --> | 13 | 7091224 | --> | 14 | 0 |

Enter the item to be searched: 45
Unsuccessful search



Also Check,

Singly Linked List: Number of nodes in the list

Singly Linked List: Count number of nodes


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

struct node
{
                int data;
                struct node *link;
};
typedef  struct node * NODE;


NODE getnode()
{
                NODE x;
                x = (NODE)malloc(sizeof(struct node));
                if(x==NULL)
                {
                                printf("\nInsufficient memory");
                                exit(0);
                }
                x->link = NULL;
                return x;
}

NODE insert(NODE first)
{
                int val;
                NODE temp, cur;
                temp = getnode();

                printf("\nEnter the value: ");
                scanf("%d", &val);
                temp->data = val;

                if(first==NULL)
                                return temp;

                cur = first;
                while(cur->link!=NULL)
                {
                                cur = cur->link;
                }
                cur->link = temp;
                return first;
}


void countnode(NODE first)
{
                NODE cur;
                int count=0;
                cur = first;
                while(cur!=NULL)
                {
                                count++;
                                cur = cur->link;
                }
                printf("\nTotal number of nodes are: %d", count);
}

void display(NODE first)
{
                 NODE cur;
                cur = first;
                printf("\nContents are:\n");
                if(cur == NULL)
                                printf("\nList is empty. Nothing to display.");
                else
                {
                                while(cur!=NULL)
                                {
                                                printf("| %d | %d | --> ", cur->data, cur->link);
                                                cur = cur->link;
                                }
                }
}


void main()
{
                int ch,i, n;
                NODE first = NULL;

                 printf("\nEnter number of nodes for list: ");
                scanf("%d",&n);
                for(i=0;i<n;i++)
                                first = insert(first);

                display(first);
                countnode(first);
}

Output:

Enter number of nodes for list: 5

Enter the value: 11
Enter the value: 12
Enter the value: 13
Enter the value: 14
Enter the value: 15

Contents are:
| 11 | 4986632 | --> | 12 | 4994056 | --> | 13 | 4994072 | --> | 14 | 4994088 | --> | 15 | 0 |