List (Array + Linked)
ArrayList ve LinkedList aslında görünürde kağıt üzerinde aynı gibi dursalarda, birbirlerinden farklı yapılar. Daha doğrusu sınıflar. Ki bu farklılık mülakatlara bile konu olur. Herhangi bir java mülakatında; “Bize ArrayList ve LinkedList arasındaki farklılıkları söyleyebilir misiniz.?” diye soru gelmesi oldukça kuvvetle muhtemel.
Biraz bu sınıfları inceleyelim. Sonra farklarına geçelim.
Kağıt üzerinde bu yapıların aynı gibi gözükmesinin çok temel bir sebebi var aslında. En üstte bir Iterable interface’i vardır. Ki collection yapısının genel interface’idir. (Map yapıları hariç) Bu interface’i extend eden bir Collection interface’i vardır. Ve bu interface’i extend eden son interface ise List interface’idir. Hikayemiz temelde buradan başlar. Çünkü dolaylı olarak hem ArrayList, hem de LinkedList en üstte bu iki interfacei gerçekler. (Collection ve Iterable interface’lerini saymıyorum.) Aslında bir yerde bu benzerliklerin sebebi de budur. Temelde ihtiyacımız için kullandığımız methodlar aynıdır. add() methodu, her ikisinde de ekleme yapar. get() methodu her iki değer için de verilen indis değerini getirir. remove() methodu her ikisi için de silme işlemi yapar. (Tabiiki ArrayList ve LinkedList somut birer sınıf. Ve birbirlerinden farklı. Bu durumda birbirlerinden farklı methodlar barındırması çok doğal. Ama söylemeye çalıştığım şey, günün sonunda bizlere sunduğu yapılar itibariyle temel ihtiyaçlarımızı bu iki sınıfta da aynı şekilde giderdiğimiz.)
Zaten yapısal olarak bu iki sınıfın farklılıkları yukarıdaki şemadan bariz bir şekilde ortaya çıkıyor.
Peki çalışma mantığı olarak davranışları nasıl.?
Her iki sınıftan da bir nesne üretip içine eleman eklediğinizde, ArrayList index bazlı eleman ekler, LinkedList adres bazlı eleman ekler. Şematize edecek olursak, her ikisi için de şöyle bir görsel çıkacaktır ortaya.
Burada aslında dikkat edilmesi gereken hususlardan birisi şu. ArrayList’te veriler index bazlı eklenirken tek ihtiyaç duyulan şey bir index ve verinin kendisi. Ama LinkedList’te olay biraz daha değişiyor. Veriyi tutmak için verinin kendisinin haricinde, bör önceki verinin adresi ve bir sonraki verinin adresine de ihtiyaç duyuluyor.
Yukarıdaki görsellere bakarak 1 milyon veri için konuşursak, ArrayList için ayrılan RAM, LinkedList için gerekli RAM’den daha az olacaktır.
Aranılan elemana ulaşmak için ise;
mesela her iki veriyapımızda da 10 milyon tane eleman olduğunu varsayalım. ve 4987564. elemana ulaşmaya çalıştığımızı düşünelim. parametre olarak get methoduna bu sayıyı verdiğimizde ArrayList’te direkt olarak, verilen indexe gidip sonucu dönderir. Ama LinkedList’te durum daha farklıdır. Baştan başlar ve adresleri izleyerek o elemana gider. Yani elemana ulaşma süresi ArrayList’te daha azken, LinkedList’te daha fazladır.
Silme işleminde ise durum tam tersine döner. Mesela ArrayList’ten veriyi silerken sağdaki elemanların tamamı sol tarafa kayar. Ama LinkedList’te durum böyle değildir. Aradaki bağ kopar ve silinen elemanın bir öncesindeki eleman ile bir sonrasndaki eleman adresler ile birbirine bağlanır. Yani eleman silme işlemi linkedlist’te daha performnslıdır. (Çok önemli not: Burada belirtmeliyim ki bu durum case’lere göre değişir. Sonuçta elemanın silinmesi için söz konusu elemanın bulunması lazım. ArrayList’te eleman bulmak hızlıyken, LinkedList’te yavaştır. Silinecek eleman veriyapılarının ilk elemanıysa ona göre hesaplama, son elemanıysa ona göre bir hesaplama yapılır. Ortadan eleman silinecekse de ona göre bir hesaplama yapılır. Yani, elemanın bulunma süresini hesaba katmalıyız. Burada bahsedilen sadece silme kısmı.)
Ekleme işleminde de durum aslında silmedeki mantıkla aynı. ArrayList’e bir eleman eklenecekse (örn: ortaya eleman eklensin.) sağdaki elemanlar tamamen sağ tarafa, soldaki elemanlar tamamen sol tarafa shift olurlar ve eleman araya eklenir. Ama bu iş LinkedList’te yine aradaki bağlar yardımıyla çok kolay bir hal alıyor. 2 veri arasındaki bağlar kopar, soldaki verinin bir sonraki adresi eklenmek istenen elemanın sol taraftaki adresini, sağdaki verinin adresi ise, eklenmek istenen verinin sağ taraftaki adresini gösterir.
Şimdi bu iddialarımın doğruluğunu bir timer yardımıyla görmeye çalışalım.
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
double beginTimeElemanEklemeArrayListIcin = 0.0d;
double endTimeElemanEklemeArrayListIcin = 0.0d;
double resultElemanEklemeArrayListIcin = 0.0d;
double beginTimeElemanEklemeLinkedListIcin = 0.0d;
double endTimeElemanEklemeLinkedListIcin = 0.0d;
double resultElemanEklemeLinkedListIcin = 0.0d;
double beginTimeElemanBulmaArrayListIcın = 0.0d;
double endTimeElemanBulmaArrayListIcin = 0.0d;
double resultElemanBulmaArrayListIcin = 0.0d;
double beginTimeElemanBulmaLinkedListIcın = 0.0d;
double endTimeElemanBulmaLinkedListIcin = 0.0d;
double resultElemanBulmaLinkedListIcin = 0.0d;
double beginTimeBirinciSirayaElemanEklemeArrayListIcin = 0.0d;
double endTimeBirinciSirayaElemanEklemeArrayListIcin = 0.0d;
double resultBirinciSirayaElemanEklemeArrayListIcin = 0.0d;
double beginTimeBirinciSirayaElemanEklemeLinkedListIcin = 0.0d;
double endTimeBirinciSirayaElemanEklemeLinkedListIcin = 0.0d;
double resultBirinciSirayaElemanEklemeLinkedListIcin = 0.0d;
double beginTimeBirinciSiradanElemanSilmeArrayListIcin = 0.0d;
double endTimeBirinciSiradanElemanSilmeArrayListIcin = 0.0d;
double resultBirinciSiradanElemanSilmeArrayListIcin = 0.0d;
double beginTimeBirinciSiradanElemanSilmeLinkedListIcin = 0.0d;
double endTimeBirinciSiradanElemanSilmeLinkedListIcin = 0.0d;
double resultBirinciSiradanElemanSilmeLinkedListIcin = 0.0d;
double beginTimeArayaElemanEklemeArrayListIcin = 0.0d;
double endTimeArayaElemanEklemeArrayListIcin = 0.0d;
double resultArayaElemanEklemeArrayListIcin = 0.0d;
double beginTimeArayaElemanEklemeLinkedListIcin = 0.0d;
double endTimeArayaElemanEklemeLinkedListIcin = 0.0d;
double resultArayaElemanEklemeLinkedListIcin = 0.0d;
double beginTimeAradanElemanSilmeArrayListIcin = 0.0d;
double endTimeAradanElemanSilmeArrayListIcin = 0.0d;
double resultAradanElemanSilmeArrayListIcin = 0.0d;
double beginTimeAradanElemanSilmeLinkedListIcin = 0.0d;
double endTimeAradanElemanSilmeLinkedListIcin = 0.0d;
double resultAradanElemanSilmeLinkedListIcin = 0.0d;
double beginTimeSonuncuElemaniSilmeArrayListIcin = 0.0d;
double endTimeSonuncuElemaniSilmeArrayListIcin = 0.0d;
double resultSonuncuElemaniSilmeArrayListIcin = 0.0d;
double beginTimeSonuncuElemaniSilmeLinkedListIcin = 0.0d;
double endTimeSonuncuElemaniSilmeLinkedListIcin = 0.0d;
double resultSonuncuElemaniSilmeLinkedListIcin = 0.0d;
beginTimeElemanEklemeArrayListIcin = System.currentTimeMillis();
for (int i = 0; i <10000000 ; i++) {
arrayList.add(i);
}
endTimeElemanEklemeArrayListIcin = System.currentTimeMillis();
resultElemanEklemeArrayListIcin = endTimeElemanEklemeArrayListIcin - beginTimeElemanEklemeArrayListIcin;
beginTimeElemanEklemeLinkedListIcin = System.currentTimeMillis();
for (int i = 0; i <10000000 ; i++) {
linkedList.add(i);
}
endTimeElemanEklemeLinkedListIcin = System.currentTimeMillis();
resultElemanEklemeLinkedListIcin = endTimeElemanEklemeLinkedListIcin - beginTimeElemanEklemeLinkedListIcin;
System.out.println();
System.out.println("*** ON milyon tane eleman ekleme isleminde ***");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultElemanEklemeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultElemanEklemeLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeElemanBulmaArrayListIcın = System.currentTimeMillis();
int sonuncuArrayList = arrayList.get(arrayList.size() - 1);
endTimeElemanBulmaArrayListIcin = System.currentTimeMillis();
resultElemanBulmaArrayListIcin = endTimeElemanBulmaArrayListIcin - beginTimeElemanBulmaArrayListIcın;
beginTimeElemanBulmaLinkedListIcın = System.currentTimeMillis();
int sonuncuLinkedList = linkedList.get(linkedList.size() - 1);
endTimeElemanBulmaLinkedListIcin = System.currentTimeMillis();
resultElemanBulmaLinkedListIcin = endTimeElemanBulmaLinkedListIcin - beginTimeElemanBulmaLinkedListIcın;
System.out.println();
System.out.println("*** SONUNCU ELEMANI BULMA ISLEMI ICIN GECEN SURE ***");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultElemanBulmaArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultElemanBulmaLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeBirinciSirayaElemanEklemeArrayListIcin = System.currentTimeMillis();
arrayList.add(0, -50);
endTimeBirinciSirayaElemanEklemeArrayListIcin = System.currentTimeMillis();
resultBirinciSirayaElemanEklemeArrayListIcin = endTimeBirinciSirayaElemanEklemeArrayListIcin - beginTimeBirinciSirayaElemanEklemeArrayListIcin;
beginTimeBirinciSirayaElemanEklemeLinkedListIcin = System.currentTimeMillis();
linkedList.add(0, -50);
endTimeBirinciSirayaElemanEklemeLinkedListIcin = System.currentTimeMillis();
resultBirinciSirayaElemanEklemeLinkedListIcin = endTimeBirinciSirayaElemanEklemeLinkedListIcin - beginTimeBirinciSirayaElemanEklemeLinkedListIcin;
System.out.println();
System.out.println("*** BIRINCI SIRAYA ELEMAN EKLEME ICIN GECEN SURE *** ");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultBirinciSirayaElemanEklemeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultBirinciSirayaElemanEklemeLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeBirinciSiradanElemanSilmeArrayListIcin = System.currentTimeMillis();
arrayList.remove(0);
endTimeBirinciSiradanElemanSilmeArrayListIcin = System.currentTimeMillis();
resultBirinciSiradanElemanSilmeArrayListIcin = endTimeBirinciSiradanElemanSilmeArrayListIcin - beginTimeBirinciSiradanElemanSilmeArrayListIcin;
beginTimeBirinciSiradanElemanSilmeLinkedListIcin = System.currentTimeMillis();
linkedList.remove(0);
endTimeBirinciSiradanElemanSilmeLinkedListIcin = System.currentTimeMillis();
resultBirinciSiradanElemanSilmeLinkedListIcin = endTimeBirinciSiradanElemanSilmeLinkedListIcin - beginTimeBirinciSiradanElemanSilmeLinkedListIcin;
System.out.println();
System.out.println("*** BIRINCI SIRADAN ELEMAN SILME ICIN GECEN SURE *** ");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultBirinciSiradanElemanSilmeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultBirinciSiradanElemanSilmeLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeArayaElemanEklemeArrayListIcin = System.currentTimeMillis();
arrayList.add(7897424, -950);
endTimeArayaElemanEklemeArrayListIcin = System.currentTimeMillis();
resultArayaElemanEklemeArrayListIcin = endTimeArayaElemanEklemeArrayListIcin - beginTimeArayaElemanEklemeArrayListIcin;
beginTimeArayaElemanEklemeLinkedListIcin = System.currentTimeMillis();
linkedList.add(7897424, - 950);
endTimeArayaElemanEklemeLinkedListIcin = System.currentTimeMillis();
resultArayaElemanEklemeLinkedListIcin = endTimeArayaElemanEklemeLinkedListIcin - beginTimeArayaElemanEklemeLinkedListIcin;
System.out.println();
System.out.println("*** ARAYA ELEMAN EKLEME ICIN GECEN SURE *** ");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultArayaElemanEklemeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultArayaElemanEklemeLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeAradanElemanSilmeArrayListIcin = System.currentTimeMillis();
arrayList.remove(9632147);
endTimeAradanElemanSilmeArrayListIcin = System.currentTimeMillis();
resultAradanElemanSilmeArrayListIcin = endTimeAradanElemanSilmeArrayListIcin - beginTimeAradanElemanSilmeArrayListIcin;
beginTimeAradanElemanSilmeLinkedListIcin = System.currentTimeMillis();
linkedList.remove(9632147);
endTimeAradanElemanSilmeLinkedListIcin = System.currentTimeMillis();
resultAradanElemanSilmeLinkedListIcin = endTimeAradanElemanSilmeLinkedListIcin - beginTimeAradanElemanSilmeLinkedListIcin;
System.out.println();
System.out.println("*** ARADAN ELEMAN SILMEK ICIN GECEN SURE *** ");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultAradanElemanSilmeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultAradanElemanSilmeLinkedListIcin);
System.out.println();
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
beginTimeSonuncuElemaniSilmeArrayListIcin = System.currentTimeMillis();
arrayList.remove(arrayList.size() - 1);
endTimeSonuncuElemaniSilmeArrayListIcin = System.currentTimeMillis();
resultSonuncuElemaniSilmeArrayListIcin = endTimeSonuncuElemaniSilmeArrayListIcin - beginTimeSonuncuElemaniSilmeArrayListIcin;
beginTimeSonuncuElemaniSilmeLinkedListIcin = System.currentTimeMillis();
linkedList.remove(linkedList.size() - 1);
endTimeSonuncuElemaniSilmeLinkedListIcin = System.currentTimeMillis();
resultSonuncuElemaniSilmeLinkedListIcin = endTimeSonuncuElemaniSilmeLinkedListIcin - beginTimeSonuncuElemaniSilmeLinkedListIcin;
System.out.println();
System.out.println("*** SONUNCU ELEMANI SILMEK ICIN GECEN SURE *** ");
System.out.println();
System.out.println("ArrayList icin gecen zaman : " + resultSonuncuElemaniSilmeArrayListIcin);
System.out.println("LinkedList icin gecen zaman : " + resultSonuncuElemaniSilmeLinkedListIcin);
System.out.println();
}Kodumuz bu. Oluşabilecek case’leri koda ekledim.
Çıktımız ise şu şekilde oldu.
Tabiiki sonuç benim de beklediğim gibi çıkmadı ama çıkan sonuç mantık çerçevesi içerisinde. Şöyleki, Arada bir bağ oluşmasından dolayı LinkedList’e veri ekleme işleminin uzun sürmesini bekliyorduk. Bundan dolayı ArrayList daha hızlı çalıştı.
Sonuncu elemana ulaşma konusunda teorikte LinkedList daha yavaş çalışmalı ama benim bilgisayarımın RAM’inden kaynaklı düşündüğüm bir durumdan dolayı bura da her ikisinde de eşit sonuç aldık. Fakat, teorikte ArrayList daha performanslı sonuç verir. Hatta en kötü case’dir sonuncu elemana ulaşmak.
Birinci sıraya eleman ekleme işleminde ise yine beklediğimiz sonuç. Çünkü ArrayList’te bütün elemanlar sağa shift oldu ve daha yavaş çalıştı. Bu durum, ArrayList için en kötü case’dir.
Birinci sıradan eleman silme işlemi yine ArrayList’te çok yavaş çalıştı. Çünkü aynı mantıkla bu durum ArrayList için aslında en kötü case.
Araya eleman ekleme işleminde ise ArrayList daha performanslı fakat, elemanın ekleneceği indeksi bulma süresini de hesaba katacak olursak teorimizi doğrular nitelikte bir sonuç aldık. Çünkü ArrayList’e veri ekleme işlemi ile LinkedList’e veri ekleme işlemi arasında bir 10 kat kadar fark var ki bu da indeksi bulmamızla doğru orantılı diyebiliriz.
Aradan eleman silmek konusunda teorimiz “silme” işleminin ArrayList’te daha yavaş çalışacağıydı. Fakat aradan eleman silme konusunda elemanı bulma süresinden dolayı da böyle bir sonuç aldık. (Ki bu sonuçlarda, bilgisayarımın da etkisi var. 16 gb RAM ve Ryzen 7 işlemciye sahibim. Bu da bu süreleri çok daha kısa sürede yapıyor. Ki buradan da anlayacağımız üzere aslında bu işlemler bilgisayardan bilgisayara süre bazında farklılık gösterebilir.)
Sonuncu elemanı silme durumunda ise teorimiz gereği tabiki ArrayList’in daha performanslı çalışmasıydı ama yine bilgisayarın özelliklerinden dolayı böyle bir sonuçla karşılaştık.
Son olarak, ortaya bir iddia attım ve bu iddialar üzerine sonuçları gördük. Bazı sonuçlar farklı çıktı. Çok araştırmama rağmen buraya yazacak kadar değerli bilgiler edinemedim farklı sonuçlarla alakalı. Lütfen bu konu hakkındaki bilgilerinizi benimle paylaşınız.
Okuduğunuz için teşekkür ederim.
Java ile Kalın. (:
İletişim, İşbirlikleri ve Teklifler için
github: https://github.com/frknshnklksz
twitter: https://twitter.com/frknshnklksz
gmail: furkansahinkulaksiz@gmail.com
