Java Program to Implement Vlist

This is a Java Program to implement a VList. VList is a persistent data structure that combines the fast indexing of arrays with the easy extension of cons-based (or singly linked) linked lists.

Here is the source code of the Java program to implement a VList. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *  Java Program to Implement VList
  3.  */
  4.  
  5. import java.util.Scanner;        
  6.  
  7. /*  Class Node  */
  8. class VListNode
  9. {
  10.     VListNode next, prev;
  11.     int numElements;
  12.     int array[];
  13.  
  14.     /* Constructor */
  15.     public VListNode(int n)
  16.     {
  17.         next = null;
  18.         prev = null;
  19.         numElements = 0;
  20.         array = new int[n];        
  21.     }
  22. }
  23.  
  24. /* Class VList */
  25. class VList
  26. {
  27.     private VListNode start;
  28.     private VListNode end;
  29.     private int nodeNumber;
  30.     private int size;
  31.  
  32.     /* Constructor */
  33.     public VList()
  34.     {
  35.         start = null;
  36.         end = null;
  37.         nodeNumber = 0;    
  38.         size = 0;    
  39.     }
  40.     /*  Function to check if list is empty  */
  41.     public boolean isEmpty()
  42.     {
  43.         return start == null;
  44.     }
  45.     /*  Function to get size of list  */
  46.     public int getSize()
  47.     {
  48.         return size;
  49.     }  
  50.     /* Function to clear list */
  51.     public void makeEmpty()
  52.     {
  53.         start = null;
  54.         end = null;
  55.         nodeNumber = 0;
  56.         size = 0;
  57.     }
  58.     /* Function to insert element */
  59.     public void insert(int x)
  60.     {
  61.         size++;
  62.         int n = (int) Math.pow(2, nodeNumber);
  63.         if (start == null)
  64.         {
  65.             start = new VListNode(n);
  66.             start.array[0] = x;
  67.             start.numElements++;
  68.             end = start;
  69.             return;
  70.         }
  71.         if (end.numElements + 1 <= n)
  72.         {
  73.             end.array[end.numElements] = x;
  74.             end.numElements++;                        
  75.         }
  76.         else
  77.         {
  78.             nodeNumber++;
  79.             n = (int) Math.pow(2, nodeNumber);            
  80.             VListNode nptr = new VListNode(n);
  81.             nptr.array[0] = x;
  82.             nptr.numElements++;
  83.             nptr.prev = end;
  84.             end.next = nptr;
  85.             end = nptr;                    
  86.         }        
  87.     }
  88.     /* Function to get kth element */
  89.     public int kthElement(int k)
  90.     {
  91.         if (k < 1 || k > size)
  92.             throw new IndexOutOfBoundsException("No element present");
  93.         k--;
  94.         VListNode ptr = start;
  95.         while (k >= ptr.numElements)
  96.         {
  97.             k -= ptr.numElements;
  98.             ptr = ptr.next;
  99.         }
  100.         return ptr.array[k];
  101.     }
  102.     /* Function to display list */
  103.     public void display()
  104.     {
  105.         System.out.print("\nVList = ");
  106.         if (size == 0) 
  107.         {
  108.             System.out.print("empty\n");
  109.             return;
  110.         }
  111.         System.out.println();
  112.         VListNode ptr = start;
  113.         int num = 0;
  114.         while (ptr != null)
  115.         {
  116.             for (int i = 0; i < ptr.numElements; i++)
  117.                 System.out.print(ptr.array[i] +" ");
  118.             System.out.println();            
  119.             ptr = ptr.next;
  120.             num++;
  121.         }
  122.     }
  123.  
  124. }
  125.  
  126. /*  Class VListTest */
  127. public class VListTest
  128. {    
  129.     public static void main(String[] args)
  130.     {             
  131.         Scanner scan = new Scanner(System.in);
  132.         System.out.println("VList Test\n");  
  133.  
  134.         /* Creating object of class VList */
  135.         VList vl = new VList(); 
  136.  
  137.         char ch;
  138.         /*  Perform list operations */
  139.         do
  140.         {
  141.             System.out.println("\nVList Operations\n");
  142.             System.out.println("1. insert");
  143.             System.out.println("2. kth element");
  144.             System.out.println("3. check empty");
  145.             System.out.println("4. get size");  
  146.             System.out.println("5. clear");            
  147.             int choice = scan.nextInt();            
  148.             switch (choice)
  149.             {
  150.             case 1 :  
  151.                 System.out.println("Enter integer element to insert");
  152.                 vl.insert( scan.nextInt() );                     
  153.                 break;  
  154.             case 2 :  
  155.                 try
  156.                 {
  157.                     System.out.println("Enter postion");
  158.                     System.out.println("\nK-th element = "+ vl.kthElement( scan.nextInt() ));                     
  159.                 }
  160.                 catch (Exception e)
  161.                 {
  162.                     System.out.println("\nError : "+ e.getMessage() );
  163.                 }
  164.                 break;                        
  165.             case 3 : 
  166.                 System.out.println("Empty status = "+ vl.isEmpty());
  167.                 break;                   
  168.             case 4 : 
  169.                 System.out.println("Size = "+ vl.getSize() +" \n");
  170.                 break; 
  171.             case 5 : 
  172.                 System.out.println("List Cleared\n");
  173.                 vl.makeEmpty();
  174.                 break;                        
  175.             default : 
  176.                 System.out.println("Wrong Entry \n ");
  177.                 break;   
  178.             }
  179.             /*  Display List */ 
  180.             vl.display();
  181.  
  182.             System.out.println("\nDo you want to continue (Type y or n) \n");
  183.             ch = scan.next().charAt(0);                        
  184.         } while (ch == 'Y'|| ch == 'y');               
  185.     }
  186. }

VList Test
 
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
28
 
VList =
28
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
5
 
VList =
28
5
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
19
 
VList =
28
5 19
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
63
 
VList =
28
5 19
63
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
14
 
VList =
28
5 19
63 14
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
7
 
VList =
28
5 19
63 14 7
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
19
 
VList =
28
5 19
63 14 7 19
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
70
 
VList =
28
5 19
63 14 7 19
70
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
1
 
VList =
28
5 19
63 14 7 19
70 1
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
5
 
VList =
28
5 19
63 14 7 19
70 1 5
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
90
 
VList =
28
5 19
63 14 7 19
70 1 5 90
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
67
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
87
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
2
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87 2
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
99
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87 2 99
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
1
Enter integer element to insert
24
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87 2 99
24
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
2
Enter postion
5
 
K-th element = 14
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87 2 99
24
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
4
Size = 16
 
 
VList =
28
5 19
63 14 7 19
70 1 5 90 67 87 2 99
24
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
5
List Cleared
 
 
VList = empty
 
Do you want to continue (Type y or n)
 
y
 
VList Operations
 
1. insert
2. kth element
3. check empty
4. get size
5. clear
3
Empty status = true
 
VList = empty
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

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

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

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 & discussions at Telegram SanfoundryClasses.