LinkedList neden ortadan ekleme için ArrayList'ten daha yavaş?

Çünkü ortadan ekleme yapmak için önce o pozisyona kadar düğümleri tek tek dolaşmanız gerekir ve her düğüm bellekte rastgele bir yerdedir. Bu da her adımda cache miss üretir. ArrayList ise ardışık bellekte System.arraycopy ile blok kopyalama yapar, CPU bunu çok daha verimli işler.

Cache locality tam olarak nedir ve neden bu kadar önemli?

CPU veriyi RAM'den 64 byte'lık cache line'lar halinde okur. Ardışık bellekte tutulan veri yapıları (ArrayList gibi) tek erişimde birden fazla elemanı cache'e getirir. L1 cache erişimi 4 cycle, RAM erişimi 100-300 cycle alır. Yani teorik karmaşıklık aynı olsa bile pratik performans 25-75 kat farklı olabilir.

ArrayList yerine LinkedList kullanmalı mıyım hiç?

Çok nadiren. LinkedList'in tek meşru senaryosu Queue veya Deque arayüzü gerektiren FIFO/LIFO işlemlerdir. Ama bu durumda bile ArrayDeque hem daha hızlı hem de daha az bellek tüketir. Modern Java kodunda LinkedList tercih etmek için somut bir benchmark sonucunuz olmalı.

HashMap her zaman O(1) midir?

Hayır, sadece ortalama durumda. Kötü bir hashCode() implementasyonu tüm anahtarların aynı bucket'a düşmesine yol açabilir. Java 8'den itibaren çakışan bucket'lar belirli bir eşikten sonra dengeli ağaca dönüşür, böylece worst case O(n) yerine O(log n) olur. Yine de iyi hash dağılımı kritiktir.

HashMap'i başlatırken kapasiteyi neden manuel belirlemeliyim?

Default kapasite 16'dır ve load factor 0.75 aşıldığında 2x rehash olur. 10.000 eleman ekleyecekseniz birden fazla rehash tetiklersiniz, her biri O(n) maliyetlidir. new HashMap(expectedSize / 0.75 + 1) ile başlatmak bu rehash zincirinden kurtarır ve performansı belirgin biçimde artırır.

Thread-safe bir Map için ne kullanmalıyım?

ConcurrentHashMap kullanın. Hashtable ve Collections.synchronizedMap tüm map'i tek bir kilitle korur, yüksek concurrency altında darboğaz olur. ConcurrentHashMap ise lock striping veya CAS işlemleri kullanarak okuma işlemlerini neredeyse kilitsiz gerçekleştirir ve çok daha yüksek throughput sağlar.

Sıralı iterasyon gereken bir Map için ne tercih etmeli?

Eğer ekleme sırası korunmalıysa LinkedHashMap, key'lere göre sıralı iterasyon gerekiyorsa TreeMap kullanın. TreeMap kırmızı-siyah ağaç kullandığı için get/put işlemleri O(log n)'dir, HashMap'ten yavaştır. Sıra önemli değilse her zaman HashMap tercih edin.

ArrayList kapasitesini önceden bilmiyorsam ne yapmalıyım?

Default kapasite 10 ile başlayıp 1.5x büyüme stratejisini bırakın. Bu strateji amortized O(1) ekleme garantisi verir. Ancak son boyut beklenenden çok küçük çıkarsa trimToSize() ile fazla kapasiteyi geri verebilirsiniz. Uzun ömürlü ve büyük listelerde bu, bellek tasarrufu açısından faydalıdır.

JAVA COLLECTIONS PERFORMANSI

Java Collections performans karşılaştırma bar grafiği ArrayList LinkedList HashMap hız farkları

"LinkedList ortadan ekleme için hızlıdır, ArrayList ise random access için." — Java dünyasında neredeyse herkesin ezberlediği bu cümle, modern CPU mimarilerinde büyük ölçüde yanlıştır. Big-O notasyonu size O(1) ile O(n) farkını söyler ama RAM'den L1 cache'e veri çekmenin maliyetini söylemez. Gerçekte ArrayList, çoğu pratik senaryoda LinkedList'i hem random access hem de ortadan ekleme/silme işlemlerinde geride bırakır. Bunun nedeni teorik karmaşıklık değil, cache locality denilen donanımsal gerçekliktir.

LinkedList Hakkındaki En Büyük Yanılgı

Java derslerinde standart anlatım şudur: "LinkedList düğümleri pointer ile bağlıdır, dolayısıyla ortadan ekleme O(1)'dir." Bu cümlenin gizlediği şey, "ortayı bulmak" için O(n) traversal gerektiğidir. Yani list.add(5000, x) çağrısı, 5000 düğümü tek tek dolaşıp pointer'ları takip etmek anlamına gelir. ArrayList'te ise bu işlem, ardışık bellek bloğunda System.arraycopy ile yapılır ve CPU bunu blok bazlı SIMD instruction'larla işler.

Sonuç: 10.000 elemanlı bir listede ortadan ekleme yapacaksanız, ArrayList LinkedList'ten 5-10 kat daha hızlıdır. Bu, JMH benchmark'larıyla defalarca doğrulanmış bir gerçektir.

