Veri Yapısı Nedir? Dizi, Yığın, Ağaç ve Graf Rehberi

Bir veri yapısını seçerken yalnızca depolama alanına bakılmaz

Bir veri yapısını değerlendirirken üç soruyu birlikte sormak gerekir: Veriler arasında nasıl bir ilişki var, en sık hangi işlem yapılacak ve verinin sırası korunacak mı?

Veriler basit bir sıra oluşturuyorsa doğrusal veri yapıları düşünülebilir. Dizi, bağlı liste, yığın ve kuyruk bu gruptadır. Veriler arasında üst-alt ilişkisi varsa ağaç; kullanıcılar, şehirler veya cihazlar arasındaki bağlantılar önemliyse graf daha uygun bir model olabilir.

İkinci soru işlemlerin önceliğidir. Bir uygulamada belirli bir konuma doğrudan ulaşmak önemliyse dizi gibi indeks temelli bir yapı anlamlıdır. Elemanların sık sık eklenip çıkarıldığı bir senaryoda bağlı liste esneklik sağlayabilir. Ancak bu, bağlı listenin her arama işleminde daha iyi olduğu anlamına gelmez; yapı seçimi arama, ekleme ve silme işlemlerinin birlikte değerlendirilmesini gerektirir.

Üçüncü soru erişim kuralıdır. Yığın, son giren ilk çıkar mantığıyla çalışır. Kuyruk ise ilk giren ilk çıkar mantığına dayanır. Bu iki yapı, aynı sayıda veriyi tutabilse de veriye erişim sıraları farklıdır. Dolayısıyla veri yapısının adı kadar, izin verdiği işlem düzeni de önemlidir.

Dizi ve bağlı liste: sıralı verilerde iki farklı düzen

Dizi, birden fazla veriyi sıralı biçimde tutan doğrusal bir yapıdır. Elemanlar indekslerle ayırt edilir. Örneğin ["Ali", "Buse", "Cem"] dizisinde ilk elemanın indeksi kullanılan dile göre 0 veya 1 olabilir; bu ayrıntı programlama diline bağlıdır. Bu nedenle indeksin başlangıç değerini varsaymak yerine kullanılan dilin kuralı kontrol edilmelidir.

Dizinin güçlü yönü, belirli bir indeksle ifade edilen elemana doğrudan ulaşılabilmesidir. Buna karşılık araya yeni bir eleman eklemek veya ortadaki bir elemanı silmek, sonraki elemanların konumlarının düzenlenmesini gerektirebilir. Dizi bu yüzden sırası ve konumu önemli olan veriler için anlaşılır bir seçimdir; fakat her ekleme ve silme senaryosunda en uygun yapı olduğu söylenemez.

Bağlı listede her düğüm, kendi verisinin yanında başka bir düğüme nasıl ulaşılacağını gösteren bağlantı bilgisi taşır. Düğümler bellekte yan yana bulunmak zorunda değildir. Listenin bir sonraki düğümünü gösteren bağlantılar, verilerin mantıksal sırasını oluşturur.

Bağlı listenin önemli sonucu şudur: Bir düğümün konumu değiştiğinde bütün verilerin bellekte yan yana taşınması gerekmeyebilir. Ancak belirli bir elemana ulaşmak için bağlantılar sırayla izlenebilir; bu nedenle bağlı liste, doğrudan indeksle erişim beklenen her problem için uygun değildir. Dizi ile bağlı liste arasındaki farkı yalnızca "biri hızlı, diğeri yavaş" biçiminde ezberlemek yerine, hangi işlemin ve hangi erişim biçiminin öncelikli olduğuna bakmak gerekir.

Yığın ve kuyrukta sonucu belirleyen şey erişim sırasıdır

Yığın, LIFO yani "son giren ilk çıkar" kuralını kullanır. Bir yığına sırasıyla A, B ve C eklenirse en üstte C bulunur. Çıkarma işlemleri sırasıyla C, B ve A şeklinde gerçekleşir. Web tarayıcısındaki geri gitme davranışı, ziyaret edilen sayfaların son ziyaret edilenden başlayarak geri alınması fikrine örnek olarak verilebilir.

Yığında temel işlemler genellikle üste eleman ekleme ve üstteki elemanı çıkarma ya da inceleme biçimindedir. Yığının ortasındaki bir elemana erişim, yığının temel kullanım amacı değildir. Bu nedenle yığın seçerken soru "veriyi nasıl ararım?" değil, çoğu zaman "en son eklenen veriyi önce mi işlerim?" olmalıdır.

