Comparison Between ArrayList and LinkList

I have seen Java developers are confuse when they need to use collections, especially when there are multiple option. Without knowing the detail of Collections you want to use would make selection harder. Here we go when you need to select either ArrayList or LinkList. Using LinkList and ArrayList is pretty much same except few things to consider,

Array List Usage:  

• Getting an element by Index is super-Fast, use get(index) method.
• Insertion Value could be slow, especially when you reach at last element, Array List use array behind the screen, so once you reach at limit , it will create another array with larger size and move already added elements, but if you know the expected number of element you can define capacity when initializing Array List
• Adding Values in mid would take time, as it would need to drift all elements in array.

Link List: Usage:

• Addition / Insertion is super fast because in Link list each element has link to next element, so adding , deleting elements would be really fast.
• Weak part for Link List is getting element at any position, even if you use get index method, it would iterate all elements until reach at that position .

Also, make sure you use iterator which is pretty fast to get all elements.

So I have a code which calculate time in (ms) while using Iterator or For Loop with both ArrayList and LinkList, NEVER use for Loop for LinkList.

[code language=”java”] /*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package performancetest;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
*
* @author ukhan
*/
public class PerformanceTest {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {

int numOfData = 90000;

LinkedList linkList = new LinkedList();
ArrayList arrayList = new ArrayList();

// Filling Random Data
long t = System.currentTimeMillis();
populateLinkList(numOfData, linkList);
t = System.currentTimeMillis() – t;

System.out.println("Insertion Time Taken for LinkList = " + t + "(ms)");

t = System.currentTimeMillis();
populateArray(numOfData, arrayList);
t = System.currentTimeMillis() – t;

System.out.println("Insertion Time Taken for ArrayList = " + t + "(ms)");

t = System.currentTimeMillis();

for (int i = 0; i != numOfData; i++) {
linkList.get(i);
}

t = System.currentTimeMillis() – t;

System.out.println("Time Taken for LinkList with get(index) method in For Loop = " + t + "(ms)");

t = System.currentTimeMillis();
for (Iterator itr = linkList.iterator();
itr.hasNext();) {
itr.next();
}
t = System.currentTimeMillis() – t;

System.out.println("Time Taken for LinkedList with Iterator = " + t + "(ms)");

t = System.currentTimeMillis();
for (int i = 0; i != numOfData; i++) {
arrayList.get(i);
}

t = System.currentTimeMillis() – t;
System.out.println("Time Taken for ArrayList with get(index) method in For Loop= " + t + "(ms)");

//Using iterator
t = System.currentTimeMillis();
for (Iterator itr = arrayList.iterator();
itr.hasNext();) {
itr.next();
}
t = System.currentTimeMillis() – t;
System.out.println("Time Taken for ArrayList with Iterator = " + t + "(ms)");

}
public static void populateRandom(int numOfData, LinkedList linkedLst , ArrayList arrayList){
for (int m = 0; m != numOfData; m++) {
int x = (int) Math.random();
linkedLst.add(x);
arrayList.add(x);
}
}

public static void populateArray(int numOfData , ArrayList arrayList){
for (int m = 0; m != numOfData; m++) {
int x = (int) Math.random();

arrayList.add(x);
}
}

public static void populateLinkList(int numOfData, LinkedList linkedLst ){
for (int m = 0; m != numOfData; m++) {
int x = (int) Math.random();
linkedLst.add(x);
}
}
}
[/code]

Comments

comments