VList

VList#

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

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];
}
}