VList is a data structure that combines fast indexing of arrays with the easy extension of singly-linked lists. VList generally supports the following functions.
- Insert Element
- Get Element at index k
- Clear List
- Display List
- Etc.
VList has rows connected as Singly Linked List where the Nth row contains maximum 2^N elements.
Example:
VList: [2] ↓ [1, 3] ↓ [5, 1, 5, 8] ↓ [10, 12, 5, 9, 1, 0, 8, 7] ↓ [3, 5, 7]
VList is Filled first Left to Right Then Top to Bottom.
Implementation:
Java
// Java Program to Implement VList  import java.io.*;import java.util.*;  // This will act as each row of VListclass VListNode {    VListNode next;    List<Integer> list;      public VListNode()    {        next = null;        list = new ArrayList<Integer>();    }}  class VList {      private VListNode start;    private VListNode end;    private int nodeNumber;    private int size;      // Constructor of VList    public VList()    {        start = null;        end = null;        nodeNumber = 0;        size = 0;    }      // Check if VList is Empty or Not    public boolean isEmpty() { return start == null; }      // Get Number of Elements in VList    public void getSize()    {        System.out.println("VList size : " + size);        System.out.println();    }      // Make VList Empty    public void clearVList()    {        start = null;        end = null;        nodeNumber = 0;        size = 0;          System.out.println("VList is Cleared");        System.out.println();    }      // Insert a new Element in VList    public void insert(int x)    {        size++;        int n = (int)Math.pow(2, nodeNumber);          if (start == null) {            start = new VListNode();            start.list.add(x);            end = start;            return;        }          if (end.list.size() + 1 <= n) {            end.list.add(x);        }        else {            nodeNumber++;              VListNode tempNode = new VListNode();            tempNode.list.add(x);              end.next = tempNode;            end = tempNode;        }    }      // Get value of Element at index k in VList    public void searchElementWithPosition(int k)    {        System.out.print("Element at position " + k                         + " is = ");          if (k < 1 || k > size) {            System.out.println("Does not Exist");            System.out.println();            return;        }          k--;        VListNode startTemp = start;          while (k >= startTemp.list.size()) {            k -= startTemp.list.size();            startTemp = startTemp.next;        }          System.out.println(startTemp.list.get(k));        System.out.println();    }      // Print full VList    public void displayVList()    {        System.out.print("VList : ");        if (size == 0) {            System.out.print("empty\n");            return;        }          System.out.println();          VListNode startTemp = start;        int num = 0;          while (startTemp != null) {            for (int i = 0; i < startTemp.list.size();                 i++) {                System.out.print(startTemp.list.get(i)                                 + " ");            }              System.out.println();              startTemp = startTemp.next;            num++;        }          System.out.println();    }}  class GFG {    public static void main(String[] args)    {        // Driver Code          // Initialize Vlist        VList vlist = new VList();          int[] arr            = new int[] { 9, 1, 5, 4, 3, 5, 2, 1, 0, 8 };          // Insert Elements in VList        for (int val : arr) {            vlist.insert(val);        }          // Display VList        vlist.displayVList();          // Search 1st Element        vlist.searchElementWithPosition(1);          // Search 5th Element        vlist.searchElementWithPosition(5);          // Search 8th Element        vlist.searchElementWithPosition(8);          vlist.getSize();          // Make List Empty        vlist.clearVList();          System.out.println("Vlist IsEmpty = "                           + vlist.isEmpty());    }} |
Output
VList : 9 1 5 4 3 5 2 1 0 8 Element at position 1 is = 9 Element at position 5 is = 3 Element at position 8 is = 1 VList size : 10 VList is Cleared Vlist IsEmpty = true
Time Complexity:
- Insert operation: O(1)Â
- Search operation: O(log(n))
- Display: O(n)
- Get Size & Check Empty: O(1)
