Monday 19 September 2016

Singly Linked List Operations

Singly Linked List Operations:

1) Insert at beginning
2) Insert at end
3) Insert after the given key node
4) Insert before the given key node
5) Insert at specified position
6) Delete from the beginning
7) Delete from the end
8) Delete the specified key node


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

NODE create_list(NODE first);
NODE insert_at_front(NODE first);
NODE insert_at_end(NODE first); 
NODE insert_after(NODE first);
NODE insert_before(NODE first);
NODE insert_at_pos(NODE first);
NODE delete_at_front(NODE first);
NODE delete_at_end(NODE first);
NODE delete_at_midle(NODE first);

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 create_list(NODE first)
{
                int i, n;
                printf("\nCreating the list: ");
                printf("\nEnter the number of nodes: ");
                scanf("%d", &n);

                /*Number of nodes 0*/
                if(n==0)
                                return first;

                printf("\nEnter the VALUES for nodes: ");
                for(i=1; i<=n; i++)
                                first= insert_at_end(first);
                return first;
}


NODE insert_at_front(NODE first)
{
                int val;
                NODE temp;
                temp = getnode();

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

                /*Case 1: List is empty.*/
                if(first == NULL)
                                return temp;

                /*Case 2: List has nodes.*/
                temp->link = first;
                return temp;
}

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

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

                /*Case 1: List is empty*/
                if(first == NULL)
                                return temp;

                /*Case 2: List has nodes: Traverse till the end of the list*/
                cur = first;
                while(cur->link!=NULL)
                {
                                cur = cur->link;
                }

                /*Set the link field of last node to point to temp node*/
                cur->link = temp;
                return first;
}

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

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

                /*Case 1: List is empty.*/
                if(first == NULL)
                                return temp;

                printf("\nEnter the key after which node to be inserted:");
                scanf("%d", &key);

                /*Case 2: List has nodes. Traverse till key node is found. */
                cur = first;
                while(cur != NULL)
                {
                                if( cur->data == key)
                                {
                                                temp->link = cur->link;
                                                cur->link = temp;
                                                return first;
                                }
                                cur = cur->link;
                }
                 /*End of list. Key is not found*/
                printf("\nKey element not found");
                return first;
}

NODE insert_before(NODE first)
{
                int val, key;
                NODE temp, cur, prev;
                temp = getnode();

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

                /*Case 1: List is empty. */
                if(first == NULL)
                                return temp;

                printf("\nEnter the key before which node to inserted:");
                scanf("%d", &key);

                /*Case 2: If the first node itself is the key node*/
                if(first->data == key)
                {
                                temp->link = first;
                                return temp;
                }

                 /*Case 3: Otherwise*/
                prev = NULL;
                cur = first;
                while(cur != NULL)
                {
                                if( cur->data == key)
                                {
                                                prev->link = temp;
                                                temp->link = cur;
                                                return first;
                                }
                                prev = cur;
                                cur = cur->link;
                }
                printf("\nKey element not found");
                return first;
}


NODE insert_at_pos(NODE first)
{
                int val, pos, i;
                NODE temp, cur, prev;
                temp = getnode();

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

                 /*Case 1: List is empty*/
                if(first == NULL)
                                return temp;

                printf("\nEnter the position where node to inserted:");
                scanf("%d", &pos);

                 /*Case 2: First position*/
                if(pos == 1)
                {
                                temp->link = first;
                                return temp;
                }

                /*Case 3: Any other position*/
                prev = NULL;
                cur = first;

                for(i =1; cur != NULL && i<pos; i++)
                {
                                prev = cur;
                                cur = cur->link;
                }
                if(cur==NULL)
                {
                                printf("\nThere are less than %d elements", pos);
                                return first;        
                 }
                else
                {
                                prev->link = temp;
                                temp->link = cur;
                                return first;
                }
}

NODE delete_at_front(NODE first)
{
                NODE temp;
                /*Case 1: List is empty. Nothing to delete. */
                if(first == NULL)
                {
                                printf("\nList is empty. Cannot delete.");
                                return NULL;
                }

                /*Case 2: List has only one node. Deleting this node makes list empty. */
                if(first->link ==NULL)
                {
                                printf("\nItem that got deleted is %d", first->data);
                                free(first);
                                return NULL;
                }

                /*Case 3: List has more than one node. Delete the front node. Update the first pointer. */
                temp = first;
                first = first->link;
                temp->link=NULL;
                printf("\nItem that got deleted is %d", temp->data);
                free(temp);
                return first;
}

