Java Program to Implement Sparse Array

«
»
This Java program is to Implement Sparse array. In computer science, a sparse array is an array in which most of the elements have the same value (known as the default value—usually 0 or null). The occurrence of zero elements in a large array is inefficient for both computation and storage. An array in which there is a large number of zero elements is referred to as being sparse.
Here is the source code of the Java program to implement sparse array. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
  1. class List
  2. {
  3.     private int index;
  4.     private Object value;
  5.     private List nextindex;
  6.  
  7.     public List(int index)
  8.     {
  9.         this.index = index;
  10.         nextindex = null;
  11.         value = null;
  12.     }
  13.  
  14.     public List()
  15.     {
  16.         index = -1;
  17.         value = null;
  18.         nextindex = null;
  19.     }
  20.  
  21.     public void store(int index, Object value)
  22.     {
  23.         List current = this;
  24.         List previous = null;
  25.  
  26.         List node = new List(index);
  27.         node.value = value;
  28.  
  29.         while (current != null && current.index < index)
  30.         {
  31.             previous = current;
  32.             current = current.nextindex;
  33.         }
  34.  
  35.         if (current == null)
  36.         {
  37.             previous.nextindex = node;
  38.         } else
  39.         {
  40.             if (current.index == index)
  41.             {
  42.                 System.out.println("DUPLICATE INDEX");
  43.                 return;
  44.             }
  45.             previous.nextindex = node;
  46.             node.nextindex = current;
  47.         }
  48.         return;
  49.     }
  50.  
  51.     public Object fetch(int index)
  52.     {
  53.         List current = this;
  54.         Object value = null;
  55.         while (current != null && current.index != index)
  56.         {
  57.             current = current.nextindex;
  58.         }
  59.         if (current != null)
  60.         {
  61.             value = current.value;
  62.         } else
  63.         {
  64.             value = null;
  65.         }
  66.         return value;
  67.     }
  68.  
  69.     public int elementCount()
  70.     {
  71.         int elementCount = 0;
  72.         for (List current = this.nextindex; (current != null); current = current.nextindex)
  73.         {
  74.             elementCount++;
  75.         }
  76.         return elementCount;
  77.     }
  78. }
  79.  
  80. public class SparseArray
  81. {
  82.     private List start;
  83.     private int index;
  84.  
  85.     SparseArray(int index)
  86.     {
  87.         start = new List();
  88.         this.index = index;
  89.     }
  90.  
  91.     public void store(int index, Object value)
  92.     {
  93.         if (index >= 0 && index < this.index)
  94.         {
  95.             if (value != null)
  96.                 start.store(index, value);
  97.         } else
  98.         {
  99.             System.out.println("INDEX OUT OF BOUNDS");
  100.         }
  101.     }
  102.  
  103.     public Object fetch(int index)
  104.     {
  105.         if (index >= 0 && index < this.index)
  106.             return start.fetch(index);
  107.         else 
  108.         {
  109.             System.out.println("INDEX OUT OF BOUNDS");
  110.             return null;
  111.         }
  112.     }
  113.  
  114.     public int elementCount()
  115.     {
  116.         return start.elementCount();
  117.     }
  118.  
  119.     public static void main(String... arg)
  120.     {
  121.         Integer[] iarray = new Integer[5];
  122.         iarray[0] = 1;
  123.         iarray[1] = null;
  124.         iarray[2] = 2;
  125.         iarray[3] = null;
  126.         iarray[4] = null;
  127.  
  128.         SparseArray sparseArray = new SparseArray(5);
  129.         for (int i = 0; i < iarray.length; i++)
  130.         {
  131.             sparseArray.store(i, iarray[i]);
  132.         }
  133.  
  134.         System.out.println("NORMAL ARRAY");
  135.         for (int i = 0 ; i < iarray.length; i++)
  136.         {
  137.             System.out.print(iarray[i] + "\t");
  138.         }
  139.  
  140.         System.out.println("\nSPARSE ARRAY");
  141.         for (int i = 0; i < iarray.length; i++)
  142.         {
  143.             if (sparseArray.fetch(i) != null)
  144.                 System.out.print(sparseArray.fetch(i) + "\t");
  145.         }
  146.         System.out.println("The Size of Sparse Array is " + sparseArray.elementCount());
  147.     }
  148. }


$javac SparseArray.java
$java SparseArray
 
NORMAL ARRAY
1	null	2	null	null	
SPARSE ARRAY
1	2	
The Size of Sparse Array 2

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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