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.

advertisement
advertisement

Here’s the list of Best Reference Books in Java Programming, Data Structures and Algorithms.

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter