C Program to Implement Locality of Reference in Link List

«
»
This C program Implements locality of reference in Link list.

Here is the source code of the C program which implements locality of reference in Link list.The found element in a linked list moves to the front as soon as it is found. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to find element in a linked list and element is moved 
  3.  * to the front as soon as it is found.
  4.  * This techinque is based on the locality of reference.
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. typedef struct Node
  10. {
  11.     int data;
  12.     struct Node *next;
  13. }node;
  14.  
  15. /* Function to insert node in link list */
  16. void insert(node **head, int data)
  17. {
  18.     node **ptr2 = head;
  19.     if (*ptr2 == NULL) {
  20.       (*ptr2) = (node*)malloc(sizeof(node));
  21.       (*ptr2)->data = data;
  22.       (*ptr2)->next = NULL;
  23.     }
  24.     else {
  25.       while (*ptr2 != NULL)
  26.         ptr2 = &(*ptr2)->next;
  27.       (*ptr2) = (node*)malloc(sizeof(node));
  28.       (*ptr2)->data = data;
  29.       (*ptr2)->next = NULL;
  30.     }
  31. }
  32. /* End of insert() */
  33.  
  34. /* Function to search a node and insert it at the begining */
  35. int find(node *p, int key)
  36. {
  37.     node *pointer;
  38.     pointer = p;
  39.     while (pointer != NULL) {
  40.       if (pointer->data == key) {
  41.         printf("Element  found\n");
  42.         return(key);
  43.       }
  44.       pointer = pointer->next;
  45.     }
  46.     printf("Element not found\n");
  47. }
  48. /* End of find() */
  49.  
  50. /* Function to insert node at begining */
  51. void insertStart(node **pointer, int data)
  52. {
  53.     node *temp;
  54.     temp = (node*)malloc(sizeof(node));
  55.     temp->data = data;
  56.     temp->next = *pointer;
  57.     *pointer = temp;
  58. }
  59. /* End of insertStart() */
  60.  
  61. /* Function to delete a node */
  62. void delete(node **head, int data)
  63. {
  64.     node **ptr2;
  65.     for (ptr2= head; *ptr2 != NULL; ptr2 = &(*ptr2)->next)
  66.     {
  67.       if ((*ptr2)->data == data) {
  68.         *ptr2 = (*ptr2)->next;
  69.         break;
  70.       }
  71.     }
  72. }
  73. /* End of delete() */
  74.  
  75. /* Function to print elements of the list */
  76. void print (node *head)
  77.  {
  78.     node * ptr =head;
  79.     while (ptr != NULL) {
  80.       printf("%d ", ptr->data);
  81.       ptr = ptr->next;
  82.     }
  83.     printf("\n");
  84. }
  85. /* End of print() */
  86.  
  87. /* The main() begins */
  88. int main()
  89. {
  90.     int query, data, t;
  91.     char ch = 'y';
  92.     node *start = NULL, *temp;
  93.     printf("1. Insert\n");
  94.     printf("2. Print\n");
  95.     printf("3. Find\n");
  96.     printf("4. Exit\n");
  97.  
  98.     while(1) {
  99.       printf("Enter choice:");
  100.       scanf("%d", &query);
  101.       switch(query) {
  102.         case 1: printf("Enter Data:");
  103.           scanf("%d", &data);
  104.           insert(&start, data);
  105.           break;
  106.         case 2: printf("The list is ");
  107.           print(start);
  108.           printf("\n");
  109.           break;
  110.         case 3: printf("Enter element to be searched:");
  111.           scanf("%d",&data);
  112.           t = find(start, data);
  113.       if(t != -1) {
  114.             delete(&start, t);
  115.             insertStart(&start, t);
  116.           }
  117.           break;
  118.         case 4: printf("Exit\n");
  119.           exit(0);
  120.           break;
  121.         default: printf("Wrong choice");
  122.       }
  123.     }
  124.     return 0;
  125. }

$ gcc link_list.c
$ ./a.out
1. Insert
2. Print
3. Find
4. Exit
Enter choice:1
Enter Data:1
Enter choice:1
Enter Data:2
Enter choice:1
Enter Data:3
Enter choice:2
The list is 1 2 3 
 
Enter choice:3
Enter element to be searched:2
Element  found
Enter choice:2
The list is 2 1 3 
 
Enter choice:4
Exit

Sanfoundry Global Education & Learning Series – 1000 C Algorithms.

advertisement
advertisement
If you wish to look at all C Algorithms and Solutions, go to C Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.