Algoritmalar ve Veri Yapıları: Teoriden Pratiğe

Algoritma, bir problemi çözmek için adım adım izlenen talimattır; veri yapısı ise bu bilgilerin bilgisayar belleğinde nasıl organize edildiğidir. Doğru "algoritma + veri yapısı" ikilisinin seçimi, programın çalışma hızını ve kaynak tüketimini belirler. Örneğin, anahtar bazlı hızlı arama için karma tablolar (O(1)), hiyerarşik verileri depolamak için ise ağaçlar kullanılır.

Bu içerikte temel veri yapılarını inceleyecek, Big O notasyonu ile etkinliklerini değerlendirecek ve pratikte nerelerde uygulandıklarını ele alacağız.

Algoritma Karmaşıklığı (Big O) Nedir?

Bir araç seçmeden önce, etkinliğinin nasıl ölçüleceğini anlamak gerekir. Bunun için asimptotik karmaşıklık (Big O notasyonu) kullanılır. Bu notasyon, girdi verisi miktarı ($n$) arttığında yürütme süresinin veya bellek tüketiminin nasıl büyüdüğünü gösterir.

Doğrusal Yapılar: Diziler ve Listeler

Bunlar programlamanın temel taşlarıdır. Aralarındaki seçim, veriyi daha çok okumaya mı yoksa değiştirmeye mi ihtiyaç duyduğunuza bağlıdır.

Diziler (Arrays)

Bellekte sürekli bir blok halindedir.

• Avantajları: İndeksle anında erişim $O(1)$, önbellek yerelliği sayesinde yüksek tarama hızı.
• Dezavantajları: Sabit boyut (statik dizilerde), ortasına ekleme/silme işlemlerinin maliyetli olması $O(n)$, çünkü elemanların kaydırılması gerekir.

Bağlı Listeler (Linked Lists)

Elemanlar belleğin farklı bölgelerinde tutulur ve işaretçilerle birbirine bağlanır.

• Avantajları: Herhangi bir yere hızlı ekleme ve silme $O(1)$ (düğüm biliniyorsa), dinamik boyut.
• Dezavantajları: İndeksle erişimin yavaş olması $O(n)$ (tüm zinciri gezmek gerekir), işaretçileri saklamak için ek bellek maliyeti.

Yığın ve Kuyruk: Sıranın Yönetimi

Bu yapılar, veri ekleme ve çıkarma yöntemlerini kısıtlayarak yürütme akışının kontrol edilmesine olanak tanır.

Yığın (Stack)

LIFO (Last In, First Out — Son Giren, İlk Çıkar) prensibi.

• Analoji: Üst üste dizilmiş tabaklar. En üsttekini alırsınız, o da en son konulan tabaktır.
• Uygulama Alanları: Editörlerde geri alma (Undo) işlemleri, fonksiyon çağrı bağlamının saklanması (Call Stack), parantez dizilerinin kontrolü.

Kuyruk (Queue)

FIFO (First In, First Out — İlk Giren, İlk Çıkar) prensibi.

• Analoji: Mağazadaki sıra.
• Uygulama Alanları: Arka planda görev işleme (yazdırma kuyruğu), veri akışlarının tamponlanması, grafılarda genişlik öncelikli arama (BFS) algoritmaları.

Karma Tablolar: Anında Erişim

Karma tablo (HashMap, Dictionary, Map), "anahtar-değer" çiftlerini saklamaya olanak tanır.

• Çalışma Prensibi: Anahtar, bellek hücresinin indeksini hesaplayan bir karma fonksiyonundan geçirilir.
• Karmaşıklık: Arama, ekleme ve silme işlemleri için ortalama $O(1)$.
• Detaylar: Çarpışmalar mümkündür (iki farklı anahtarın aynı hücreye karşılık gelmesi durumu). Zincirleme veya açık adresleme yöntemleriyle çözülür.
• Uygulama Alanları: Önbellekleme, kelime sıklığı sayımı, küme (Set) implementasyonu, veritabanları (indeksler).

Ağaçlar ve Grafılar: Karmaşık Bağlantılar

Veriler hiyerarşik veya ağ benzeri bir yapıya sahip olduğunda, doğrusal listeler kullanışsız hale gelir.

Ağaçlar (Trees)

Kök düğüme sahip hiyerarşik yapı.

