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.

//This is a java program to search an element in self organizing lists

```
import java.util.Random;
```
```
import java.util.Scanner;
```
```
 
```
```
class SelfOrganizingList 
```
```
{
```
```
    private int[] list;
```
```
    private int[] count;
```
```
    private int size;
```
```
 
```

    public SelfOrganizingList(int listSize)

```
    {
```
```
        list = new int[listSize];
```
```
        count = new int[listSize];
```
```
        size = 0;
```
```
    }
```
```
 
```
```
    public boolean isEmpty() 
```
```
    {
```
```
        return size == 0;
```
```
    }
```
```
 
```
```
    public boolean isFull() 
```
```
    {
```
```
        return size == list.length;
```
```
    }
```
```
 
```
```
    public void makeEmpty() 
```
```
    {
```
```
        int l = list.length;
```
```
        list = new int[l];
```
```
        count = new int[l];
```
```
        size = 0;
```
```
    }
```
```
 
```
```
    public int getSize() 
```
```
    {
```
```
        return size;
```
```
    }
```
```
 
```
```
    public void insert(int val) 
```
```
    {
```
```
        if (isFull()) 
```
```
        {
```

            System.out.println("Error : List full!");

```
            return;
```
```
        }
```
```
        list[size] = val;
```
```
        count[size] = 0;
```
```
        size++;
```
```
    }
```
```
 
```
```
    public void remove(int pos) 
```
```
    {
```
```
        pos--;
```
```
        if (pos < 0 || pos >= size) 
```
```
        {
```

            System.out.println("Invalid position ");

```
            return;
```
```
        }
```

        for (int i = pos; i < size - 1; i++)

```
        {
```
```
            list[i] = list[i + 1];
```
```
            count[i] = count[i + 1];
```
```
        }
```
```
        size--;
```
```
    }
```
```
 
```
```
    public boolean search(int x) 
```
```
    {
```
```
        boolean searchResult = false;
```
```
        int pos = -1;
```
```
        for (int i = 0; i < size; i++) 
```
```
        {
```
```
            if (list[i] == x) {
```
```
                searchResult = true;
```
```
                pos = i;
```
```
                break;
```
```
            }
```
```
        }
```
```
        if (searchResult) 
```
```
        {
```
```
            count[pos]++;
```
```
            int c = count[pos];
```

            for (int i = 0; i < pos; i++)

```
            {
```

                if (count[pos] > count[i])

```
                {
```

                    for (int j = pos; j > i; j--)

```
                    {
```

                        list[j] = list[j - 1];

                        count[j] = count[j - 1];

```
                    }
```
```
                    list[i] = x;
```
```
                    count[i] = c;
```
```
                    break;
```
```
                }
```
```
            }
```
```
        }
```
```
        return searchResult;
```
```
    }
```
```
 
```
```
    public void printList() 
```
```
    {
```
```
        System.out.print("\nList = ");
```
```
        for (int i = 0; i < size; i++)
```

            System.out.print(list[i] + " ");

```
        System.out.print("\nCount = ");
```
```
        for (int i = 0; i < size; i++)
```

            System.out.print(count[i] + " ");

```
    }
```
```
}
```
```
 
```
```
public class Search_Self_Organizing 
```
```
{
```

    public static void main(String[] args)

```
    {
```
```
        Random random = new Random();
```
```
        int N = 20;
```
```
 
```

        SelfOrganizingList list = new SelfOrganizingList(N);

```
        for (int i = 0; i < N; i++)
```

            list.insert(Math.abs(random.nextInt(1000)));

```
 
```

        Scanner scan = new Scanner(System.in);

        System.out.println("SelfOrganizingList Searching \n");

```
 
```
```
        list.printList();
```
```
 
```

        System.out.println("\nEnter integer element to search");

        System.out.println("Search Result : " + list.search(scan.nextInt()));

```
 
```
```
        scan.close();
```
```
    }
```
```
}
```

Output:

$ 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.

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

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Quick Sort using Randomization

» Next - Java Program to Find Second Smallest of n Elements with Complexity Constraint

Related Posts:

Recommended Articles: