Merhabalar.

List Implementation ArrayList yazısında List arabirimini uygulayan bir sınıf olan ArrayList’i görmüştük. Bu yazıda ise bir başka List Implementation olan LinkedList‘i ve ArrayList ile LinkedList’in farklarını ve benzer yönlerini öğreneceğiz.

LinkedList List arabiriminin çift bağlatılı uygulamasıdır. Çift bağlı liste içerisindeki hücreler hem kendinden öncekini hem de kendinden sonraki işaret eden işaretçilere sahiptir. LinkedList İsteğe bağlı tüm list işlemlerini uygular, Null da dahil olmak üzere tüm elemanlara izin verir.

ArrayList gibi LinkedList sınıfı da varsayılan olarak Synchronized özelliğine sahip değildir. Bir LinkedList nesnesinin senkronize olabilmesi için şöyle bir kod kullanmamız gerekmektedir:

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList sınıfının iki adet yapılandırıcısı bulunmaktadır.

  • new LinkedList() : Boş bir LinkedList nesnesi oluşturur.
  • new LinkedList(Collection<? extends E> c) : Parametre olarak verilen Collection’ı kendisine dahil ederek yeni bir LinkedList nesnesi oluşturur.

Peki ArrayList ile LinkedList’in farkı nedir? Şimdi bu sorunun cevabına bakalım.

  1. En temel farkları List arabirimini uygulama (implementation) etme şekilleri. ArrayList yeniden boyutlandırılabilir bir dizi olarak uygularken, LinkedList veri yapılarından tanıdığımız çift bağlı listeyi temel alarak List arabirimini uygular.
  2. Performans bakımından karşılaştırılacak olunursa operasyonel olarak bakılmalıdır.
    • a) get(int index): ArrayList sınıfından oluşturulmuş bir nesne üzerinde get (int index) metodunun çalıştırılması O(1) sabit zamanını alırken LinkedList üzerinde get(int index) metodunun çalıştırılması O(n) zaman almaktadır. Bu duruma sebep olan şey ArrayList’in Array tabanlı olması ve index tabanlı yapıyı doğrudan kullanabilmesidir. LinkedList ise belirlenen index’deki veriye doğrudan ulaşmayı sağlamaz. Bunun yerine listedeki elemanları dolaşarak ulaşır. Örneğin 5 elemanlı bir LinkedList nesnemiz varsa ve siz de get(4); metodunu çalştırırsanız önce ilk 4 eleman üzerinden geçilir sonra istediğiniz eleman size verilir.
    • b) add(Object Object): LinkedList’e veri eklemek ArrayList’e göre oldukça hızlıdır. LinkedList’de veri ekleme işlemi O(1) zaman alır. ArrayList’de durum iki yönden değerlendirilmelidir. Eğer listemiz boş ise O(1) zaman alır. Eğer liste kapasitesine ulaşmış ise listenin boyutunun arttırılması ve mevcut verilerin kopyalanması işlemi işin içine gireceğinden, ki bu worst-case yani en kötü durum olarak kabul edilir, O(n) zaman alır.
    • c) remove(int index): Remove operasyonu her iki sınıf objesinde de O(n) zamanda gerçekleşmektedir ama burada bir parantez açmak gerekiyor. LinkedList sınıfında iki adet remove metodu yer almaktadır. Birisi parametre almayan (remove(); ) metodudur ki bu metot listenin başındaki elemanı siler. Bu sayede işlemini O(1) zamanda koşturabilir. Fakat diğer remove metodu silinmek istenen veriyi yahut o verinin indexini alabilir. Bu durumda LinkedList objesi üzerinde dolaşma gerekeceğinden (iterasyon) işlem O(n) zamanda koşturulur. ArrayList’de ise veriyi yahut verinin indexini parametre olarak alıp işlemi gerçekleştiren bir remove metodu yer almaktadır. Bu metot da her ne kadar ArrayList’de doğrudan indis bazlı işlem yapma yeteneği olsa da Array tabanlı olması, veri silinecek eski eleman yeni bir diziye kopyalanacak, nedeni ile işlemini O(n) zamanda gerçekleştirir.

  3. Listeyi tersten gezinme işlemi için LinkedList sınıfı içerisinde descendingIterator() isimli bir metot yer almaktadır. Sadece bu metot vasıtası ile liste tersten okunabilinir. Kullanımı şöyledir (Kodda sol tarafın List değil LinkedList olduğuna dikkat ediniz):

    LinkedList linkedList = new LinkedList<>(); System.out.println(linkedList.descendingIterator());

