Veri Yapıları İçin Ön Bilgiler

Gerçek bir veri yapısını kodlamadan önce temel programlamada rahat olmak gerekir.

Bir veri yapısını yalnız sakladığı değerler tanımlamaz; kodun koruduğu işlemler ve değişmezler (invariant) de tanımlar.

• Atama, koşul, döngü ve metot çağrılarını adım adım izleyebilmek.
• Parametre alan ve değer döndüren metotlar yazabilmek.
• Yerel değişkenleri ve kapsamı (scope) anlamak.
• İç içe döngüleri okuyup kaç kez çalışacaklarını kestirebilmek.

Veri yapılarıyla bağlantısı: Gezinme, ekleme, silme, arama ve güncelleme işlemleri.

Derste gerçeklemeler Java ile yazılır. Bu yüzden sınıf, nesne, alan, yapıcı (constructor) ve metot kavramları önceden tanıdık olmalıdır.

Veri yapılarının çoğu sınıf olarak gerçeklenir; iç gösterim, işlemlerin arkasında gizli kalır.

• Sınıf ile nesneyi ayırt edebilmek.
• new ile nesne oluşturmak ve yapıcıları kullanmak.
• Örnek alanlarını, yerel değişkenleri ve this anahtar sözcüğünü anlamak.
• Kapsüllemeyi, erişim belirleyicilerini ve static üyelerle örnek üyeleri arasındaki farkı tanımak.
• İstisna (exception) fırlatıp yakalayabilmek; örneğin boş bir yapıdan öğe çıkarılmak istendiğinde.
• Arayüzleri ve List<Integer> gibi jenerik tipleri okuyabilmek; Bölüm 1 ikisini de yeniden ele alır.

Veri yapılarıyla bağlantısı: Düğüm sınıfları, kap sınıfları, ADT'ler ve kapsüllenmiş değişmezler.

Bağlı yapılar, nesneleri çalışma anında birbirine bağlayan referanslara dayanır.

Bağlı listeler, ağaçlar, çizgeler ve nesne tabanlı yapılar için referansları anlamak şarttır.

• Nesne değişkeninin nesnenin kopyasını değil, nesneye giden referansı tuttuğunu bilmek.
• İki değişkenin aynı nesneyi gösterebileceğini fark etmek (takma ad, aliasing).
• null değerini güvenle kullanmak ve neyi temsil ettiğini bilmek.
• Nesneyi değiştirmek ile referansa yeni değer atamak arasındaki farkı görmek.

Veri yapılarıyla bağlantısı: Sonraki düğüm bağlantıları, çocuk referansları, çizge düğümleri ve yapısal güncellemeler.

Diziler; dinamik dizilerin, heap'lerin, hash tablolarının, komşuluk matrislerinin ve birçok iç gösterimin temelidir. Temel dizi kullanımının bilindiği varsayılır. Bölüm 3 dizileri ve dizi algoritmalarını ayrıntılı işler; ArrayList'in dinamik dizi olarak büyümesi Bölüm 6'dadır.

İndisle sabit sürede erişim, diziyi veri yapısı tasarımının en önemli yapı taşlarından biri yapar.

• Sıfırdan başlayan indislemeyi doğru kullanmak.
• Dizi üzerinde gezinmek ve indisi saklanan değerden ayırt etmek.
• Tek ve iki boyutlu dizileri tanımlamak, doldurmak ve yazdırmak.
• Sınır dışı indislerden kaçınmak; ArrayIndexOutOfBoundsException hatasının ne zaman oluştuğunu bilmek.

Veri yapılarıyla bağlantısı: ArrayList, ikili heap'ler, hash tablosu kovaları ve komşuluk matrisleri.

Ağaç ve çizge algoritmaları çoğunlukla özyinelemeli (recursive) yazılır. Özyineleme, ağaçlarda ve çizgelerde kullanılmadan önce Bölüm 4'te yeniden ele alınır.

Özyineleme, aynı problemi alt yapılar üzerinde çözerek hiyerarşik yapıları işlemenin doğal yoludur.

• Özyinelemeyi sonlandıran taban durumu belirlemek.
• Özyinelemeli çağrıları ve dönüşleri izlemek.
• Yığın derinliğini ve sonsuz özyinelemeyi anlamak.
• Ağaç gezinmesinde ve derinlik öncelikli aramada özyinelemeli kalıpları tanımak.

Veri yapılarıyla bağlantısı: Ağaç gezinmeleri, DFS, özyinelemeli ekleme ve silme, böl ve fethet yaklaşımı.

