Operasi Java Arraylist vs Linkedlist

Jika kita browsing di internet maka akan kita dapati bahwa linkedlist itu lebih bagus dalam proses insert dan remove sedangkan arraylist lebih bagus dalam proses get data. Mengapa sih arraylist lebih bagus (lebih cepat) dalam beberapa operasi jika dibandingkan linkedlist ? dan apa sih beda kodingan antara arraylist dan linkedlist ? dalam artikel berikut akan dibahas sedikit arraylist vs linkedlist.

Sebelum masuk kepembahasan, kita akan bahas sedikit dengan O-Notation, dalam buku “Java Generics and Collections halaman 150” ada pernyataan “The O-notation is a way of describing the perormance of an algorithm in an abstract way, without the detail required to predict the precise performance of a particular program running on a particular machine. Our main reason for using it is that it gives us a way of describing how the execution time for an algorithm depends on the size of its data set, provided the data set is large enough”. Bisa di simpulkan bahwa O-Notation adalah pengaruh data set terhadap lama waktu sebuah algoritma dieksekusi. algoritma disini biasanya berupa method atau fungsi.

Table O-Notation dari Buku “Java Generics and Collections” hal. 151

Dari table diatas sudah kelihatan jelas maksud O(1), O(N) dan lain lain.

Berikut adalah contoh kodingan konsep O-notation:

public class NotaionTest {
 private int[] arr = {1,2,3,4,5,6,7,8};
 
 public int getData(int item) {
  return arr[item];
 }
 public void printData() {
  for (int i = 0; i < arr.length; i++) {
   System.out.println(arr[i]);
  }
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  NotaionTest tes = new NotaionTest();
  tes.getData(2);
  tes.printData();
 }
 
}

Pada kodingan diatas, method getData biasa dikatakan O(1) karena berapapun panjang arraynya waktu eksekusi akan konstan. Sedangkan method printData bisa dikatakan O(N) karena panjang array mempengaruhi lama waktu eksekusi method tersebut.

Sekarang kembali ke Arraylist vs Linkedlist, berikut adalah table komparasi arraylist vs linkedlist.

Dari buku Java Generics and Collections

Selanjutnya saya ingin sedikit membuktikan kecepatan method arraylist vs linkedlist dalam nano second, tentu saja ini tergantung kemampuan processor PC / server.

https://github.com/wahyueko22/unit-test-java-collection/blob/master/src/main/java/Main.java

hasil test kodingan github diatas adalah sebagai berikut (dalam nano second ) :

elapsed time ArrayList add = 3067700 ns
elapsed time ArrayList get = 9400 ns
elapsed time ArrayList remove = 12400 ns
elapsed time LinkedList add = 759900 ns
elapsed time LinkedList get = 23100 ns
elapsed time LinkedList remove = 10100 ns

Dari hasil test terlihat arraylist menang di get sedangkan linkedlist menang di add dan remove. Selanjutnya apa yang membuat beda antara arraylist dan linkedlist. Arraylist dari namanya saja sudah kelihatan bahwa basic dari arraylist adalah array, sedangkan linkedlist basicnya adalah object yang saling berkaitan (lebih detail bisa di baca di java doc).

Berikut adalah contoh sederhana arraylist yang basicnya array :

public class MockArrayList<E> {
 transient Object[] elementData;
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 private int index;
 private int defaultIncrement = 10;
public MockArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
public void add(E item) { 
  ensureExplicitCapacity();
  elementData[index++] = item;
 }
private void ensureExplicitCapacity() {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   Object[] tempData = new Object[defaultIncrement];
   elementData = tempData;
  } else if (elementData.length <= index) {
   int newIncrement = index + (index >> 1);
   System.out.println("old index = "+ index + " ||  newIncrement = " + newIncrement);
   Object[] tempData = new Object[newIncrement];
   for (int i = 0; i < elementData.length; i++) {
    tempData[i] = elementData[i];
   }
   elementData = tempData;
  }
 }
public E getItem(int idx) {
  E val=null;
  this.checkIndex(idx);
  for(int i=0; i<this.index; i++) {
   if(idx == i)
    val = (E) this.elementData[idx];
  }
  return val;
 }
}

Pada kodingan diatas, pada kontruktor dedifinikan array dengan type of object.

Berikut adalah contoh sederhana linkedlist yang basicnya object :

public class ModelLinked<E> {
 E item;
 ModelLinked<E> prev;
 ModelLinked<E> next;
  
 public ModelLinked(E item, ModelLinked<E> prev, ModelLinked<E> next) {
  super();
  this.item = item;
  this.prev = prev;
  this.next = next;
 }
 //getter settet
}

Kodingan diatas adalah contoh object linkedlist yang saling berkaitan. Property prev berisi object sebelum, property next berisi object berikutnya. Implemtasi object diatas adalah sebagai berikut :

public class MockLinkedList<E> {
 private ModelLinked<E> firstValue;
 private ModelLinked<E> lastValue;
 private int size;
public void add(E item) {
  ModelLinked<E> last = lastValue;
  ModelLinked<E> newData = new ModelLinked<E>(item, last, null);
  lastValue = newData;
  if (last == null) {
   firstValue = newData;
  } else {
   lastValue.setNext(newData);
  }
  size++;
 }
public E get(int index) {
  checkElementSize(index);
  return node(index).item;
 }
 
 ModelLinked<E> node(int index) {
        if (index < (size >> 1)) {
         ModelLinked<E> x = firstValue;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
         ModelLinked<E> x = lastValue;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
private void checkElementSize(int index) {
  if (!(index >= 0 && index < size)) {
   throw new IndexOutOfBoundsException("eeroor");
  }
 }
}

source github : https://github.com/wahyueko22/unit-test-java-collection/tree/master/src/main/java