ArrayList içerisinde ise listeyi tersten okuma işlemi için bizim ListIterator sınıfından bir nesne elde edip onunla tersten dolanan döngüyü yazmamız gerekir. Şöyle ki:

List<String> liste = new ArrayList<>();
ListIterator<String> listIterator = liste.listIterator(liste.size());
while (listIterator.hasPrevious())
{
   System.out.println(listIterator.previous());
}

Bu kısımda şunu da söyliyeyim. Collection Interface içerisindeki Iterator’ın geri gitme özelliği yoktur. List Interface için yazılmış olan listIterator metodu ve ListIterator sınıfından yararlanarak ileri gitme özelliği olan iterator’ı kullanırız.

  1. ArrayList oluşturma işlemi sırasında eğer parametre alamayan yapılandırıcı (constructor) kullanılırsa başlangıç kapasitesi olarak 10 kullanılır (önceki yazıda değinmiştim). Fakat LinkedList oluşturma sırasında herhangi bir başlangıç kapasitesi belirlenmez. Boş bir liste oluşturulur o kadar.

  2. Bellek Kullanımı açısından bakıldığında ise ArrayList’in LinkedList’e bir üstünlüğü olduğu söylenebilir. Çünkü tıpatıp aynı verileri tutsalar bile LinkedList bir gözde veriyi, o veriden önceki ve sonraki veriyi işaret eden alanları tutarken ArrayList sadece veriyi tutar. ArrayList ile LinkedList ortak özellikler de muhteva etmektedir. Şimdi bunlara da bakalım.

  3. İkisi de senkronize değildir. LinkedList ve ArrayList snıflarından oluşturulmuş objeler üzerinde aynı anda birden fazla Thread işlem yapabilir.

  4. clone() metodu ile ArrayList ve LinkedList sınıfları klonlama işlemi sunar. Klonlama işlemi sırasında listenin içindeki veriler klonlanmaz. Bunun yerine liste objesinin kendisi klonlanır. Kullanımı hakkında örnek bir kod şöyledir:

    ArrayList liste = new ArrayList<>(); ArrayList list = (ArrayList)liste.clone();

  5. İkisi de iterator ve listIterator metodları sayesinde iterasyon işlemine tabi tutulabilir. Buradaki listIterator metodu fail-fast metot olarak geçer. Yani tam bu metot çalışırken bir Thread işin içine girmeye kalkarsa ConcurrentModificationException fırlatılır.
  6. İki tüdeki objemiz de değerlerin eklenme sırasını muhafaza eder. Burada List arabirimi olmaları temel özellik teşkil eder.

Peki, ikisini karşılaştırdık. Benzer ve farklı yönlerini gördük. Ne zaman ArrayList, ne zaman LinkedList kullnmalıyız? Şon olarak bu sorunun cevabını irdeleyelim:

Eğer yapmış olduğunuz projede çok miktarda arama veya get(int index); metodundan faydalanacaksanız ArrayList sizin tercihiniz olmalı. Çünkü yukarıda da değindiğimiz üzere ArrayList bu işi O(1) zamanda yaparken LinkedList O(n) zamanda yapmaktadır. Eğer kodunuzda liste üzerinde ekleme ve silme işlemeleri arama-getirme işlemelerinden daha çok yer alıyorsa o zaman da LinkedList tercihiniz olabilir.

Önceki yazımızdaki örnek kodumuzdaki tüm işlemleri ikisi List Implementation olduğu için LinkedList ile de yapabiliriz. Sadece sağ tarafı LinkedList yapmak ya da sağ ve solun ikisini de LinkedList yapmak yeterli. O nedenle bu yazıda bir örnek kod yapmıyorum arkadaşlar. Gelecek yazıda Queue Interface konusuna giriş yapmış olacağız.

Görüşene kadar sağlıcakla kalın.

Bu yazıyı hazırlarken şu makale kaynak alınmıştır:http://javahungry.blogspot.com/2015/04/difference-between-arraylist-and-linkedlist-in-java-example.html