Kuyruk, FIFO yani "ilk giren ilk çıkar" kuralıyla çalışır. Bir kuyruğa A, B ve C sırasıyla girerse ilk çıkarılacak eleman A olur. Müşteri sırası, yazdırma işleri veya sıraya alınan görevler bu mantıkla modellenebilir. Kuyrukta yeni eleman genellikle kuyruğun arkasına eklenir ve işlem görecek eleman önden alınır.

Yığın ve kuyruk birbirine benzer çünkü ikisi de doğrusal veri yapısıdır; fakat erişim kuralları aynı değildir. Bir soruda "son eklenen önce işlenecek" ifadesi varsa yığın, "gelenler geliş sırasına göre işlenecek" ifadesi varsa kuyruk düşünülmelidir.

Ağaç ve graf, veriler arasındaki ilişkiyi sıradan listenin ötesine taşır

Ağaç, bağlı ve döngüsüz bir graf türüdür. Köklü ağaçlarda düğümler kök, ebeveyn ve alt düğüm ilişkileriyle hiyerarşik olarak gösterilir; bu gösterimde ilişkiler yönlü düşünülebilir, ancak yönlülük her ağacın zorunlu özelliği değildir. Dosya klasörleri, bir kategori ve alt kategori düzeni veya üst-alt ilişkisi ağaç modeliyle anlatılabilir.

Graf ise düğümler ve bu düğümler arasındaki kenarlardan oluşan ağ benzeri bir modeldir. Sosyal ağdaki kullanıcılar düğüm, arkadaşlık veya takip ilişkileri kenar olarak gösterilebilir. Harita uygulamalarında şehirler ya da kavşaklar düğüm; yollar kenar olarak modellenebilir. Böylece iki nokta arasındaki bağlantılar ve olası rotalar temsil edilir.

Ağaç ile graf arasındaki temel ayrım, ağaçta hiyerarşik düzenin öne çıkması; grafın ise daha genel bağlantıları temsil etmesidir. Bir graf, kullanıcılar arasında çok sayıda farklı bağlantıyı gösterebilir. Bu bağlantılar yönlü veya yönsüz olarak ele alınabilir; örneğin takip ilişkisi ile karşılıklı arkadaşlık aynı ilişki biçimi değildir.

Bu yapılar doğrusal yapılardan farklıdır çünkü veriler yalnızca tek bir sıra üzerinde ilerlemez. Soruda "kök", "alt dal", "ortak arkadaş", "kavşak", "rota" veya "bağlantı" gibi ifadeler geçiyorsa liste, yığın ya da kuyruk yerine ağaç veya graf modeli değerlendirilmelidir.

Çözümlü örnek: Aynı veriyi dizi, yığın ve kuyruk olarak okumak

Verilenler: A, B ve C elemanları sırasıyla yapıya eklenecek. Amaç, çıkarma sırasında hangi elemanların hangi sırayla alınacağını bulmaktır.

Adım 1: Dizi için veriler [A, B, C] biçiminde tutulur. Dizinin temel özelliği, elemanların indekslerle ifade edilmesidir. Bu nedenle dizide "ikinci eleman" gibi konuma dayalı bir erişim yapılabilir. Çıkarma sırası ise dizinin otomatik kuralı değildir; programcının hangi indisi seçtiğine bağlıdır.

Adım 2: Yığında önce A, sonra B, sonra C eklenir. C en son eklenen eleman olduğu için üstte bulunur. Çıkarma sırası C → B → A olur.

Adım 3: Kuyrukta yine A, B ve C sırasıyla eklenir. İlk giren A olduğundan çıkarma sırası A → B → C olur.

Sonuç: Üç yapı aynı elemanları tutabilse de aynı davranışı göstermez. Sıralı veriye konumla erişmek için dizi; son eklenen öğeyi önce işlemek için yığın; geliş sırasını korumak için kuyruk seçilir. Buradaki karar, elemanların adlarından değil, istenen işlem sırasından çıkarılır.

Çözümlü örnek: Bir sosyal ağ ilişkisini graf olarak kurmak

Verilenler: Ayşe, Berk ve Ceren adlı üç kullanıcı vardır. Ayşe ile Berk arkadaş, Berk ile Ceren arkadaş kabul edilsin. Amaç, bu ilişkiyi uygun veri yapısıyla göstermektir.

Adım 1: Her kullanıcı bir düğüm olarak yazılır: Ayşe, Berk, Ceren.

Adım 2: Arkadaşlık ilişkileri kenarlarla gösterilir. Ayşe-Berk arasında bir kenar, Berk-Ceren arasında bir kenar bulunur.

