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.

/*
 *  Java Program to Implement VList
 */
 
import java.util.Scanner;        
 
/*  Class Node  */
class VListNode
{
    VListNode next, prev;
    int numElements;
    int array[];
 
    /* Constructor */
    public VListNode(int n)
    {
        next = null;
        prev = null;
        numElements = 0;
        array = new int[n];        
    }
}
 
/* Class VList */
class VList
{
    private VListNode start;
    private VListNode end;
    private int nodeNumber;
    private int size;
 
    /* Constructor */
    public VList()
    {
        start = null;
        end = null;
        nodeNumber = 0;    
        size = 0;    
    }
    /*  Function to check if list is empty  */
    public boolean isEmpty()
    {
        return start == null;
    }
    /*  Function to get size of list  */
    public int getSize()
    {
        return size;
    }  
    /* Function to clear list */
    public void makeEmpty()
    {
        start = null;
        end = null;
        nodeNumber = 0;
        size = 0;
    }
    /* Function to insert element */
    public void insert(int x)
    {
        size++;
        int n = (int) Math.pow(2, nodeNumber);
        if (start == null)
        {
            start = new VListNode(n);
            start.array[0] = x;
            start.numElements++;
            end = start;
            return;
        }
        if (end.numElements + 1 <= n)
        {
            end.array[end.numElements] = x;
            end.numElements++;                        
        }
        else
        {
            nodeNumber++;
            n = (int) Math.pow(2, nodeNumber);            
            VListNode nptr = new VListNode(n);
            nptr.array[0] = x;
            nptr.numElements++;
            nptr.prev = end;
            end.next = nptr;
            end = nptr;                    
        }        
    }
    /* Function to get kth element */
    public int kthElement(int k)
    {
        if (k < 1 || k > size)
            throw new IndexOutOfBoundsException("No element present");
        k--;
        VListNode ptr = start;
        while (k >= ptr.numElements)
        {
            k -= ptr.numElements;
            ptr = ptr.next;
        }
        return ptr.array[k];
    }
    /* Function to display list */
    public void display()
    {
        System.out.print("\nVList = ");
        if (size == 0) 
        {
            System.out.print("empty\n");
            return;
        }
        System.out.println();
        VListNode ptr = start;
        int num = 0;
        while (ptr != null)
        {
            for (int i = 0; i < ptr.numElements; i++)
                System.out.print(ptr.array[i] +" ");
            System.out.println();            
            ptr = ptr.next;
            num++;
        }
    }
 
}
 
/*  Class VListTest */
public class VListTest
{    
    public static void main(String[] args)
    {             
        Scanner scan = new Scanner(System.in);
        System.out.println("VList Test\n");  
 
        /* Creating object of class VList */
        VList vl = new VList(); 
 
        char ch;
        /*  Perform list operations */
        do
        {
            System.out.println("\nVList Operations\n");
            System.out.println("1. insert");
            System.out.println("2. kth element");
            System.out.println("3. check empty");
            System.out.println("4. get size");  
            System.out.println("5. clear");            
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 :  
                System.out.println("Enter integer element to insert");
                vl.insert( scan.nextInt() );                     
                break;  
            case 2 :  
                try
                {
                    System.out.println("Enter postion");
                    System.out.println("\nK-th element = "+ vl.kthElement( scan.nextInt() ));                     
                }
                catch (Exception e)
                {
                    System.out.println("\nError : "+ e.getMessage() );
                }
                break;                        
            case 3 : 
                System.out.println("Empty status = "+ vl.isEmpty());
                break;                   
            case 4 : 
                System.out.println("Size = "+ vl.getSize() +" \n");
                break; 
            case 5 : 
                System.out.println("List Cleared\n");
                vl.makeEmpty();
                break;                        
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /*  Display List */ 
            vl.display();
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
}

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