Veri yapıları, girdi büyüdükçe işlemlerinin ne kadar maliyetli olduğuna göre karşılaştırılır. Gösterimi Bölüm 2 biçimsel olarak tanıtır; yaygın büyüme hızlarını önceden tanımak bu bölümü kolaylaştırır.

Büyük O, bir gösterimin neden ötekinden daha iyi ölçeklendiğini açıklamanın dilidir.

• O(1), O(log n), O(n), O(n log n) ve O(n²) sınıflarını tanımak.
• İç içe döngülerin maliyetini kestirmek.
• Art arda ikiye bölmenin neden logaritmik davranış verdiğini anlamak.
• Tek bir ölçüte bağlı kalmadan zaman ve alan ödünleşimlerini karşılaştırmak.

Veri yapılarıyla bağlantısı: Diziler, listeler, ağaçlar, heap'ler, hash tabloları ve çizgeler için işlem maliyeti tabloları.

Bir algoritmayı elle izleyebilmek, bir veri yapısını anlamanın en yararlı becerilerinden biridir.

İzleme; işaretçilerin, indislerin, yığınların, kuyrukların ve ağaç bağlantılarının bir adımdan ötekine nasıl değiştiğini gösterir.

• Her işlemden sonra değişkenlerin ve yapının durumunu takip etmek.
• Döngüleri ve özyinelemeli çağrıları çalışma sırasıyla izlemek.
• Güncellemelerden sonra yapısal değişmezlerin hâlâ geçerli olup olmadığını denetlemek.
• Uç durumları küçük örnekler üzerinde düşünmek.

Veri yapılarıyla bağlantısı: Simülatör kullanımı, hata ayıklama, doğruluk denetimi ve sınav sorularındaki akıl yürütme.

Biraz ayrık matematik bilgisi; kümeler, ağaçlar, çizgeler ve karmaşıklık üzerine akıl yürütmeyi kolaylaştırır.

Matematiksel gösterim; ilişkileri, sınırları, bağlantılılığı ve yapısal özellikleri kesin biçimde ifade etmeye yarar.

• Küme, üyelik, birleşim, kesişim ve fark kavramlarında rahat olmak.
• Basit bağıntıları ve çizgedeki gibi bağlantıları anlamak.
• Dengeli ağaçlar ve art arda ikiye bölme üzerine düşünürken üsleri ve logaritmaları kullanmak.
• Algoritma maliyetlerini karşılaştırırken basit toplamları ve eşitsizlikleri okuyabilmek.

Veri yapılarıyla bağlantısı: Kümeler, çizgede bağlantılılık, ağaç yüksekliği ve asimptotik analiz.

Ağaç yüksekliği sınırları, özyinelemeli algoritmaların doğruluğu ve hash tablolarındaki yoklama dizileri gibi birçok sonuç derste kısa kanıtlarla gösterilir. Bu kanıtlar çoğunlukla tümevarıma ya da çelişkiye dayanır.

Kanıt, bir yapının her girdide beklenen sınırı koruduğunu gösterir; birkaç örnek üzerinde denemek bu güvenceyi vermez.

• Tümevarımda taban adımını ve tümevarım adımını kurabilmek; tümevarım varsayımının nerede kullanıldığını görmek.
• Düğüm sayısı, yükseklik ya da rütbe gibi bir büyüklük üzerinden yapılan tümevarımı izleyebilmek.
• Tersini varsayıp bir çelişkiye ulaşarak kanıtlama yöntemini tanımak.
• Bölünebilme, asal sayı ve ortak bölen kavramlarını bilmek.

Veri yapılarıyla bağlantısı: Özyinelemenin doğruluğu, ikili ağaçta düğüm sayısı ile yükseklik arasındaki bağıntılar, kırmızı-siyah ağaç ve ayrık küme ağaçlarının yükseklik sınırları, karesel yoklamada ve çift hash'lemede denenen yuvaların farklı olması.

Veri yapısı hataları çoğu zaman yanlış bağlantılardan, yanlış indislerden, sınır koşullarından ya da bozulan değişmezlerden kaynaklanır.

Sistemli hata ayıklama, çıktı doğru görünene kadar kodu deneme yanılmayla değiştirmekten daha güvenilirdir.

• Boş, tek öğeli ve sınırdaki durumları test etmek.
• Yalnız son çıktıya değil, ara durumlara da bakmak.
• Değişmezler için assert ifadeleri ya da açık denetimler kullanmak.
• Girdi hatalarını yapının mantık hatalarından ayırmak.

Veri yapılarıyla bağlantısı: Bağlı liste güncellemeleri, döndürmeler, heap düzeni, hash tablosunu yeniden boyutlandırma ve çizgede gezinme.