BİL207U-VERİ YAPILARI
Ünite 2: Dizi, Sözlük ve Kümler, Listeler
Giriş
Bu ünitede diziler, sözlük ve küme yapılarının yanında liste veri yapıları incelenecektir. Bahsedilen veri yapılarının tümü, çeşitli senaryolarda kullanılabilecek ilginç veri yapılarıdır. Bu tür koleksiyonları ayrıntılı açıklamalar ve örneklerle sunarak, uygun bir veri yapısı seçmenin kolay bir iş olmadığı ve performansla ilgili konuların detaylı analiz gerektirdiğini önceki bölümde incelenmişti çünkü bazı veri yapısı değerleri almada daha iyi çalışmakta bazısı da değerlerin eklenmesi ve kaldırılmasında gerekli performansı sunmaktadır.
Dizi, Sözlük, Küme ve Listeler (Dictionaries and Sets, Array, Lists)
Veri yapıları, bilgisayardaki verileri etkin bir şekilde kullanılabilecek şekilde düzenlemenin özel bir yoludur. Buradaki amaç, farklı görevlerin uzay ve zaman karmaşıklığını azaltmaktır.
Dizi (Array)
Dizi veri yapısını inceleyecek olursak int, string veya kullanıcı tanımlı bir sınıf gibi aynı türden birçok değişkeni saklamak için kullanılabilen bir veri yapısıdır. Bir dizi, bitişik bellek konumlarında depolanan ögeler topluluğudur. Buradaki amaç, aynı türden birden fazla ögeyi bir arada saklamaktır. Bu yapıda, bir temel değere yani dizinin ilk ögesinin bellek konumuna (genellikle dizinin adı ile gösterilir) bir ofset eklenerek her bir ögenin konumunun hesaplanması kolaylaştırılmaktadır.
Tek Boyutlu Diziler
Tek boyutlu bir dizi, bir dizin tarafından erişilebilen aynı türdeki ögelerin bir koleksiyonunu depolamaktadır. C#’daki dizi indekslerinin sıfır tabanlı olduğu unutulmamalıdır. Bu, ilk ögenin indeksinin 0 olduğu, sonuncusunun ise dizinin uzunluğundan bir eksik indekse sahip olduğu anlamına gelmektedir.
Çok Boyutlu Diziler
C# programlama dilinde dizilerin yalnızca bir boyutlu olması zorunluluğu yoktur. İki boyutlu ve hatta üç boyutlu diziler oluşturmak da mümkündür.
Dizi Dizileri (Jagged Arrays)
Son olarak bahsedilecek dizi türü, diziler dizisi olarak da adlandırılan pürüzlü dizidir. Kulağa karmaşık gelse de kullanımı oldukça basittir. Pürüzlü bir dizi, her bir elemanın başka bir dizi olduğu tek boyutlu bir dizi olarak da tanımlanabilir. Ayrıca, bu tür iç diziler farklı uzunluklara sahip olabilir veya boş da olabilir.
Sözlük ve Kümeler (Dictionaries and Sets)
Sözlükler ve kümelerle ilgili veri yapılarının uygun bir şekilde kullanılması, anahtarları değerlere eşlemeyi ve hızlı arama yapmanın yanında, kümeler üzerinde çeşitli işlemler yapmayı da mümkün kılmaktadır.
Hash Tabloları (Hash Tables)
Hash tabloları, hash map olarak da bilinmektedir. Hash tablosunun en önemli varsayımlarından biri; Anahtara dayalı bir Değer için çok hızlı arama yapabilen, O(1) işlem karmaşıklığında arama işlemi yapabilmesi gerekmektedir. Bu amaca ulaşmak için Hash Fonksiyonu kullanılmaktadır. Değerin bulunabileceği bir Kova dizini (bucket) oluşturmak için Anahtar (key) gerekmektedir. Böylece anahtarın bir değerini bulmanız gerekiyorsa koleksiyondaki tüm ögelerin üzerinden tek tek geçilmesi gerekmez çünkü anahtara karşılık gelen uygun bir kovayı kolayca bulmak ve değeri almak için hash fonksiyonunu kullanabilirsiniz. Hash tablosunun mükemmel performansı sebebiyle bu veri yapısı; ilişkisel diziler, veritabanı indeksleri veya önbellek sistemleri gibi birçok gerçek dünya uygulamasında sıklıkla kullanılmaktadır.
Sözlük (Dictionary)
Hashtable sınıfı, hash tablosuyla ilgili sınıfların jenerik olmayan bir varyantıdır ancak anahtar ve değer için bir değişken tipi belirlenmesine izin vermediği için önemli bir sınırlaması vardır. Sözlük veri yapısında bu sınırlama kaldırılmıştır. DictionaryEntry sınıfının Key ve Value özelliklerinin ikisi de nesne türündedir bu nedenle tüm anahtarlar ve değerler aynı tipte olsa bile kutulama (boxing) ve kutudan çıkarma (unboxing) işlemleri yapılması gerekmektedir. C# projelerinizde Sözlük için hazırlanan Dictionary jenerik sınıfını kullanabilirsiniz. Dictionary sınıfının bir örneğini oluştururken bir anahtar türü ve bir değer olmak üzere iki tür belirtilmelidir.
Sıralanmış Sözlükler (Sorted Dictionaries)
Hash tabloları ile ilgili sınıfların hem genel olmayan hem de genel türevleri, ögelerin sırasını tutmaz bu nedenle koleksiyondaki verilere anahtarlara göre sıralanmış şekilde erişmek gerekiyorsa bunların kullanımdan önce sıralanması gerekir ancak bu sorunu çözmek ve anahtarları her zaman sıralı tutmak için başka bir veri yapısı, sıralanmış sözlük kullanılabilir. Böylece gerektiğinde tasnif edilmiş koleksiyona kolayca ulaşılabilir. Sıralanmış sözlük, System.Collections.Generic ad alanında bulunan SortedDictionary genel sınıfı kullanılarak tanımlanmaktadır. SortedDictionary sınıfının yeni bir örneği oluşturulurken anahtar ve değerler için veri tipi belirtilebilir. Ayrıca bu sınıf, Sözlük’e (Dictionary) benzer özellikler ve yöntemler içermektedir. Sıralanmış sözlük sınıfı, içerdiği ögelerin sayısını (Count) almayı ve ayrıca anahtarlar ve değerler koleksiyonunu (sırasıyla Keys ve Values) döndürmeyi mümkün kılan birkaç özelliğe sahiptir. Ayrıca yeni bir öge eklemek (Add), bir ögeyi kaldırmak (Remove), tüm ögeleri kaldırmak (Clear), ayrıca koleksiyonun belirli bir anahtarı (ContainsKey) ve verilen değeri (ContainsValue) içerip içermediğini kontrol etmek gibi mevcut yöntemler kullanılabilir. Belirli bir anahtar için karşılık gelen bir değer varsa onu döndürmek veya bulunamadıysa null döndürmek için TryGetValue yöntemi kullanılabilir. Koleksiyonda depolanan tüm çiftleri yinelemek istendiğinde foreach döngüsünü kullanılabilir.
Döngüde kullanılan değişken, Anahtar (Key) ve Değer (Value) özelliklerine sahip KeyValuePair genel sınıfının bir örneğidir ve anahtara ve değere erişmenizi sağlar. Otomatik sıralama avantajlarına rağmen SortedDictionary sınıfının Dictionary ile karşılaştırıldığında bazı performans dezavantajları vardır çünkü alma, ekleme ve çıkarma O(log n) karmaşıklığına sahip işlemlerdir; burada n, koleksiyondaki öge sayısıdır. SortedDictionary, SortedList’e oldukça benzer ancak bellek ve performansla ilgili sonuçlarda farklılık gösterir. Bu sınıfların her ikisi için de alma, O(log n) işlemidir ancak sıralanmamış veriler için ekleme ve çıkarma, SortedDictionary için O(log n) ve SortedList için O(n)’dir. Elbette SortedDictionary için SortedList’ten daha fazla bellek gereklidir. Görüldüğü gibi uygun bir veri yapısı seçmek kolay bir iş değildir ve belirli veri yapılarının kullanılacağı senaryolar dikkatlice düşünülmeli ve hem artıları hem de eksileri hesaba katılmalıdır.
Karma Kümeler (Hash Sets)
Bazı algoritmalarda çeşitli veriler içeren kümeler üzerinde işlem yapmak gerekmektedir. Küme, yinelenen ögeleri ve belirli bir düzeni olmayan farklı nesnelerden oluşan bir koleksiyondur bu nedenle yalnızca belirli bir elemanın kümede olup olmadığını öğrenebilirsiniz. Kümeler; birleştirme, kesişme, çıkarma ve simetrik fark gibi matematiksel modeller ve işlemlerle sıkı bir şekilde ilişkilidir. C# dilinde uygulama geliştirirken System.Collections.Generic ad alanından HashSet sınıfının sağladığı yüksek performanslı işlemlerden yararlanılabilir. HashSet sınıfı, kümedeki ögelerin sayısını döndüren Count dahil olmak üzere birkaç özellik içermektedir. Ayrıca, aşağıdaki gibi küme işlemlerini gerçekleştirmek için birçok yöntem kullanılabilir. İlk yöntem grubu, parametre olarak gönderilen küme ile aşağıdakileri oluşturmak için yöntemin çağrıldığı geçerli kümeyi değiştirmeyi mümkün kılmaktadır:
• Birleşim (UnionWith) • Kesişme (IntersectWith) • Çıkarma (ExceptWith) • Simetrik fark (SmetricExceptWith)
İki küme arasındaki ilişkiler de kontrol edilebilir. Yöntemin çağrıldığı geçerli kümede aşağıdaki özellikler kontrol edilebilir:
• Parametre olarak iletilen kümenin bir alt kümesi (IsSubsetOf) • Parametre olarak iletilen kümenin bir üst kümesi (IsSupersetOf) • Parametre olarak geçirilen kümenin uygun bir alt kümesi (IsProperSubsetOf) • Parametre olarak geçirilen kümenin uygun bir üst kümesi (IsProperSupersetOf)
Ayrıca, iki kümenin aynı ögeleri içerip içermediğini (SetEquals) veya iki kümenin en az bir ortak ögeye sahip olup olmadığını (Overlaps) doğrulayabilirsiniz. Belirtilen işlemler dışında, kümeye yeni eleman eklenebilir (Add),
belirli bir eleman kaldırılabilir (Remove) veya tüm elemanlar kaldırılabilir (Clear) ve verilen elemanın kümede olup olmadığı kontrol edilebilir (Contains).
Sıralanmış Kümeler (Sorted Sets)
Daha önce açıklanan HashSet sınıfı; değerleri olmayan, yalnızca anahtarları depolayan bir sözlük olarak anlaşılabilir. Tanım gereği bir küme, yinelenen ögeler ve belirli bir sıra olmaksızın farklı nesnelerin bir koleksiyonunu depolar. Bir küme düzenli veri depolamayı desteklemiyorsa nasıl sıralanabilir? Sıralanmış bir küme, bir kümenin kendisi değil HashSet ve SortedList’in bir kombinasyonu olarak düşünülebilir. Sıralı küme, tekrar eden elemanlar olmadan sıralanmış farklı nesnelerden oluşan bir koleksiyona sahip olunmak istendiği zaman kullanılabilir. Uygun sınıf SortedSet olarak adlandırılır ve System.Collections. Generic ad alanında bulunmaktadır. Sıralı kümeler; UnionWith, IntersectWith, ExcludeWith, SmetricExceptWith, Overlaps, IsSubsetOf, IsSupersetOf, IsProperSubsetOf ve IsProperSupersetOf gibi HashSet sınıfında açıklananlara benzer bir dizi yönteme sahiptir. Ayrıca, minimum ve maksimum değerleri döndürmek için ek özellikler içerir (Min ve Max). Bunun yanında, verilen aralıktaki değerlerle bir SortedSet örneği döndüren GetViewBetween yöntemini de desteklemektedir.
Listeler (List)
Listeler, programlamada oldukça kullanışlı veri yapılarıdır ve birçok algoritmada uygulanırlar. Bununla birlikte bazı durumlarda kullanımları, oluşturulmuş bir listenin uzunluğunu artırmaya veya azaltmaya izin vermeyen yapıları nedeniyle karmaşıklığa neden olabilir. Peki, liste yapısında saklanacak toplam öge sayısını bilmiyorsanız ne yapmalısınız? Çok büyük bir dizi oluşturmanız ve gereksiz ögeleri kullanmamanız mı gerekiyor? Böyle bir çözüm kulağa hoş gelmiyor. Çok daha iyi bir yaklaşım, gerektiğinde listenin boyutunu dinamik olarak artırmayı mümkün kılan bir veri yapısı kullanmaktır.
Array List (Dizi Listesi)
Gerektiğinde liste boyutunu düzenleme gereksinimi karşılayan ilk veri yapısı, System.Collections ad alanından ArrayList sınıfı tarafından temsil edilen dizi listesidir. Bu sınıf, gerektiğinde kolayca yeni ögeler ekleyebileceğiniz büyük veri koleksiyonlarını depolamak için kullanılabilir. Bu sınıf ile ögeler kaldırılabilir, sayılabilir ve dizi listesinde saklanan belirli bir değerin indeksi bulunabilir.
Genel/Genelleyici Liste (Generic List)
Görüldüğü gibi ArrayList sınıfı geniş bir özellik yelpazesi içerir ancak önemli bir dezavantajı vardır, güçlü bir şekilde yazılmış bir liste değildir. Güçlü yazılan bir listeden yararlanmak istenirse gerektiğinde boyutu artırılıp azaltılabilen koleksiyonu temsil eden Generic List sınıfı kullanılabilir. Generic List sınıfı, veri depolayan uygulamalar geliştirirken çok yararlı olan birçok özellik ve yöntem içermektedir. Count ve Capacity gibi özelliklerinin yanı sıra Add, AddRange, Clear, Contains, IndexOf, Insert, InsertRange, LastIndexOf, Remove, RemoveAt,
RemoveRange gibi özelliklerin ArrayList sınıfındaki ile tamamen aynı şekilde adlandırıldığını görülmektedir. Reverse ve ToArray yöntemleri indeks ve [ ] operatörü kullanılarak listeden belirli bir elemana da ulaşılabilir. List<T>; dizine göre erişilebilen ve sıralama, arama ve listeyi değiştirme yöntemlerine sahip, kesin olarak girilmiş nesneler topluluğudur. System.Collections.Generic ad alanı altında gelen ArrayList’in genel sürümüdür.
List <T> Özellikleri
• List<T>, IList<T> arayüzünü uygulayan ArrayList’in eşdeğeridir. • System.Collections.Generic ad alanı altında gelir. • List<T>, belirtilen türdeki ögeleri içerebilir. Derleme zamanı tür denetimi sağlar ve genel olduğu için kutulama/kutudan çıkarma (boxing/unboxing) gerçekleştirmez. • Ögeler, Add(), AddRange() yöntemleri veya koleksiyon başlatıcı sözdizimi kullanılarak eklenebilir. • Ögelere bir dizin geçirilerek erişilebilir, örneğin listem[0]. İndeksler sıfırdan başlar. • List<T>, ArrayList’ten daha hızlı ve daha az hataya açık çalışır.
List<T> genel bir koleksiyondur bu nedenle depolayabileceği veri türü için bir tür parametresi belirtilmesi gerekmektedir.