Veri Yapıları — Diziler, Bağlı Listeler, Ağaçlar ve Graflar

Veri yapıları, arama, ekleme, silme ve dolaşma gibi yaygın görevleri kolaylaştıracak şekilde veriyi düzenleme yollarıdır. Dizileri, bağlı listeleri, ağaçları ve grafları anlamanın en hızlı yolu iki soru sormaktır: verinin şekli nedir ve hangi işlemin ucuz hissettirmesi gerekir?

Veri bir dizi ise başlangıç noktası çoğu zaman bir dizidir. Her öğe esas olarak bir sonraki öğeyi gösteriyorsa bağlı liste uygun olabilir. Verinin seviyeleri varsa ağaç kullanın. Öğeler birçok yönde bağlanabiliyorsa graf kullanın.

İşte en kısa faydalı kural:

• Dizi: indeksli sıra için en iyisi.
• Bağlı liste: zincirlenmiş yerel bağlantılar için en iyisi.
• Ağaç: hiyerarşi için en iyisi.
• Graf: ağlar için en iyisi.

Diziler, bağlı listeler, ağaçlar ve graflar aslında ne yapar?

Bir dizi, öğeleri sabit bir sırada tutar ve "öğe $7$" gibi bir konuma doğrudan başvurmanıza izin verir. Yaygın bitişik bellek uygulamasında bu doğrudan indeksleme $O(1)$'dir.

Bağlı liste, öğeleri her düğümün başka bir düğümü gösterdiği düğümler olarak saklar. Düğümden düğüme ilerleyebilirsiniz, ancak $n$. öğeye ulaşmak için genellikle önceki düğümlerden geçmeniz gerekir; bu yüzden konuma göre erişim tipik olarak $O(n)$'dir.

Ağaç, veriyi seviyeler halinde saklar. Her düğümün çocukları olabilir, bu yüzden yapı doğal olarak klasör içinde klasör gibi iç içe yapıları temsil eder. Arama ve güncelleme maliyetleri ağacın türüne ve dengeli kalıp kalmamasına bağlıdır.

Graf, düğümleri ve kenarları saklar. Ağaçtan farklı olarak bir düğüm keyfi biçimde birçok başka düğüme bağlanabilir ve döngülere izin verilir. Bu da grafları yollar, sosyal ağlar ve bağımlılık haritaları için doğal model yapar.

Hızlı karşılaştırma: her veri yapısı ne zaman uygundur?

Yapı	En iyi zihinsel model	Genellikle iyi olduğu şey	Yaygın sınırlama
Dizi	Numaralandırılmış bir öğe sırası	İndekse göre doğrudan erişim	Ortadan ekleme ve silme çoğu zaman öğeleri kaydırmayı gerektirir
Bağlı liste	Düğümlerden oluşan bir zincir	Bilinen bir düğümün yakınında ekleme veya çıkarma	Rastgele erişim yavaştır
Ağaç	Dallanan bir hiyerarşi	Seviyeleri ve ebeveyn-çocuk ilişkilerini temsil etme	Davranış büyük ölçüde ağaç türüne bağlıdır
Graf	Bir bağlantılar ağı	Erişilebilirlik, yollar ve ilişkiler	Algoritmalar çoğu zaman daha karmaşıktır

Çözümlü örnek: tek bir kampüs uygulamasında yapı seçimi

Diyelim ki bir kampüs uygulamasında ders programı ekranı, ders kataloğu ve yürüme haritası oluşturuyorsunuz. Veri yapısı seçmenin en kolay yolu, her özelliği verisinin şekliyle eşleştirmektir.

Ders programı ekranındaki hafta içi sekmeleri doğal olarak bir dizidir:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

Buradaki temel özellik, konuma göre doğrudan erişimdir. "Bana $3$. sekmeyi göster" anlamlıdır ve sıra önemlidir.

Ders kataloğu doğal olarak bir ağaçtır:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

Her seviye bir sonraki seviyeyi içerir. Bu bir hiyerarşidir, bu yüzden en temiz model ağaçtır.

Binalar arasındaki yürüme yolları ise doğal olarak bir graftır. Bir bina birkaç başka binaya bağlanabilir ve yollar geri dönüp döngü oluşturabilir. Kütüphaneden laboratuvara en kısa rotayı istiyorsanız, bir ağaç problemi değil, bir graf problemi çözüyorsunuzdur.