• İkili Arama Ağacı (BST): Sol çocuk ebeveynden küçük, sağ çocuk büyüktür. Dengeli halde arama $O(\log n)$ sürer.
• Dengeli Ağaçlar (AVL, Kırmızı-Siyah): Yükseklik dengesini otomatik olarak korur, en kötü durumda bile $O(\log n)$ garantisi verir. Veritabanlarında ve dosya sistemlerinde dahili olarak kullanılır.
• Yığın (Heap): Öncelikli kuyrukların implementasyonu için özel bir ağaçtır. Minimum veya maksimum değere hızlı erişim sağlar ($O(1)$).

Grafılar (Graphs)

Düğümler (noktalar) ve kenarlardan (bağlantılar) oluşan küme.

• Türleri: Yönlü/yönsüz, ağırlıklı/ağırlıksız.
• Gezinme:
  • DFS (Derinlik Öncelikli Arama): Özyineleme veya yığın kullanır. Yol bulma, bağlantısallık kontrolü, topolojik sıralama için iyidir.
  • BFS (Genişlik Öncelikli Arama): Kuyruk kullanır. Ağırlıksız graflarda en kısa yolu bulmak için idealdir.
• Uygulama Alanları: Sosyal ağlar (arkadaşların arkadaşları), haritalar ve navigasyon (en kısa yol), bağımlılık ağları (Linux/npm paketleri).

Temel Algoritmalar: Arama ve Sıralama

Arama

1. Doğrusal Arama: Tüm elemanları tarar. $O(n)$. Evrenseldir ancak yavaştır.
2. İkili Arama: Sıralı diziyi ikiye böler. $O(\log n)$. Ön sıralama gerektirir.

Sıralama

Algoritma seçimi verilere bağlıdır:

• QuickSort (Hızlı Sıralama): Ortalama $O(n \log n)$. Yerinde çalışır, pratikte çok hızlıdır ancak kararsızdır.
• MergeSort (Birleştirmeli Sıralama): Kararlı $O(n \log n)$. Ek bellek gerektirir. Bağlı listeler için iyidir.
• TimSort: MergeSort ve InsertionSort hibrididir. Python (sorted) ve Java (Arrays.sort) dillerinde varsayılan olarak kullanılır.

Doğru Veri Yapısını Nasıl Seçersiniz?

Geliştirmeye başlamadan önce şu üç soruyu cevaplayın:

1. Veriler ne sıklıkla değişiyor?
   • Nadiren: Dizi.
   • Sık sık (ekleme/silme): Bağlı liste veya Ağaç.
2. Erişim nasıl gerekiyor?
   • İndeksle: Dizi.
   • Anahtarla: Karma tablo.
   • Aralık/sıra ile: Arama ağacı (BST).
3. Veriler arasındaki ilişki nedir?
   • Hiyerarşi: Ağaç.
   • Bağlantı ağı: Graf.

Yeni Başlayanların Sık Yaptığı Hatalar

• Karma tablo varken iç içe döngüler kullanmak.
  • Hata: Toplamı $K$ olan sayı çiftini tüm çiftleri tarayarak bulmak $O(n^2)$.
  • Çözüm: Daha önce karşılaşılan sayıları saklamak için HashSet kullanmak $O(n)$.
• En kötü durumu göz ardı etmek.
  • QuickSort, pivot eleman kötü seçilirse zaten sıralı verilerde $O(n^2)$ seviyesine düşebilir.
• Yineleme sırasında koleksiyonu değiştirmek.
  • Birçok dilde bu, çalışma zamanı hatasına neden olur. Yineleyicileri (iterators) kullanın veya listenin bir kopyasını oluşturun.

SSS: Sorulara Cevaplar

Yığın ile kuyruk arasındaki fark nedir? Yığın "son giren ilk çıkar" (kitap yığını gibi) prensibiyle çalışırken, kuyruk "ilk giren ilk çıkar" (kasadaki sıra gibi) prensibiyle çalışır.

Karma tablolar bu kadar hızlıysa neden her zaman onları kullanmıyoruz? Daha fazla bellek tüketirler ve karşılaştırma işlemlerini ("küçük/büyük") veya sıralı sırada gezinmeyi desteklemezler.

Özyineleme mi yoksa yineleme mi daha iyi? Yineleme genellikle bellek açısından daha verimlidir (çağrı yığını ek yükü yoktur). Özyineleme, ağaç yapılı görevler (ağaç gezinme, DFS) için kodu daha temiz hale getirir ancak yığın taşmasını önlemek için derinlik kontrolü gerektirir.