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)
