comparing time performance: Array vs LinkedList vs ArrayList

[osa holwa]

My Professor asked us to compare the Time performance: Array vs LinkedList vs ArrayList.
we have to write following methods:
Add to front
Add to end
Iterate through n elements
delete first Element n times

I wrote the program but i don't know I have the feeling it is wrong.

public class PerformanceTest {
//variable declaration

int n;

//constructor
public PerformanceTest(int number) {
this.n = number;
}

//add Elements to front of ArrayLit and LinkedList
//the list is a List of Objects
//this method will write the Object obj
//n times to the Front of List
public void addToFrontList(List list) {
//creates new Object to add.
Object obj = new Object();
long start = System.currentTimeMillis();
//add Object at position 0, all elements will be
//moved to the right
for (int i = 0; i < this.n - 1; i++) {
list.add(0, obj);
}
System.out.println(System.currentTimeMillis() - start);
}

//adds Elements to front of Array
//this method will write the Object obj
//n times to the Front of the Array.
//All old Elements will be moved
// to the end of the New Array
public void addToFrontArray(Object[] tab) {
//creates new object
Object obj = new Object();
int vorIndex=tab.length;
tab = Arrays.copyOf(tab, this.n + tab.length);
int index = tab.length - 1;
long start = System.currentTimeMillis();
//moves all elements to the right of the new Array
for (int s = vorIndex; s >= 0; s--) {
tab[index] = tab[s];
index--;
}
//Writes n times object to Front of Array
for (int i = 0; i < n; i++) {
tab[i] = obj;
}
System.out.println(System.currentTimeMillis() - start);

}

private void addToEndArray(Object[] tab) {
//Creates new Object
Object obj = new Object();
//creates new Array of objects + makes array bigger
Object[] tabNew = Arrays.copyOf(tab, this.n + tab.length);
long start = System.currentTimeMillis();
//writes Elements in Array
for (int s = tab.length; s < tabNew.length; s++) {
tabNew[s] = obj;
}
System.out.println(System.currentTimeMillis() - start);

}

private void addToEndList(List list) {
//creates new Object to add.
Object obj = new Object();
long start = System.currentTimeMillis();
//add Object at position 0, all elements will be
//moved to the right
for (int i = 0; i < this.n; i++) {
list.add(obj);
}

System.out.println(System.currentTimeMillis() - start);
}

private void iterateArray(Object[] tab) {
Object j;
long start = System.currentTimeMillis();
for (int i = 0; i < this.n - 1; i++) {
j = tab[i];
}
System.out.println(System.currentTimeMillis() - start);
}

private void iterateArrayList(List list) {
Object j;
long start = System.currentTimeMillis();
for (int i = 0; i < this.n; i++) {
j = list.get(i);
}
System.out.println(System.currentTimeMillis() - start);
}

private void deleteArray(Object[] tab) {
long start = System.currentTimeMillis();
for (int i = 0; i < this.n; i++) {
tab = Arrays.copyOfRange(tab, 1, tab.length);
}
System.out.println(System.currentTimeMillis() - start);
}

private void deleteArrayList(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < this.n; i++) {
list.remove(0);
}
System.out.println(System.currentTimeMillis() - start);
}

public static void main(String[] args) {
PerformanceTest test = new PerformanceTest(100000);
ArrayList<Object> list = new ArrayList<Object>();
LinkedList<Object> linkedList = new LinkedList<Object>();
Object[] array = new Object[0];
System.out.println("Performance addtoFrontArray: Array");
test.addToFrontArray(array);
System.out.println("Performance addtoFrontList: ArrayList");
test.addToFrontList(list);
System.out.println("Performance addtoFrontlist: LinkedList");
test.addToFrontList(linkedList);
System.out.println("Performance addtoEndArray: Array");
test.addToEndArray(array);
System.out.println("Performance addtoEndlist: ArrayList");
test.addToEndList(list);
System.out.println("Performance addtoEndlist: LinkedList");
test.addToEndList(linkedList);


the Output for n=100000

Performance addtoFrontArray: Array
15
Performance addtoFrontList: ArrayList
6927
Performance addtoFrontlist: LinkedList
31
Performance addtoEndArray: Array
0
Performance addtoEndlist: ArrayList
16
Performance addtoEndlist: LinkedList
16

I don t anderstand why the performance when adding elements to front of array changes everytime that I execute the program and why the performance of addtoend = 0

[Campbell Ritchie]

Welcome to the Ranch

I am afraid your code is difficult to read; I would have improved it with code tags, but you haven’t indented it.

The reason for the 0 is probably that the milliseconds method does not have enough resolution to measure the time taken; some operating systems only work to the nearest 10 ms, so anything less will show as 0. There is a method in the System class which gives nanoseconds. It is not absolutely precise, but will probably give you time to the nearest μs, so try that method instead.
When you add something to the beginning or middle of an array, you have to move all subsequent elements. That is probably best done with the System#arraycopy() method (alternative link). You can add something to the beginning or end or middle of a linked list without moving anything else. There are several references to change in a linked list, but it is still faster than adding to the middle of an array.
It is very fast to add something to the end of an array, provided there are vacant slots in the array.

[Campbell Ritchie]

You should beware of anything taking ≥10000 repetitions. At that stage, the JVM will start to optimise the code by re-compiling it. Try each of your stages with 0, 1, 1000, 10000, 1000000 and 1000000 elements, and try them in different orders. You will see how performance varies.