Circular Singly Linked List: Delete from End

Circular Singly Linked List: Delete from End

#include<stdio.h>

#include<stdlib.h>

struct node

{

                int data;

                struct node *link;

};

typedef struct node* NODE;

NODE getnode();

NODE insert_at_end(NODE last,int item);

NODE delete_at_end(NODE last);

void display(NODE last);

NODE getnode()

{

                NODE x;

                x =(NODE) malloc(sizeof(struct node));

                return x;

}

void display(NODE last)

{

                NODE cur;

                printf("\nContents are:\n");

                if(last == NULL)

                                printf("\nList is empty. Nothing to display.");

                else

                {

                                cur = last->link;

                                printf("==> ");

                                while(cur != last)

                                {

                                                printf("| %d | %d | => ", cur->data, cur->link);

                                                cur = cur->link;

                                }

                                printf("| %d | %d | => ", cur->data, cur->link);

                }

}

NODE insert_at_end(NODE last, int item)

{

                int val;

                NODE cur, temp;

                temp = getnode();

                temp->data = item;

                if(last == NULL)

                {

                                last = temp;

                }

                else

                {

                                temp->link = last->link;

                }

                last->link = temp;

                return temp;

}

NODE delete_at_end(NODE last)

{

                NODE prev, cur;

                if(last == NULL)

                {

                                printf("\nList is empty");

                                return NULL;

                }

                if(last->link == last)

                {

                                printf("\nThe node %d is deleted", last->data);

                                free(last);

                                return NULL;

                }

                prev = last->link;

                while(prev->link!=last)

                {

                                prev = prev->link;

                }

                prev->link = last->link;

                printf("The node %d is deleted \n", last->data);

                free(last);

                return prev;

}

void main()

{

                int ch, item;

                NODE last = NULL;

                while(1)

                {

                                printf("\n\n~~MENU~~");

                                printf("\n1.Insert at end");

                                printf("\n2.Delete at end");

                                printf("\n3.Display");

                                printf("\n4.exit");

                                printf("\nEnter your choice: ");

                                scanf("%d", &ch);

                                switch(ch)

                                {

                                                case 1:                 printf("\nEnter the value: ");

                                                                                scanf("%d", &item);

                                                                                last = insert_at_end(last, item);

                                                                                break;

                                                case 2:                 last = delete_at_end(last);

                                                                                break;

                                                case 3:                  display(last);

                                                                                break;

                                                case 4:                  exit(0);

                                }

                }

}

Output:

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 1

Enter the value: 11

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 3

Contents are:

==> | 11 | 8591216 | =>

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 1

Enter the value: 12

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 3

Contents are:

==> | 11 | 8591112 | => | 12 | 8591216 | =>

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 2

The node 12 is deleted

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 2

The node 11 is deleted

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 2

List is empty

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 3

Contents are:

List is empty. Nothing to display.

~~MENU~~

1.Insert at end

2.Delete at end

3.Display

4.exit

Enter your choice: 4

Also Check,

• Circular Singly Linked List
• Insert at Front
• Insert at End
• Delete from Front
• Delete from End

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,

• Create the List
• Search in the List
• Concatenate two Lists
• Reversing the List
• Ordered List
• Count the number of nodes in the List/ Length of the List

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 |

Total number of nodes are: 5



Also Check,

• Create the List
• Search in the List
• Concatenate two Lists
• Reversing the List
• Ordered List
• Count the number of nodes in the List/ Length of the List

Lab Program 12 Hashing 15CSL38 Data Structures in C Lab

Lab program 12

Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the records in file F.
Assume that file F is maintained in memory by a Hash Table(HT) of m memory locations with L as the set of memory addresses (2-digit) of locations in HT.
Let the keys in K and addresses in L are integers.
Design and develop a Program in C that uses Hash function H: K -> L as H(K)=K mod m (remainder method), and implement hashing technique to map a given key K to the address space L.
Resolve the collision (if any) using linear probing.

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

int key[20],n,m;
int *ht,index;
int count = 0;

void insert(int key)
{
            index = key % m;
            while(ht[index] != -1)
            {
                         index = (index+1)%m;
            }
            ht[index] = key;
            count++;
 }

void display()
{
           int i;
           if(count == 0)
          {
                         printf("\nHash Table is empty");
                         return;
           }

           printf("\nHash Table contents are:\n ");
           for(i=0; i<m; i++)
                      printf("\n T[%d] --> %d ", i, ht[i]);
}


void main()
{
         int i;
         printf("\nEnter the number of employee  records (N) :   ");
         scanf("%d", &n);

         printf("\nEnter the two digit memory locations (m) for hash table:   ");
         scanf("%d", &m);

         ht = (int *)malloc(m*sizeof(int));
         for(i=0; i<m; i++)
                     ht[i] = -1;

         printf("\nEnter the four digit key values (K) for N Employee Records:\n  ");
         for(i=0; i<n; i++)
                    scanf("%d", &key[i]);

         for(i=0;i<n;i++)
        {
                   if(count == m)
                   {
                        printf("\n~~~Hash table is full. Cannot insert the record %d key~~~",i+1);
                        break;
                   }
                   insert(key[i]);
    }

            //Displaying Keys inserted into hash table
             display();
}

Output:

Enter the number of employee  records (N) :   12

Enter the two digit memory locations (m) for hash table:   15

Enter the four digit key values (K) of 'N' Employee Records:

1234

5678

3456

2345

6799

1235

7890

3214

3456

1235

5679

2346

Hash Table contents are:

 T[0] --> 7890

 T[1] --> -1

 T[2] --> -1

 T[3] --> -1

 T[4] --> 1234

 T[5] --> 2345

 T[6] --> 3456

 T[7] --> 6799

 T[8] --> 5678

 T[9] --> 1235

 T[10] --> 3214

 T[11] --> 3456

 T[12] --> 1235

 T[13] --> 5679

 T[14] --> 2346