Uygulamayı yazarken sürekli ArrayList kullanıyorum. Ama veri yapıları konularında linked list diye bir kavram daha var. ArrayList’e göre avantajı nedir? Hangi durumda ve neden kullanmalıyım?
comments
1 references
// Comments are closed.
Çok klasik soru.
Kod yazılırken birden fazla aynı türden verileri tutmak için normal değişken yerine dizi (array) kullandığımızı biliyoruz. Bu diziler üzerindeki işlemleri daha rahat yaptırabilmek için programlama dilleri bize biraz daha gelişmiş seçenekler sunuyor. Bunların başında arraylist geliyor. Temel olarak dizi ile aynı işlevde olup içine birşeyler eklene eklene gidiyor. Bunun da bir başlangıç sınırı var. Örneğin 10 tane ekleyebiliyorsunuz. 11. elemanı eklediğinizde programlama dilinin gerçekleştirimine göre hafızada daha büyük bir alan ayırıp bütün elemanlarınızı buraya taşıyıp 11. elemanı ekleyip devam ediyor. Tabi bu işlemin bir maliyeti var. Yeni yer açılması, olan bilgilerin taşınması gibi işlemler yapıldığı için bunları maliyet olarak alıyoruz. Bir başka konu diziler hafızada art arda tutulduğu için, örneğin 4. ile 5. elemanlar arasına yeni bir eleman koymak istediğiniz zaman 5+ olan elemanların hepsini bir ileri alana kaydırmanız gerekir.
Bunun yanında programlama dilleri bize dizi yerine linked-list seçeneği de verir. Bu yapı node altyapısı ile çalışır. Yani her bir eklenen eleman hafıza art arda değil de birbirini referans gösterecek şekilde tutulur. Bu bize özellikle ekleme işlerinde büyük esneklik verir. Dizinin tersine iki elemanın arasına birşey ekleyeceğiniz zaman kaydırma işlemleri yapmanıza gerek kalmaz. Ya da başlangıçtaki sınırı geçtikçe hepsi için yer ayır bunları taşı gibi sorunlarınız olmaz. Yani sürekli büyüyen ve aralara da ekleme yapabileceğiniz yapılar için linked-list (bağlı liste) daha mantıklı çözüm olacaktır.
Bu ikisinin arasındaki en büyük fark elinizdeki elemanlar içinden birisini seçmek/almak istediğinizde çıkacaktır. ArrayList için herhangi bir elemana ulaşmak O(1) karmaşıklığında çalışır. Yani 1500. elemana ulaşmak için arraylist.get(1500) dediğiniz zaman bir hamlede o elemanı getirir. Bu durum linked list için pek geçerli değildir. Keza art arda gelmedi için 1500. elemanı getir demek; birinci elemandan başla 1500 tane say, bulunca getir demek olur. Yani karmaşıklık O(n) çıkar. n elemanlık bir listede en kötü ihtimalle n. sırada aradığınıza ulaşırsınız.