Cache Locality: Asıl Belirleyici Faktör

Modern CPU'lar RAM'den veri çekerken tek byte değil, 64 byte'lık cache line halinde çeker. ArrayList elemanları ardışık bellekte tutulduğundan, bir elemanı okurken yanındaki 7-15 eleman da L1 cache'e gelir. LinkedList'te ise her düğüm heap'in rastgele bir yerinde durur — her erişim potansiyel bir cache miss'tir.

ArrayList ardışık bellek hücreleri ile LinkedList dağınık düğüm yerleşimi cache locality şeması

Bir cache miss yaklaşık 100-300 CPU cycle'a mal olur. L1 hit ise 4 cycle. Yani LinkedList traversal'ı, ArrayList traversal'ına göre teorik olarak aynı O(n) olsa da pratikte 25-75 kat daha yavaş çalışabilir. Bu fark, ölçek büyüdükçe sertleşir.

ArrayList'i Gerçekten Yavaşlatan Şey

ArrayList'in gerçek zayıf noktası ortadan ekleme değildir — başa eklemedir. add(0, element) her seferinde tüm diziyi bir slot kaydırır. Eğer iş yükünüz sürekli başa eklemeyse:

ArrayDeque: Çift uçlu kuyruk, başa/sona O(1) ekleme, ardışık bellek avantajı korunur
LinkedList: Sadece başa/sona iterator ile ekleme + sıralı traversal yapacaksanız mantıklı
ArrayList + ters çevirme: Sona ekleyip sonda iterate etmek çoğu zaman en hızlısıdır

Pratikte LinkedList'in tek meşru kullanım alanı kalmıştır: Queue veya Deque arayüzü ile FIFO/LIFO işlemleri. Ama burada bile ArrayDeque neredeyse her zaman daha iyi seçimdir.

HashMap: O(1) Sözünün Küçük Yazısı

HashMap'in get ve put işlemleri ortalamada O(1)'dir — ama bu söz iki koşula bağlıdır: iyi bir hash fonksiyonu ve uygun bir load factor. Kötü hash dağılımı, bucket'ların lineer listeye (Java 8+ ile belirli eşikten sonra dengeli ağaca) dönüşmesine yol açar ve performans O(n) ya da O(log n)'e iner; bu iç yapının davranışı ve eşik değerleri resmi API dokümantasyonunda ayrıntılandırılmıştır.

HashMap'in iç yapısını ve diğer JVM seviyesi performans konularını daha derinlemesine öğrenmek için Java performans ve JVM eğitimi içeriğinden yararlanabilirsiniz.

Boyutlandırma ve Resize Maliyeti

ArrayList default kapasitesi 10'dur ve dolduğunda 1.5x büyür. HashMap default 16 bucket ile başlar ve load factor 0.75'i aştığında 2x rehash olur. Eğer veri boyutunuzu önceden biliyorsanız:

ArrayList için new ArrayList<>(expectedSize) kullanın — gereksiz resize'ı önler
HashMap için new HashMap<>(expectedSize / 0.75 + 1) ile başlatın — rehash maliyetinden kurtulursunuz
Çok büyük koleksiyonlarda trimToSize() ile fazlalık belleği geri verin

Resize işlemi ArrayList için O(n), HashMap için O(n) (tüm bucket'ların yeniden hash'lenmesi) maliyetindedir. Sık tetiklendiğinde toplam karmaşıklık amortized analizden sapar.

Karar Matrisi: Hangi Senaryoda Hangisi?

Pratik bir rehber:

Sıralı erişim + index ile arama: ArrayList — neredeyse her zaman
Sık başa/sona ekleme (queue/stack): ArrayDeque
Key-value lookup: HashMap (sıra önemsizse), LinkedHashMap (insertion order korunmalıysa), TreeMap (sıralı iterasyon gerekiyorsa)
Thread-safe lookup: ConcurrentHashMap — Hashtable veya synchronizedMap değil
Unique elemanlar: HashSet (sırasız), LinkedHashSet (insertion order), TreeSet (sıralı)

Java Collection Framework hiyerarşisi List Set Map ve Queue arayüzlerinin ilişki şeması

Benchmark'a Güvenin, Sezgiye Değil

Java koleksiyon performansında "şu hep daha hızlıdır" diyebileceğiniz bir kural yoktur. JIT compiler, escape analysis, branch prediction ve cache davranışı; aynı kodun farklı veri boyutlarında farklı sıralamalar üretmesine neden olur. Bir kararı performansa dayandırıyorsanız, JMH ile ölçün — özellikle koleksiyon seçiminizi etkileyecek kadar kritik bir sıcak yolda (hot path) çalışıyorsa.

İleri seviye JVM tuning, garbage collector seçimi ve benchmark metodolojisi gibi konularda derinleşmek isteyenler Java performans eğitim içeriğini inceleyebilirsiniz.

Sonuç olarak, "LinkedList ortadan ekleme için iyidir" cümlesini unutun. Çoğu modern Java kodunda ArrayList ve HashMap, hayal ettiğinizden çok daha geniş bir senaryo yelpazesinde optimal seçimdir. Donanımı anlamadan algoritma karmaşıklığını anlamak, eksik kalan bir bilgidir.