VList

Implement an array that has flexible length. In other words, implement ArrayList in Java without using ArrayList.

• Implement 2 methods:
  • void append(T element) -> should be O(1)
  • T getByIndex(int index) -> should be O(log n)
• Full explanation:
  • http://www.keithschwarz.com/interesting/code/vlist/VList.java.html
• TL;DR:
  • ArrayList ditches previous arrays after a new longer array is created, VList save those previous arrays and link them together

Knowledge Points

• Do you know how does Java implement ArrayList, why is it implement that way (1, 2, 4, 8, 16...growth):
  • Java implement ArrayList by making a new Array with size * 2, then copy the original elements over.
  • append might be -> O(n)
  • get is always -> O(1)

Implementation

class VList<T> {

private VListCell<T> head;

int size;

private class VListCell<T> {

public T[] elems;

public VListCell<T> next;

public VListCell<T> prev;

public int count;

public VListCell(int numElems, VListCell<T> next){

this.elems = (T[]) new Object[numElems];

this.next = next;

this.prev = null;

if(next != null){

next.prev = this;

}

count = 0;

}

public boolean isFull(){

return this.count == elems.length;

}

}

public boolean add(T elem){

if(head == null || head.isFull()){

head = new VListCell<T>(head == null ? 1 : head.elems.length * 2, head);

}

head.elems[head.count++] = elem;

size++;

return true;

}

public T get(int index){

index = size - 1 - index; // find the reverse index

VListCell<T> cur = head;

while(index >= cur.count){

index -= cur.count;

cur = cur.next;

}

index = cur.count - index - 1;

return cur.elems[index];

}

}