NODE delete_at_midle(NODE first)
{
                int val, key;
                NODE prev, cur;
                prev =NULL;

                 /*Case 1: List is empty. Nothing to delete. */
                if(first==NULL)
                {
                                printf("\nList empty cannot delete");
                                return NULL;
                }
                printf("\nEnter the key:");
                scanf("%d", &key);

                /*Case 2: First node is the key node. */
                if(first->link==NULL && first->data == key)
                {
                                printf("\nItem that got deleted is %d", first->data);
                                free(first);
                                return NULL;
                }

                /*Case 3: traverse till key node is found. Delete that node. */
                cur = first;
                while(cur != NULL)
                {
                                if( cur->data == key)
                                {
                                                prev->link = cur->link;
                                                printf("\nItem that got deleted is %d", cur->data);
                                                free(cur);
                                                return first;
                                }
                                prev = cur;
                                cur = cur->link;
                }
                printf("\nKey element not found");
                return first;
}

NODE delete_at_end(NODE first)
{
                NODE cur, prev;

                /*Case 1: List is empty. */
                if(first==NULL)
                {
                                printf("\nList is empty. Cannot delete.");
                                return NULL;
                }

                /*Case 2: List has only one node. Deleting that node makes list empty. */
                if(first->link ==NULL)
                {
                                printf("\nItem that got deleted is %d", first->data);
                                free(first);
                                return NULL;
                }

                 /*Case 3: List having more than one node. Delete the last node. Update the link of last but one node. */
                prev =NULL;
                cur = first;
                while(cur->link!=NULL)
                {
                                prev = cur;
                                cur = cur->link;
                }
                prev->link =NULL;
                printf("\nItem that got deleted is %d", cur->data);
                free(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  ", cur->data);
                                                cur = cur->link;
                                }
                }
}
void main()
{
                int ch;
                NODE first = NULL;
                while(1)
                {
                                printf("\n\n~~MENU~~");
                                printf("\n1.Create a list(any insertion)");
                                printf("\n2.Insert at front");
                                printf("\n3.Insert after a given key");
                                printf("\n4.Insert before a given key");
                                printf("\n5.Insert at pos");
                                printf("\n6.Insert at end");
                                printf("\n7.Delete from front");
                                printf("\n8.Delete from middle using key");
                                printf("\n9.Delete from end");
                                printf("\n10.exit");
                                printf("\nEnter your choice: ");
                                scanf("%d",&ch);
                                switch(ch)
                                {
                                                case 1:                 first = create_list(first);
                                                                                display(first);
                                                                                break;
                                                case 2:                  first = insert_at_front(first);
                                                                                display(first);
                                                                                break;
                                                case 3:                  first = insert_after(first);
                                                                                display(first);
                                                                                break;
                                                case 4:                  first = insert_before(first);
                                                                                display(first);
                                                                                break;
                                                case 5:                  first = insert_at_pos(first);
                                                                                display(first);
                                                                                break;
                                                case 6:                  first = insert_at_end(first);
                                                                                display(first);
                                                                                break;
                                                case 7:                  first = delete_at_front(first);
                                                                                display(first);
                                                                                break;
                                                case 8:                  first = delete_at_midle(first);
                                                                                display(first);
                                                                                break;
                                                case 9:                  first = delete_at_end(first);
                                                                                display(first);
                                                                                break;
                                                case 10:                exit(0);
                                }
                }
}


Output:

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 1

Creating the list:
Enter the number of nodes: 3

Enter the VALUES for nodes:
Enter the value:                11
Enter the value:                12
Enter the value:                13
Contents are:    11           12           13

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 2

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

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 6

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

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 3

Enter the value to be inserted:                                 66
Enter the key after which node to be inserted:                 13
Contents are:    14           11           12           13           66           15

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 4

Enter the value to be inserted:                                 88
Enter the key before which node to be inserted:             12
Contents are:    14            11            88           12           13           66           15

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 5

Enter the value to be inserted:                                 99
Enter the position where node to be inserted:  5
Contents are:    14           11           88           12           99           13           66           15

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 7

Item that got deleted is 14
Contents are:    11           88           12           99           13           66           15

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 9

Item that got deleted is 15
Contents are:    11           88           12           99           13           66

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 8

Enter the key: 99
Item that got deleted is 99
Contents are:    11           88           12           13           66

~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 10


No comments:

Post a Comment