Diziler ve Bağlı Listeler: Doğru Yapıyı Seçmek

Bir müzik çalma listesinde parçaları sırayla gezmek, belirli sıradaki parçaya ulaşmak ve araya yeni parça eklemek isteriz. Bu işlemlerin maliyeti, verinin nasıl düzenlendiğine bağlıdır.

Dizi nasıl çalışır?

Array, elemanları mantıksal olarak sıralı tutar ve çoğu düşük seviyeli uygulamada bellekte ardışık yerleşimden yararlanır. İndeks biliniyorsa adres hesaplanabildiği için values[i] erişimi O(1) olur.

Ortaya eleman eklemek için sonraki elemanların kaydırılması gerekebilir: O(n). Dinamik diziler kapasite dolduğunda daha büyük alan ayırıp elemanları kopyalar. Tek bir büyütme pahalı olsa da bu maliyet birçok ucuz eklemeye yayıldığında işlem başına ortalama sabit kalır. Buna amortized O(1), yani “bir işlem bazen pahalı olsa da uzun işlem dizisinin ortalama maliyeti sabit” denir.

Bağlı liste nasıl çalışır?

Her node (düğüm) bir değer ve sonraki node’a referans taşır. Doubly linked list (çift yönlü bağlı liste) ayrıca önceki node’u da tutar; böylece iki yönde gezilebilir. Bir node biliniyorsa yanına ekleme O(1) olabilir; fakat i numaralı elemana ulaşmak baştan yürümeyi gerektirir ve O(n) sürer.

type Node<T> = {
  value: T;
  next: Node<T> | null;
};

value saklanan veridir. next, sıradaki node’un referansıdır; listenin sonunda null olur. Bu öz-referanslı tip zincirin yapısını tanımlar.

Hangisini seçmeliyiz?

Diziler indeks erişimi, iterasyon hızı ve cache locality açısından genellikle üstündür. Bağlı listeler, mevcut node üzerinden sık ekleme/silme yapılan özel durumlarda yararlıdır. Ancak node başına referans maliyeti ve cache miss üretme ihtimali vardır.

Gerçek uygulamalarda kuyruk için ring buffer veya deque, arama için hash table, sıralı veri için ağaç daha uygun olabilir. “Ekleme O(1)” bilgisini bağlamdan koparmayın: eklenecek konumu bulmak O(n) ise toplam işlem yine lineerdir.

Yaygın hatalar

• Listenin son node’unda next = null durumunu unutmamak
• Silinen node’a referansları temizlememek
• Dinamik dizinin yeniden boyutlanmasını her eklemede gerçekleşiyor sanmak
• Veri yapısını yalnızca teorik Big-O ile seçip gerçek erişim düzenini ölçmemek

Alıştırma

Tek yönlü bağlı listeyi tersine çeviren bir fonksiyon yazın. previous, current ve next referanslarının her döngü adımında neyi gösterdiğini kâğıt üzerinde çizin.