Bağlı liste, aynı uygulamanın daha dar bir kısmına uyar: eğer ana işlem birer adım ileri veya geri gitmekse, yakın zamanda ziyaret edilen ekranların zinciri. Bu durumda her ekranın, $20$. ekrana hızlı erişimden çok yakındaki ekranlara bağlantılara ihtiyacı vardır.

Buradaki ders şudur: "en iyi" seçim işe bağlıdır. Tek bir ürün birkaç veri yapısı kullanabilir çünkü verinin farklı bölümlerinin ilişkileri farklıdır.

Aralarındaki farkı hızlıca nasıl anlarsınız?

Birçok öğrenci bunları önce kelime bilgisi gibi öğrenir. Bu da konuyu soyut hissettirir, ama pratik soru daha basittir.

Şunu sorun: hangi işlem ucuz hissettirmeli?

Eğer "konum $i$'ye atla" işleminin ucuz olmasını istiyorsanız, diziler güçlüdür. Eğer "bir sonraki bağlantıyı takip et" işleminin ucuz olmasını istiyorsanız, bağlı yapılar yardımcı olur. Eğer "bir hiyerarşide aşağı in" istiyorsanız, ağaçlar uygundur. Eğer "iki şeyin bağlı olup olmadığını bul" istiyorsanız, graflar uygundur.

Veri yapılarını öğrenirken yapılan yaygın hatalar

Bir yapının her zaman en hızlı olduğunu varsaymak

Evrensel bir kazanan yoktur. "Hızlı", en sık ne yaptığınıza ve uygulamaya bağlıdır.

Ağaçları otomatik olarak verimli sanmak

Bazı ağaçlar çok verimli aramayı destekler, ancak bu ağacın türüne ve denge gibi yapısal koşullara bağlıdır. Kötü şekillenmiş bir ağaç, dengeli bir ağaçtan çok daha kötü performans gösterebilir.

Sırf ekleme ucuz görünüyor diye bağlı liste seçmek

Doğru düğüme zaten sahipseniz ekleme ucuz olabilir. Ama o düğümü bulmak yine de zaman alabilir.

Veri aslında grafken ağaç kullanmak

Bir öğenin birden fazla ebeveyni, çapraz bağlantıları veya döngüleri olabiliyorsa, veriyi zorla ağaç yapısına sokmak gerçek yapıyı gizleyebilir ve sonraki işlemleri hantallaştırabilir.

Soyut bir yapıyı programlama dili özelliğiyle karıştırmak

Bir programlama dilindeki "array", "list", "map" veya "tree", bellek kullanımı ve hızı etkileyen uygulama tercihleriyle gelebilir. Soyut fikir ile somut kapsayıcı ilişkilidir, ama aynı şey değildir.

Diziler, bağlı listeler, ağaçlar ve graflar ne zaman kullanılır?

Diziler; sıralı koleksiyonlar, tablolar, tamponlar ve konumun önemli olduğu her durumda kullanılır.

Bağlı listeler, rastgele erişimden çok yerel gösterici güncellemelerinin önemli olduğu özel uygulamalarda görülür.

Ağaçlar; dosya sistemleri, belge yapısı, ifade ağaçları ve birçok arama indeksi gibi hiyerarşik veriler için kullanılır.

Graflar; rotalar, bağımlılık analizi, ağ modelleme, öneri bağlantıları ve genel olarak bağlantı problemleri için kullanılır.

Doğru veri yapısı nasıl seçilir?

İki soru sorarak başlayın:

1. Verinin ilişkisi nedir: dizi, hiyerarşi yoksa ağ mı?
2. En önemli işlem nedir: indeksleme, yerel güncelleme, hiyerarşik dolaşma yoksa yol bulma mı?

Bu iki cevap genellikle seçimi hızlıca daraltır.

Hâlâ emin değilseniz, verinin küçük bir sürümünü kâğıda çizin. Görsel, çoğu zaman koddan önce yapıyı ortaya çıkarır.

Kendi sürümünüzü deneyin

Çalma listesi, klasör sistemi ve toplu taşıma haritası gibi tanıdık üç örnek seçin. Her birinin esas olarak bir dizi, bir hiyerarşi ya da bir ağ olup olmadığını belirleyin, sonra ana işlemi kolaylaştıran yapıyı seçin. Kendinizi sınamak için başka bir örnek isterseniz, GPAI Solver benzer sınıflandırma örnekleri üretebilir.