Adım 3: İlişkinin karşılıklı olduğu kabul ediliyorsa bağlantı yönsüz düşünülebilir. Ayşe'nin Berk ile bağlantısı varsa Berk'in de Ayşe ile bağlantısı vardır. Eğer konu takip ilişkisi olsaydı bağlantının yönü ayrıca belirtilmeliydi; Ayşe'nin Berk'i takip etmesi, Berk'in Ayşe'yi takip ettiği sonucunu tek başına doğurmaz.

Adım 4: Bu modelde Ayşe ile Ceren arasında doğrudan bir kenar yoktur; ancak Ayşe → Berk → Ceren şeklinde iki bağlantıdan oluşan bir yol vardır.

Sonuç: Kullanıcılar arasındaki bağlantılar tek bir sıra oluşturmadığı için bu problem grafla modellenir. Aynı verileri bir diziye yazmak kullanıcı adlarını saklayabilir; fakat arkadaşlık ilişkilerinin kimler arasında olduğunu doğal biçimde göstermez.

Sık yapılan hatalar ve karıştırılan kavramlar

1. Veri yapısını algoritmayla aynı sanmak: Veri yapısı verilerin düzenini ve erişim biçimini belirler. Algoritma ise bu veriler üzerinde problemi çözmek için izlenen adımlardır. Bir algoritma, seçilen veri yapısından bağımsız düşünülse bile uygulamadaki davranışı veri yapısından etkilenebilir.

2. Her veri yapısının her işlemi eşit biçimde yaptığına inanmak: Dizi, bağlı liste, yığın, kuyruk, ağaç ve graf farklı amaçlara sahiptir. Bir yapının belirli bir işlemde kullanışlı olması, diğer bütün işlemlerde de en iyi seçenek olduğu anlamına gelmez.

3. Yığın ile kuyruğu karıştırmak: Yığın LIFO, kuyruk FIFO kuralına dayanır. "Son eklenen önce çıkar" yığını; "ilk gelen önce işlenir" kuyruğu gösterir.

4. Grafı yalnızca haritalarla sınırlamak: Haritalar grafik yapısına iyi bir örnektir; ancak sosyal ağ ilişkileri de düğüm ve kenarlarla modellenebilir. Grafın ayırt edici yönü, nesneler arasındaki bağlantıları göstermesidir.

5. Ağaç ile grafı her durumda eş anlamlı kullanmak: Ağaç hiyerarşik bir düzeni anlatır. Graf daha genel bir bağlantı modelidir. Klasör-alt klasör ilişkisi ağaç mantığına, takipçi ilişkileri ise graf mantığına daha yakındır.

6. Bağlı listenin indeksle doğrudan erişim sağladığını düşünmek: Bağlı listede düğümler bağlantılarla takip edilir. Bu nedenle listedeki belirli bir konuma ulaşma biçimi, diziyle aynı değildir.

7. İndekslerin her dilde aynı başladığını varsaymak: Bazı dillerde ilk indeks 0, bazılarında 1 olabilir. Sınav veya kod sorusunda dilin ve sorunun verdiği indeks kuralı dikkate alınmalıdır.

TYT-AYT ve ders sorularında veri yapısını ayırt etme yöntemi

Soruyu çözerken önce veri türünü değil, işlem kuralını ve ilişki biçimini bulun.

• "Son eklenen ilk çıkar", "geri alma" veya "üstten çıkarma" ifadeleri yığını gösterir. • "İlk gelen ilk işlenir", "bekleme sırası" veya "önden alma" ifadeleri kuyruğu gösterir. • "İndeks", "sıra numarası" ve "konum" vurgusu diziyi düşündürür. • "Düğümler birbirine bağlantıyla bağlı" veya "sonraki elemanı gösterir" ifadesi bağlı listeyi işaret eder. • "Kök", "dal", "alt düğüm" ve "hiyerarşi" ağaç için ipucudur. • "Kavşak", "rota", "arkadaşlık", "takip" ve "kenar" ifadeleri grafı düşündürür.

Sınavda yalnızca yapının adını bulmak yetmez; verilen işlemin sonucunu da sırayla takip etmek gerekir. Örneğin A, B, C sırasıyla yığına eklenmişse ilk çıkarılacak eleman C'dir. Aynı sıra kuyrukta verilirse ilk çıkarılacak eleman A olur. Bu nedenle işlem sırasını küçük bir liste veya oklarla yazmak, ezber kaynaklı hataları azaltır.

Veri yapısı ile algoritmayı ayırmak için şu kısa testi kullanabilirsiniz: "Veriler nasıl tutuluyor?" sorusu veri yapısını; "Bu veriler üzerinde hangi adımlar izleniyor?" sorusu algoritmayı sorgular.