Java Program to Perform Searching using Self-Organizing Lists

«
»
This is a java program to search an element using Self Organizing lists. A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time. The aim of a self-organizing list is to improve efficiency of linear search by moving more frequently accessed items towards the head of the list. A self-organizing list achieves near constant time for element access in the best case. A self-organizing list uses a reorganizing algorithm to adapt to various query distributions at runtime.

Here is the source code of the Java Program to Perform Searching Using Self-Organizing Lists. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to search an element in self organizing lists
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. class SelfOrganizingList 
  6. {
  7.     private int[] list;
  8.     private int[] count;
  9.     private int size;
  10.  
  11.     public SelfOrganizingList(int listSize) 
  12.     {
  13.         list = new int[listSize];
  14.         count = new int[listSize];
  15.         size = 0;
  16.     }
  17.  
  18.     public boolean isEmpty() 
  19.     {
  20.         return size == 0;
  21.     }
  22.  
  23.     public boolean isFull() 
  24.     {
  25.         return size == list.length;
  26.     }
  27.  
  28.     public void makeEmpty() 
  29.     {
  30.         int l = list.length;
  31.         list = new int[l];
  32.         count = new int[l];
  33.         size = 0;
  34.     }
  35.  
  36.     public int getSize() 
  37.     {
  38.         return size;
  39.     }
  40.  
  41.     public void insert(int val) 
  42.     {
  43.         if (isFull()) 
  44.         {
  45.             System.out.println("Error : List full!");
  46.             return;
  47.         }
  48.         list[size] = val;
  49.         count[size] = 0;
  50.         size++;
  51.     }
  52.  
  53.     public void remove(int pos) 
  54.     {
  55.         pos--;
  56.         if (pos < 0 || pos >= size) 
  57.         {
  58.             System.out.println("Invalid position ");
  59.             return;
  60.         }
  61.         for (int i = pos; i < size - 1; i++) 
  62.         {
  63.             list[i] = list[i + 1];
  64.             count[i] = count[i + 1];
  65.         }
  66.         size--;
  67.     }
  68.  
  69.     public boolean search(int x) 
  70.     {
  71.         boolean searchResult = false;
  72.         int pos = -1;
  73.         for (int i = 0; i < size; i++) 
  74.         {
  75.             if (list[i] == x) {
  76.                 searchResult = true;
  77.                 pos = i;
  78.                 break;
  79.             }
  80.         }
  81.         if (searchResult) 
  82.         {
  83.             count[pos]++;
  84.             int c = count[pos];
  85.             for (int i = 0; i < pos; i++) 
  86.             {
  87.                 if (count[pos] > count[i]) 
  88.                 {
  89.                     for (int j = pos; j > i; j--) 
  90.                     {
  91.                         list[j] = list[j - 1];
  92.                         count[j] = count[j - 1];
  93.                     }
  94.                     list[i] = x;
  95.                     count[i] = c;
  96.                     break;
  97.                 }
  98.             }
  99.         }
  100.         return searchResult;
  101.     }
  102.  
  103.     public void printList() 
  104.     {
  105.         System.out.print("\nList = ");
  106.         for (int i = 0; i < size; i++)
  107.             System.out.print(list[i] + " ");
  108.         System.out.print("\nCount = ");
  109.         for (int i = 0; i < size; i++)
  110.             System.out.print(count[i] + " ");
  111.     }
  112. }
  113.  
  114. public class Search_Self_Organizing 
  115. {
  116.     public static void main(String[] args) 
  117.     {
  118.         Random random = new Random();
  119.         int N = 20;
  120.  
  121.         SelfOrganizingList list = new SelfOrganizingList(N);
  122.         for (int i = 0; i < N; i++)
  123.             list.insert(Math.abs(random.nextInt(1000)));
  124.  
  125.         Scanner scan = new Scanner(System.in);
  126.         System.out.println("SelfOrganizingList Searching \n");
  127.  
  128.         list.printList();
  129.  
  130.         System.out.println("\nEnter integer element to search");
  131.         System.out.println("Search Result : " + list.search(scan.nextInt()));
  132.  
  133.         scan.close();
  134.     }
  135. }

Output:

advertisement
$ javac Search_Self_Organizing.java
$ java Search_Self_Organizing
 
SelfOrganizingList Searching 
 
List = 855 318 462 851 373 360 811 401 813 50 291 346 707 118 633 217 715 594 999 99 
Count = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
Enter integer element to search
811
Search Result : true

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and 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.